7.

Routing and Routing Protocols

Mulugeta Libsie [Link]@[Link]

Motivation
 Traditionally, routing and forwarding were done by each and every
router
 Software Defined Networking (SDN) introduced the separation of
routing and forwarding and introduced the concepts of control plane
and data plane
 In SDN, routing is done by a central controller and the flow tables
(forwarding tables) are downloaded to each router
 The controller runs in the control plane
 Only the controller runs routing algorithms and protocols
 In addition to routing, the controller is also in charge of network
management functions
 The other routers are in charge of only forwarding
 Such routers run in the data plane

1
Objectives of the Chapter
 We will discuss
 Routing and forwarding
 Routing algorithms and protocols
 Classification of routing algorithms
 Shortest path routing
 Software Defined Networking
 Definition, major goals, control plane and data plane, SDN
controllers, flow table, OpenFlow protocol, major benefits of
SDN
 Router architecture

2
 7.1 Introduction
 There are two important network layer functions: routing and
forwarding
 Routing: is determining the route to be taken by packets from
source to destination
 The algorithms that calculate these paths are referred to as
routing algorithms
 Routing is often implemented in software on the control plane
 Forwarding: is moving packets from a router’s input link to an
appropriate router output link; some also call it switching
(especially in SDN)
 In SDN, a packet might also be blocked from exiting a router
(e.g., if the packet originated at a known malicious sending host,
or if the packet were destined to a forbidden destination host),
or might be duplicated and sent over multiple outgoing links
(multicasting)
 Forwarding is often implemented in hardware on the data plane
3
Introduction (2)
 In traditional approach, both Routing
routing and forwarding are algorithm Control Plane
the tasks of routers Data Plane
Local forwarding table
 Every router has a Header value Output link
forwarding table (or routing
0100 3
table)
0101 2
 The header value could be 0111 2
1001 1
the destination address of
the packet or the
connection into which the
1
packet belongs 0111
3 2
 In IPv4, the table will have 4
billion (232) possible entries Value in arriving
(sometimes called brute- packet’s header
force implementation)
4
Introduction (3)
 There are two types of controls: per-router control and logically
centralized control
 Per-router control: In traditional routing
 A routing algorithm runs in each and every router
 Both forwarding and routing functions are contained within each
router
 Each router has a routing component that communicates with the
routing components in other routers to compute the values for its
forwarding table

5
Introduction (4)

Communication
with other routers

Per-router control: Individual routing algorithm

components interact in the control plane

6
Introduction (5)
 Logically centralized control
 In SDN, a logically centralized controller computes and distributes
the forwarding tables (called flow tables) to be used by each and
every router
 This allows the controller to perform traditional IP forwarding as well
as a rich set of other functions (load sharing, firewalling, and NAT)
that had been previously implemented in separate systems
 The controller interacts with a Control Agent (CA) in each of the
routers via a well-defined protocol to configure and manage that
router’s flow table
 The CAs do not directly interact with each other (as in per-router
control) nor do they actively take part in computing the forwarding
table

7
Introduction (6)

Logically centralized control: A distinct, typically remote,

controller interacts with local control agents (CAs)

8
Introduction (7)
 Typically a host is attached directly to one router, the default router
for the host (also called the first-hop router for the host)
 Whenever a host sends a packet, the packet is transferred to its
default router
 What is the purpose of a routing algorithm?
 Given a set of routers, with links connecting the routers, a routing
algorithm finds a “good” path from the default router of the source
to the default router of the destination
The source and the First-Hop or Default First-Hop or Default
destination can also be router of source router of destination
an independent machine
attached to its own
router or part of a
network with routers
Source Destination

9
 7.2 Routing Algorithms and Protocols
5
Graph abstraction
3
v w 5
2
u 2 1 z
3
1 2
x 1
y
 Graph: G = (N,E) is a set of N nodes and a collection of E edges
 N = { u, v, w, x, y, z }; nodes represent routers
 E = { (u,v), (u,x), (u,w), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) }
 The arcs are labeled as a function of cost
 c(x, x’) = cost of link (x, x’)
 e.g., c(w, z) = 5
 Cost could always be 1 (hop count), or related to bandwidth, or
congestion
 Cost of path (x1, x2, x3, …, xp) = c(x1, x2) + c(x2, x3) + … + c(xp-1, xp)
10
Routing Algorithms and Protocols (2)
 A routing algorithm finds the least-cost path; this is true whether we
use traditional routing or SDN; for example, the least-cost path
between source node u and destination node w is (u, x, y, w) with a
cost of 3
 Note: we will only consider undirected graphs (i.e., graphs whose
edges do not have a direction)
 It means edge (x, y) is the same as edge (y, x) and that
c(x, y) = c(y, x)
 However, this is true only if the load carried on both directions on
the link (x, y) is the same; otherwise there will be different delays

11
Routing Algorithms and Protocols (3)
 Metrics used
 A metric is a cost assigned for passing through a network
 The cost could be the level of congestion of a link (mean queue
length, transmission delay, average traffic), bandwidth, the
geographic distance traversed by the link, number of hops,
estimated transit time, communication cost (money), ...
 Cost may change with time
 Which cost to choose depends on the application
 The total metric of a particular route is equal to the sum of the
metrics of networks that comprise the route
 A router (routing algorithm) chooses the route with the shortest
(smallest) metric

12
Routing Algorithms and Protocols (4)
 Routing algorithms can be classified in various ways
 Nonadaptive (static) and adaptive (dynamic)
 Interior (intra-AS) and exterior (inter-AS)
 Centralized and decentralized
 Load-sensitive and load-insensitive (left for reading)
Nonadaptive (Static)
 These routing decisions are not based on measurements or
estimates of the current topology or traffic
 The choice of a route is computed in advance, off-line, and
downloaded to the routers when the network is booted or
 An administrator enters the route for each destination into the
forwarding table
 Routing decisions are not automatically updated when there is a
change

13
Routing Algorithms and Protocols (5)
 Advantages of Static Routing
 There is no overhead on the router (that means a cheaper
router can do the job)
 There is no bandwidth usage between routers
 It adds security since the administrator can choose to allow
routing access to certain networks only
 Disadvantages of Static Routing
 The administrator must understand the internetwork and how
each router is connected in order to configure routers correctly
 If a network is added to the internetwork, the administrator has
to add a route to it on all routers – manually
 May be it can be used in a small internetnetwork, but not for big
internetnetwork like the Internet

14
Routing Algorithms and Protocols (6)
Adaptive (Dynamic)
 Routing decisions are made periodically (every δ sec) to reflect
changes in the topology, traffic, a shutdown of a router, a break
in the link, a better route has been created, ...
 Read about routing loops and route oscillation which are
problems of dynamic routing
Interior (intra-AS) and exterior (inter-AS) routing (protocols)
 Since an internet can be large, one routing protocol cannot
handle the task of updating the routing tables of all routers
 Hence, an internet is divided into autonomous systems

15
Routing Algorithms and Protocols (7)
 An autonomous system (AS) is a group of networks and routers under
the authority of a single administration
 An AS is identified by its globally unique autonomous system number
(ASN); a 2- or 4-byte number
 Up until IETF proposed a gradual transition to 4-byte ASNs in 2007, all
ASNs were 2-byte
 There is no longer a distinction between a 2-byte and 4-byte ASN, and
all ASNs should be considered 4-byte
 ASNs, like IP addresses, are assigned by ICANN/IANA regional
registries and are used by routing protocols
 ASNs are assigned to entities such as ISPs and other large
organizations that control blocks of IP addresses
 As an ISP, ethio telecom’s ASN is AS24757 and Safaricom’s is AS328988;
There are a total of 10 organizations in Ethiopia; 4 of them are inactive
 See [Link] for the total number of ASNs per country;
You will also get more information about Ethiopia

16
Routing Algorithms and Protocols (8)
 Routing inside an autonomous system is referred to as interior (or intra-
AS) routing; each AS can choose its own routing protocol; routers
exchange information only with routers in the same AS
 Routing between autonomous systems is referred to as exterior (or
inter-AS) routing; one protocol is usually chosen to handle routing
between autonomous systems; usually used for routing in the Internet

17
Routing Algorithms and Protocols (9)

Interconnected ASes 3c
3a 2c
3b 2a
AS3 2b
1c
AS2
1a 1b AS1
1d

Forwarding Intra-AS Inter-AS

table routing routing
algorithm algorithm

 3a, 1c, 1b, and 2a use both interior and exterior routing protocols
(gateway routers)
 The rest use only interior routing protocols (internal routers)
 Solid lines: communication between routers within an AS, called
internal BGP (iBGP) connection
 Broken lines: communication between the routers that use an exterior
routing protocol - between ASes, called external BGP (eBGP)
connection
18
Routing Algorithms and Protocols (10)
 Forwarding tables are configured by both intra- and inter-AS routing
algorithms
 Intra-AS sets entries for internal destinations
 Inter-AS & intra-AS set entries for external destinations
Centralized
 A centralized routing algorithm computes the least-cost path
between a source and destination using complete, global
knowledge about the network
 That is, the algorithm takes the connectivity between all nodes
and all link costs as inputs
 Algorithms with global state information are often referred to as
Link State algorithms, since the algorithm must be aware of the
cost of each link in the network

19
Routing Algorithms and Protocols (11)
Decentralized
 The calculation of the least-cost path is carried out in an
iterative, distributed manner by the routers
 Each node begins with only the knowledge of the costs of its
own directly attached links
 Then, through an iterative process of calculation and exchange
of information with its neighboring nodes, a node gradually
calculates the least-cost path to a destination
 An example is the Distance Vector algorithm, because each
node maintains a vector of estimates of the costs (distances) to
all other nodes in the network
 Read about load-sensitive and load-insensitive algorithms

20
Routing Algorithms and Protocols (12)
 Routing Algorithms: The set of optimal routes from all sources to a
given destination form a tree rooted at the destination called a sink tree

A subnet: Routers as nodes Sink tree for router B

and links (distance metric is the number of hops)

 The sink tree is not necessarily unique; as a tree it does not contain
any loops;  each packet will be delivered within a finite and bounded
number of hops; at least in theory
 The goal of a routing algorithm is to discover the sink trees for all
routers
 The sink tree serves as a benchmark to measure routing algorithms
21
Routing Algorithms and Protocols (13)
 Let us discuss Shortest Path Routing and Flooding
 Shortest Path Routing (by Dijkstra)
 It is a link-state routing algorithm
 Aim: build a graph of the subnet - each node of the graph
representing a router and each arc representing a link
 The arcs are labeled as a function of any one of the metrics
discussed (distance, hop count, ...); assume these costs are given
 To select a route between two routers, the algorithm finds the
“shortest” path between them on the graph

22
Routing Algorithms and Protocols (14)
Algorithm
// Initialization Step
N’ = {A} // A is the source node; N′ is subset of nodes
For all nodes V // V is in N′ if the least-cost path from the source
// to V is definitively known
If V is a neighbor of A
then D(V) = c(A, V) // D(V) is distance or cost between A and V initially

Else D(v) = ∞
Repeat // Iteration Step
Find W not in N’ such that D(W) is a minimum
Add W to N’
Update D(V) for each neighbor V of W and not in N’
D(V) = min(D(V), D(W)+ c(W, V)) // new cost to V is either old cost
// to V or known least path cost to
Until N’= N // N is total number of nodes // W plus cost from W to V

23
Routing Algorithms and Protocols (15)
 How does the algorithm work to find the shortest path?
 Let us find the path from A to D
 Each node is labeled with its distance from the source; initially
labeled ∞ since no path is known
 A label may be tentative or permanent (when the shortest possible
path is found - filled-in circle) Working node

24
Routing Algorithms and Protocols (16)

 The shortest path is ABEFHD

25
Routing Algorithms and Protocols (17)
 When the algorithm terminates, we have, for each node, its
predecessor along the least cost path from the source node
 For each predecessor, we also have its predecessor, and so in this
manner we can construct the entire path from the source to all
destinations Destination Link
LC=Least Cost from A B (A, B)
LC = 2
G (A, B)
LC = 9
B C E (A, B)
LC = 4
F (A, B)
A E F D
LC = 6 LC = 10
C (A, B)
G H H (A, B)
LC = 5 LC = 8
D (A, B)

The resulting least cost paths and forwarding table for A

26
Routing Algorithms and Protocols (18)
 As a second example, assume we want to find the path from U to Z
5
3 W 5
2 V
1 Z
U 2 3
2
1 X Y
1
(a) (b)
W(4,X)

V(2,U) Z( ,-)

X(1,U) Y(2,X)

(c) (d)
W(3,Y) W(3,Y)
V(2,U) V(2,U)
Z(4,Y) Z(4,Y)
U U

X(1,U) Y(2,X) X(1,U) Y(2,X)

(e) (f)

27
Routing Algorithms and Protocols (19)
 The shortest path is UXYZ
LC=Least Cost from U Destination Link
LC = 2 LC = 3 V (U, V)
V W X (U, X)
U Z W (U, X)
X Y
LC = 4 Y (U, X)
LC = 1 LC = 2 Z (U, X)

The resulting least cost paths and forwarding table for U

28
Routing Algorithms and Protocols (20)
Flooding (for multicast and broadcast routing)
 Every incoming packet is sent out on every outgoing line except
the one it arrived on
 Packets received a second time are discarded
 It generates too many duplicate packets
 Some measures required to avoid having an infinite number of
packets
 For example, have a hop counter included in the header of
each packet; Initially initialized by the number of hops from
source to destination
 Each hop decrements it and the packet is discarded when the
counter is zero
 For instance the Time to live field in the IPv4 header or Hop
limit in the IPv6 header can be used

29
Routing Algorithms and Protocols (21)
 Selective flooding is a variant; send only on those lines that are
going approximately in the right direction
 Possible applications of flooding include the following
 To update all databases concurrently in a distributed database
system (multicast routing)
 In wireless networks where every station can listen (broadcast
routing)
 If there is a possibility of many routers being destroyed such as
in a military application (may be for unicast transmission too)
 Flooding is not mostly practical
 However, since flooding always chooses the shortest path, it can
serve as a benchmark for other routing algorithms

30
Routing Algorithms and Protocols (22)
 Read about the following
 Interior (inside an AS) routing protocols
 RIP (Routing Information Protocol)
 OSPF (Open Shortest Path First)
 EIGRP (Enhanced Interior Gateway Routing Protocol) by Cisco
(was proprietary, but became an open standard in 2013 and
was published as RFC 7868 in 2016)
 Exterior (between ASs) routing protocol
 BGP (Boarder Gateway Protocol)
 Hierarchical Routing
 Multicast and Broadcast routing protocols
 Note that OSPF and BGP are the two widely deployed Internet
routing protocols
 OSPF operates within a single ISP’s network; BGP serves to
interconnect all of the networks in the Internet; BGP is thus often
referred to as the “glue” that holds the Internet together
31
 7.3 Software Defined Networking (SDN)
 Why is SDN developed?
 Answer: To ease the management of networks
 Recall that, loosely, management includes everything related to the
control plane (as we discussed in FCAPS)
 How are these tasks done traditionally?
 Network administrators master the complexity of networks
 They must understand all aspects of networks
 They must keep myriads of details in mind
 Definition of SDN
 SDN is a framework to allow network administrators to
automatically and dynamically manage and control a large number
of network devices, services, topology, traffic paths, and packet
handling (quality of service) policies using high-level languages
and APIs Fault, Configuration, Accounting, Performance, Security
 Management includes provisioning, operating, monitoring,
optimizing and managing FCAPS in a multi-tenant environment
32
7.3.1 Major Goals of SDN
 Routing  Isolation
 Access Control  Load Balancing (Traffic Engineering)
Routing
 Basic connectivity: route packets to destination
 Switches/routers send connectivity information to the controller
 Controller computes routes based on graph of network and sends
forwarding state to switches/routers
 Controller is replicated for resilience
 System is only “logically centralized”
 Note that in SDN the term switch (or packet switch) is usually
used instead of a router
 This is because forwarding decisions may be made using
network-layer and/or link-layer source and destination
addresses as well as many other values in transport-, network-,
and link-layer packet-header fields
33
Major Goals of SDN (2)
Access Control
 Operators want to limit access to various hosts
 e.g., Don’t let laptops access backend database machines
 This can be imposed by switches/routers using ACLs (Access
Control Lists)
 In SDN
 The controller decides who can talk to who
 and passes this information to SDN platform
 Appropriate ACL flow entries are added to network
 in the right places (based on the topology)

34
Major Goals of SDN (3)
 Isolation
 We want multiple LANs on single physical network
 Packets on LAN don’t pass through routers
 Traditionally used mechanisms: Firewalls, VLANs
 Load Balancing (Traffic Engineering)
 We want to avoid persistent overloads on links
 Choose routes to spread traffic load across links
 Often done with centralized computation
 Take snapshot of topology
 Compute appropriate MPLS/OSPF state (Multiprotocol Label
Switching/Open Shortest Path First)
 Send to network
 In the remaining part of this section, our discussion will be mostly
about routing
35
7.3.2 Control and Data Planes
 Traditional routers implement both routing and forwarding
 SDN separates the Data and Control planes
a. Data Plane: forwarding; often implemented in hardware
 It consists of the network’s switches that execute the
“match-plus-action” rules in their flow tables
 Switches contain forwarding table/flow table (computed by the
Control Plane)

36
Control and Data Planes (2)
b. Control Plane: decision
 It is implemented by controller (Controller ≡ SDN Controller ≡
Remote Controller ≡ Network Operating System)
 It consists of servers and software that determine and manage
the switches’ flow tables
 All forwarding state is computed by the controller and
downloaded to the switches; located remotely and controls the
data plane  Inside an AS  Between ASs
 Contains routing protocols such as OSPF and BGP
 The remote controller might be implemented in a remote data
center with high reliability and redundancy, and might be
managed by an ISP or some third party
 Hence, the network is “software-defined” because the controller
that computes forwarding tables and interacts with routers is
implemented in software
37
7.3.3 SDN Controllers
 Components of the SDN architecture: SDN-controlled switches, the
SDN controller, network-control applications
Note: These are not end
user applications

38
SDN Controllers (2)
 A controller’s functionality can be broadly organized into three
layers Northbound
Interface, abstractions for network control apps API

Network RESTful ... Intent

graph API

Network-wide distributed, robust state management

Flow
Statistics ... Tables SDN
Controller
Link-state Host Switch
Info Info
... Info

Communication to/from controlled devices

OpenFlow ... SNMP

Southbound
API

Components of an SDN controller

39
SDN Controllers (3)
 A communication layer
 Communicating between the SDN controller and controlled
network devices
 A device must be able to communicate locally-observed events to
the controller (e.g., a message indicating that an attached link has
gone up or down, that a device has just joined the network)
 This protocol constitutes the lowest layer of the controller
architecture
 The communication between the controller and the controlled
devices cross what has come to be known as the controller’s
“southbound” interface
 OpenFlow provides this communication functionality which is
implemented in most, if not all, SDN controllers; OpenFlow was
developed by a team of researchers who worked with switch
vendors to expose this interface to software programs – see later
for OpenFlow when discussing Flow Tables

40
SDN Controllers (4)
A network-wide state-management layer
 The ultimate control decisions made by the SDN control plane
(e.g., configuring flow tables in all switches to achieve the desired
end-to-end forwarding, to implement load balancing, or to
implement a particular firewalling capability) will require that the
controller have up-to-date information about state of the
networks’ hosts, links, switches, and other SDN controlled
devices
 A switch’s flow table contains counters whose values might also
be used by network-control applications; these values should
thus be available to the applications
 Since the ultimate aim of the control plane is to determine flow
tables for the various controlled devices, a controller might also
maintain a copy of these tables; these pieces of information all
constitute examples of the network-wide “state” maintained by the
SDN controller
41
SDN Controllers (5)
The interface to the network-control application layer
 The controller interacts with network-control applications through
its “northbound” interface
 This API allows network-control applications to read/write network
state and flow tables within the state-management layer
 Applications can register to be notified when state-change events
occur, so that they can take actions in response to network event
notifications sent from SDN-controlled devices
 Different types of APIs may be provided, for example, an SDN
controller can communicate with its applications using a REST
request-response interface (REST stands for Representational
State Transfer – Read about the details of REST)
 Controller functions (and the databases used to hold state
information) are implemented by a distributed set of servers for fault
tolerance, high availability, scalability, or for performance reasons
42
SDN Controllers (6)
 SDN Controller Implementations
 In the earliest days of SDN, there was a single SDN protocol
(OpenFlow) and a single SDN controller (NOX)
 Since then, the number of SDN controllers in particular has grown
significantly
 Some SDN controllers are company-specific and proprietary, e.g.,
ONIX, Juniper, Networks Contrail, and Google’s controller for its B4
wide-area network (the first SDN; Google demonstrated the
feasibility of SDN while many others were skeptic; read page 447
of Kurose and Ross for more)
 But many more controllers are open-source and implemented in a
variety of programming languages
 Most recently, the OpenDaylight controller and the ONOS
controller have found considerable industry support; they are both
open-source and are developed in partnership with the Linux
Foundation

43
7.3.4 Flow Table
 Each switch contains a match-plus-action table (or flow table) that is
computed and distributed by a remote controller
 Note that forwarding table is for destination-based (traditional)
forwarding while flow table is for generalized forwarding; both link
the network layer’s data and control planes

44
Flow Table (2)
 In traditional destination-based forwarding there are two steps
 match: looking up a destination IP address
 action: sending the packet to the specified output port
 In SDN, we have a more general “match-plus-action” paradigm
 The SDN Controller manages the traffic (network flows) by
manipulating the flow table at switches
 Instructions are stored in flow tables
 When a packet arrives at a switch, it matches the header fields with
flow entries in a flow table
 If any entry matches, it performs the indicated actions
 The “match” can be made over multiple header fields
associated with different protocols at different layers
 If there is no match, the switch asks the controller by sending a
message with the packet header

45
Flow Table (3)
 The “action” can include the following
 Forwarding: An incoming packet may be forwarded to a particular
physical output port, broadcast over all ports (except the port on
which it arrived) or multicast over a selected set of ports
 Dropping: A flow table entry with no action indicates that a
matched packet should be dropped
 Purposefully dropping a packet - as in a firewall (e.g., if the
packet originated at a known malicious sending host, or if the
packet were destined to a forbidden destination host)
 Load balancing: packets are sent across multiple outgoing
interfaces that lead to a service (as in traditional load balancing)
 Modify-Field/Rewriting header values (as in NAT); the values in
ten packet header fields (all layer 2, 3, and 4 fields except the IP
Protocol field) may be re-written before the packet is forwarded to
the chosen output port, e.g., At the IPv4 header, decrement the
TTL and update the checksum
46
Flow Table (4)
 Sending a packet to a special server for further processing and action
(as in DPI - Deep Packet Inspection)
 Each entry in the match-plus-action forwarding table, known as a
flow table in OpenFlow, includes the following
 A set of header field values to which an incoming packet will be
matched; a packet that matches no flow table entry can be
dropped or sent to the remote controller for more processing
 A set of counters that are updated as packets are matched to flow
table entries; these counters might include the number of packets
that have been matched by that table entry, and the time since
the table entry was last updated
 A set of actions to be taken when a packet matches a flow table
entry; these actions might be to forward the packet to a given
output port, to drop the packet, to make copies of the packet and
send them to multiple output ports, etc.

47
Flow Table (5)
 The following are eleven packet-header fields and the incoming port ID
that can be matched in an OpenFlow 1.0 match-plus-action rule
Ingress Src Dst Eth VLAN VLAN IP IP TCP/UDP TCP/UDP
IP Src IP Dst
Port MAC MAC Type ID Pri Proto ToS Src Port Dst Port

Link Layer Network Layer Transport Layer

 OpenFlow’s match abstraction allows for a match to be made on

selected fields from three layers of protocol headers (defying the
layering principle)
 The ingress port refers to the input port at the packet switch on which a
packet is received
 Src MAC and Dst MAC are the source and destination MAC addresses
which means an OpenFlow-enabled device can equally perform as a
router (layer-3 device) forwarding datagrams as well as a switch (layer-
2 device) forwarding frames (replacing self-learning by switches)
 The Ethernet type field corresponds to the upper layer protocol (e.g.,
IP) to which the frame’s payload will be de-multiplexed, and the VLAN
fields are concerned with VLANs
48
Flow Table (6)
 The other fields are packet’s IP source address, IP destination
address, IP protocol field, IP type of service fields and the transport-
layer source and destination port number fields
 Flow table entries may also have wildcards; for example, an IP
address of 128.119.*.* in a flow table will match the corresponding
address field of any datagram that has 128.119 as the first 16 bits of
its address
 Each flow table entry also has an associated priority; if a packet
matches multiple flow table entries, the selected match and
corresponding action will be that of the highest priority entry with
which the packet matches
 Note that not all fields in an IP header can be matched; for example
OpenFlow does not allow matching on the basis of TTL field or
length field
 The set of twelve values that can be matched in the OpenFlow 1.0
specification has grown to 41 values in more recent OpenFlow
specifications
49
Flow Table (7)
 Note that there were multiple versions of OpenFlow
 OpenFlow version 1.0 has a single match-action table
 Later versions of OpenFlow (the most prominent version being
OpenFlow 1.3) added more complex operations, including chains of
tables, but very few vendors ever implemented these standards
 In SDN, self-learning behaviour of switches is not required and
switch tables are constructed by the controller
 On startup, switches are instructed by the controller to report their
neighboring switches and hosts
 With this information the controller is then able to form a complete
map of the switch topology
 Once the location of a destination host has been learned by the
controller (that is, the controller learns which switch the host is
directly connected to), the controller calculates the shortest path
from each switch to that host; the controller then instructs each
switch how to forward to that host
50
Flow Table (8)
 Example
 Assume a network that has 6 hosts (h1, h2, h3, h4, h5 and h6)
and three switches (s1, s2 and s3), each with four local interfaces
(numbered 1 through 4)
OpenFlow Controller
Host h4
[Link]
Host h6
[Link]
1 4
4 1
s3 s2 Host h3
2 2
3 3 [Link]
1 4
s1
Host h5 Host h2
2 3
[Link] [Link]
Host h1
[Link]

51
Flow Table (9)
 We will consider a number of network-wide behaviors that we would
like to implement, and the flow table entries in s1, s2 and s3 needed
to implement this behavior
 Example 1: Simple Forwarding
 Packets from h5 or h6 destined to h3 or h4 are to be forwarded
from s3 to s1, and then from s1 to s2 (thus completely avoiding
the use of the link between s3 and s2); the flow table entry in s1
would be the following
s1 Flow Table
Match Action
Ingress port = 1 ; IP Src = 10.3.*.* ; IP Dst = 10.2.*.* Forward(4)
.... ….

52
Flow Table (10)
 We also need a flow table entry in s3 so that datagrams sent from
h5 or h6 are forwarded to s1 over outgoing interface 3
s3 Flow Table
Match Action
IP Src = 10.3.*.* ; IP Dst = 10.2.*.* Forward(3)
.... ….

 We also need a flow table entry in s2 to complete this first example,

so that datagrams arriving from s1 are forwarded to their
destination, either host h3 or h4
s2 Flow Table
Match Action
Ingress port =2; IP Dst = [Link] Forward(3)
Ingress port =2; IP Dst = [Link] Forward(4)
.... ….

53
Flow Table (11)
Example 2: Load Balancing
 Let us consider a load balancing scenario, where datagrams from
h3 destined to 10.1.*.* are to be forwarded over the direct link
between s2 and s1, while datagrams from h4 destined to 10.1.*.*
are to be forwarded over the link between s2 and s3 (and then
from s3 to s1)
 Note that this behavior couldn’t be achieved with IP’s destination-
based forwarding; in this case, the flow table in s2 would be the
following
s2 Flow Table
Match Action
Ingress port=3; IP Dst = 10.1.*.* Forward(2)
Ingress port=4; IP Dst = 10.1.*.* Forward(1)
.... ….

54
Flow Table (12)
 We also need flow tables for s1 and s3
s1 Flow Table
Match Action
Ingress port = 4; IP Dst = [Link] Forward(2)
Ingress port = 4; IP Dst = [Link] Forward(3)
.... ….

s3 Flow Table
Match Action
Ingress port = 4; IP Dst = 10.1.*.* Forward(3)
.... ….

55
Flow Table (13)
Example 3: Firewalling
 Let us consider a firewall scenario in which s2 wants only to
receive (on any of its interfaces) traffic sent from hosts attached
to s3
 Note that this behavior couldn’t be achieved with IP’s destination-
based forwarding
 In this case, the flow table in s2 would be the following
s2 Flow Table
Match Action
IP Src = 10.3.*.*; IP Dst = [Link] Forward(3)
IP Src = 10.3.*.*; IP Dst = [Link] Forward(4)
.... ….

 If there were no other entries in s2’s flow table, then only traffic from
10.3.*.* would be forwarded to the hosts attached to s2

56
 7.4 Router Architecture
 A router has four components (whether SDN or traditional routing is
used): Input ports, switching fabric, output ports, and routing
processor

57
Router Architecture (2)
Input ports
 An input port performs the physical and link layer functions
 Lookup Function: The forwarding table is consulted to
determine the router output port (possibly zero or more than
one) to which an arriving packet will be forwarded via the
switching fabric

 The number of ports supported by a router can range from a

relatively small number in enterprise routers, to hundreds of 10
Gbps ports in a router at an ISP’s edge
 For example, the Juniper MX2020 edge router supports up to 960
Ethernet ports each with 10 Gbps, with an overall router system
capacity of 80 Tbps
58
Router Architecture (3)
Switching fabric: connects the router’s input ports to its output ports
 Read about the different methods of switching
Output ports: An output port stores packets received from the
switching fabric and transmits these packets on the outgoing link by
performing the necessary link layer and physical layer functions

59
Router Architecture (4)
 Routing processor: The routing processor performs control plane
functions
 In traditional routers, it executes the routing protocols, maintains
routing tables, and computes the forwarding table for the router
 In SDN routers, the routing processor is responsible for
communicating with the remote controller in order to receive
forwarding table entries computed by the remote controller, and
install these entries in the router’s input ports
 The routing processor also performs the network management
functions that we discussed in Chapter 6 (Managing Server)
 Input ports, output ports, and switching fabric are almost always
implemented in hardware while the routing processor is
implemented in software (typically on a traditional CPU)

60
Router Architecture (5)
 Queuing: occurs both at input ports and output ports
 It occurs at the input ports if the switch fabric is not fast enough -
relative to the input line speeds - to transfer all arriving packets
through the fabric without delay
 As these queues grow large, the router’s memory can eventually
be exhausted and packet loss will occur when no memory is
available to store arriving packets

 Scheduling: What is the order in which queued packets are

transmitted over an outgoing link? We will discuss scheduling in
Chapter 10 – Multimedia Networking

61
Comment from Innovation/Implementation Point of View
 SDN has been heralded as the future of networking; someday that
future may arrive
 While SDN has been very successful in some specific areas,
Ethernet installations are still dominant in LANs
 SDN represents a significant “unbundling” of network functionality
 Data plane switches, SDN controllers, and network-control
applications are separate entities that may each be provided by
different vendors and organizations
 With the pre-SDN model, a switch/router (together with its
embedded control plane software and protocol implementations)
was monolithic and sold by a single vendor

62
Comment from Innovation Point of View (2)
 This unbundling of network functionality in SDN has been likened to
 the earlier evolution from mainframe computers (where hardware,
system software, and applications were provided by a single
vendor) to
 personal computers (with their separate hardware, operating
systems, and applications)
 The unbundling of computing hardware, system software, and
applications has led to a rich, open ecosystem driven by innovation
in all three of these areas

63
 Network Functions Virtualization (NFV)
 Read about Network Functions Virtualization (NFV) which is a
generalization of SDN to virtualize entire classes of network node
functions such as virtualized load balancers, firewalls, intrusion
detection devices, etc.

64