Module 4
Network Layer
a. Overview of Network Layer
Shows a simple network with two hosts, H1 and H2, and several routers on the
path between H1 and H2. Let’s suppose that H1 is sending information to H2, and
consider the role of the network layer in these hosts and in the intervening routers. The
network layer in H1 takes segments from the transport layer in H1, encapsulates each
segment into a datagram, and then sends the datagrams to its nearby router, R1. At the
receiving host, H2, the network layer receives the datagrams from its nearby router R2,
extracts the transport-layer segments, and delivers the segments up to the transport layer
at H2. The primary data-plane role of each router is to forward datagrams from its input
links to its output links; the primary role of the network control plane is to coordinate
these local, per-router forwarding actions so that datagrams are ultimately transferred
end-to-end, along paths of routers between source and destination hosts.
Forwarding. When a packet arrives at a router’s input link, the router must move
the packet to the appropriate output link. For example, a packet arriving from Host H1 to
Router R1 must be forwarded to the next router on a path to H2. As we will see,
forwarding is but one function (albeit the mostcommon and important one!) implemented
in the data plane. In the more general case, which we’ll cover, a packet might also be
blocked from exiting a router (for example, 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.
Routing. The network layer must determine the route or path taken by packets as
they flow from a sender to a receiver. The algorithms that calculate these paths are
referred to as routing algorithms. A routing algorithm would determine, for example, the
path along which packets flow from H1 to H2. Routing is implemented in the control
plane of the network layer.
The terms forwarding and routing are often used interchangeably by authors
discussing the network layer. We’ll use these terms much more precisely in this book.
Forwarding refers to the router-local action of transferring a packet from an input link
interface to the appropriate output link interface. Forwarding takes place at very short
timescales (typically a few nanoseconds), and thus is typically implemented in hardware.
Routing refers to the network-wide process that determines the end-to-end paths that
packets take from source to destination. Routing takes place on much longer timescales
(typically seconds), and as we will see is often implemented in software. Using our
driving analogy, consider the trip from Pennsylvania to Florida undertaken by our
traveler. During this trip, our driver passes through many interchanges en route to
Florida. We can think of forwarding as the process of getting through a single
interchange: A car enters the interchange from one road and determines which road it
should take to leave the interchange. We can think of routing as the process of planning
the trip from Pennsylvania to Florida: Before embarking on the trip, the driver has
consulted a map and chosen one of many paths possible, with each path consisting of a
series of road segments connected at interchanges.
A key element in every network router is its forwarding table. A router forwards a
packet by examining the value of one or more fields in the arriving packet’s header, and
then using these header values to index into its forwarding table. The value stored in the
forwarding table entry for those values indicates the outgoing link interface at that router
to which that packet is to be forwarded. For example, a packet with header field value of
0110 arrives to a router. The router indexes into its forwarding table and determines that
the output link interface for this packet is interface 2. The router then internally forwards
the packet to interface, we’ll look inside a router and examine the forwarding function in
much greater detail. Forwarding is the key function performed by the data-plane
functionality of the network layer.
But now you are undoubtedly wondering how a router’s forwarding tables are
configured in the first place. This is a crucial issue, one that exposes the important
interplay between forwarding (in data plane) and routing (in control plane), the routing
algorithm determines the contents of the routers’ forwarding tables. In this example, a
routing algorithm runs in each and every router and both forwarding and routing
functions are contained within a router, the routing algorithm function in one router
communicates with the routing algorithm function in other routers to compute the values
for its forwarding table. How is this communication performed? By exchanging routing
messages containing routing information according to a routing protocol! We’ll cover
routing algorithms and protocols.
The distinct and different purposes of the forwardand routing functions can be
further illustrated by considering the hypothetical (and unrealistic, but technically
feasible) case of a network in which all forwarding tables are configured directly by
human network operators physically present at the routers. In this case, no routing
protocols would be required! Of course, the human operators would need to interact with
each other to ensure that the forwarding tables were configured in such a way that
packets reached their intended destinations. It’s also likely that human configuration
would be more error-prone and much slower to respond to changes in the network
topology than a routing protocol. We’re thus fortunate that all networks have both a
forwarding and a routing function!
The approach to implementing routing functionality —with each router having a
routing component that communicates with the routing component of other routers—has
been the traditional approach adopted by routing vendors in their products, at least until
recently. Our observation that humans could manually configure forwarding tables does
suggest, however, that there may be other ways for control plane functionality to
determine the contents of the data-plane forwarding tables.
Before delving into the network layer’s data plane, let’s wrap up our introduction
by taking the broader view and consider the different types of service that might be
offered by the network layer. When the transport layer at a sending host transmits a
packet into the network (that is, passes it down to the network layer at the sending host),
can the transport layer rely on the network layer to deliver the packet to the destination?
When multiple packets are sent, will they be delivered to the transport layer in the
receiving host in the order in which they were sent? Will the amount of time between the
sending of two sequential packet transmissions be the same as the amount of time
between their reception? Will the network provide any feedback about congestion in the
network? The answers to these questions and others are determined by the service model
provided by the network layer. The network service model defines the characteristics of
end-to-end delivery of packets between sending and receiving hosts.
The Internet’s network layer provides a single service, known as best-effort
service. With best-effort service, packets are neither guaranteed to be received in the
order in which they were sent, nor is their eventual delivery even guaranteed. There is no
guarantee on the end-to-end delay nor is there a minimal bandwidth guarantee. It might
appear that best-effort service is a euphemism for no service at all—a network that
delivered no packets to the destination would satisfy the definition of best-effort delivery
service! Other network architectures have defined and implemented service models that
go beyond the Internet’s best-effort service. For example, the ATM network architecture
[Black 1995] provides for guaranteed in-order delay, bounded delay, and guaranteed
minimal bandwidth. There have also been proposed service model extensions to the
Internet architecture; for example, the Intserv architecture [RFC 1633] aims to provide
end-end delay guarantees and congestion-free communication. Interestingly, in spite of
these well-developed alternatives, the Internet’s basic best-effort service model combined
with adequate bandwidth provisioning and bandwidth-adaptive application-level
protocols such as the DASH protocol we encountered have arguably proven to be more
than “good enough” to enable an amazing range of applications, including streaming
video services such as Netflix and video-over-IP, real-time conferencing applications
such as Skype and Facetime.
b. What’s Inside a Router?
Now that we’ve overviewed the data and control planes within the network layer,
the important distinction between forwarding and routing, and the services and functions
of the network layer, let’s turn our attention to its forwarding function—the actual
transfer of packets from a router’s incoming links to the appropriate outgoing links at that
router.
Input ports. An input port performs several key functions. It performs the physical
layer function of terminating an incoming physical link at a router; this is shown in the
leftmost box of an input port and the rightmost box of an output port. An input port also
performs link-layer functions needed to interoperate with the link layer at the other side
of the incoming link; this is represented by the middle boxes in the input and output
ports. Perhaps most crucially, a lookup function is also performed at the input port; this
will occur in the rightmost box of the input port. It is here that the forwarding table is
consulted to determine the router output port to which an arriving packet will be
forwarded via the switching fabric. Control packets (for example, packets carrying
routing protocol information) are forwarded from an input port to the routing processor.
Note that the term “port” here—referring to the physical input and output router
interfaces—is distinctly different from the software ports associated with network
applications and sockets. In practice, 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, where the number of incoming lines tends to be the greatest. The
Juniper MX2020, edge router, for example, supports up to 800 100 Gbps Ethernet ports,
with an overall router system capacity of 800 Tbps [Juniper MX 2020 2020].
Switching fabric. The switching fabric connects the router’s input ports to its
output ports. This switching fabric is completely contained within the router—a network
inside of a network router! 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. When a link is bidirectional (that is,
carries traffic in both directions), an output port will typically be paired with the input
port for that link on the same line card.
Routing processor. The routing processor performs control-plane functions. In
traditional routers, it executes the routing protocols, maintains routing tables and attached
link state information, 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 (among other activities) receive forwarding table entries computed by the remote
controller, and install these entries in the router’s input ports.
A router’s input ports, output ports, and switching fabric are almost always
implemented in hardware. To appreciate why a hardware implementation is needed,
consider that with a 100 Gbps input link and a 64-byte IP datagram, the input port has
only 5.12 ns to process the datagram before another datagram may arrive. If N ports are
combined on a line card (as is often done in practice), the datagram-processing pipeline
must operate N times faster—far toofast for software implementation. Forwarding
hardware can be implemented either using a router vendor’s own hardware designs, or
constructed using purchased merchant-silicon chips.
While the data plane operates at the nanosecond time scale, a router’s control
functions—executing the routing protocols, responding to attached links that go up or
down, communicating with the remote controller (in the SDN case) and performing
management functions—operate at the millisecond or second timescale. These control
plane functions are thus usually implemented in software and execute on the routing
processor (typically a traditional CPU). Before delving into the details of router internals,
let’s return to our analogy from the beginning of this, where packet forwarding was
compared to cars entering and leaving an interchange. Let’s suppose that the interchange
is a roundabout, and that as a car enters the roundabout, a bit of processing is required.
Destination-based forwarding. Suppose the car stops at an entry station and
indicates its final destination (not at the local roundabout, but the ultimate destination of
its journey). An attendant at the entry station looks up the final destination, determines
the roundabout exit that leads to that final destination, and tells the driver which
roundabout exit to take.
Generalized forwarding. The attendant could also determine the car’s exit ramp
on the basis of many other factors besides the destination. For example, the selected exit
ramp might depend on the car’s origin, for example the state that issued the car’s license
plate. Cars from a certain set of states might be directed to use one exit ramp (that leads
to the destination via a slow road), while cars from other states might be directed to use a
different exit ramp (that leads to the destination via superhighway). The same decision
might be made based on the model, make and year of the car. Or a car not deemed
roadworthy might be blocked and not be allowed to pass through the roundabout. In the
case of generalized forwarding, any number of factors may contribute to the attendant’s
choice of the exit ramp for a given car.
We can easily recognize the principal router components in this analogy—the
entry road and entry station correspond to the input port (with a lookup function to
determine to local outgoing port); the roundabout corresponds to the switch fabric; and
the roundabout exit road corresponds to the output port. With this analogy, it’s instructive
to consider where bottlenecks might occur. What happens if cars arrive blazingly fast (for
example, the roundabout is in Germany or Italy!) but the station attendant is slow? How
fast must the attendant work to ensure there’s no backup on an entry road? Even with a
blazingly fast attendant, what happens if carstraverse the roundabout slowly—can
backups still occur? And what happens if most of the cars entering at all of the
roundabout’s entrance ramps all want to leave the roundabout at the same exit ramp—can
backups occur at the exit ramp or elsewhere? How should the roundabout operate if we
want to assign priorities to different cars, or block certain cars from entering the
roundabout in the first place? These are all analogous to critical questions faced by router
and switch designers.
As just discussed, the input port’s line-termination function and link-layer
processing implement the physical and link layers for that individual input link. The
lookup performed in the input port is central to the router’s operation—it is here that the
router uses the forwarding table to look up the output port to which an arriving packet
will be forwarded via the switching fabric. The forwarding table is either computed and
updated by the routing processor (using a routing protocol to interact with the routing
processors in other network routers) or is received from a remote SDN controller. The
forwarding table is copied from the routing processor to the line cards over a separate bus
(e.g., a PCI bus) indicated by the dashed line from the routing processor to the input line
cards. With such a shadow copy at each line card, forwarding decisions can be made
locally, at each input port, without invoking the centralized routing processor on a per-
packet basis and thus avoiding a centralized processing bottleneck.
Let’s now consider the “simplest” case that the output port to which an incoming
packet is to be switched is based on the packet’s destination address. In the case of 32-bit
IP addresses, a brute-force implementation of the forwarding table would have one entry
for every possible destination address. Since there are more than 4 billion possible
addresses, this option is totally out of the question.
Given the existence of a forwarding table, lookup is conceptually simple—
hardware logic just searches through the forwarding table looking for the longest prefix
match. But at Gigabit transmission rates, this lookup must be performed in nanoseconds
(recall our earlier example of a 10 Gbps link and a 64-byte IP datagram). Thus, not only
must lookup be performed in hardware, but techniques beyond a simple linear search
through a large table are needed; surveys of fast lookup algorithms can be found in
[Gupta 2001, Ruiz-Sanchez 2001]. Special attention must also be paid to memory access
times, resulting in designs with embedded on-chip DRAM and faster SRAM (used as a
DRAM cache) memories. In practice, Ternary Content Addressable Memories (TCAMs)
are also often used for lookup [Yu 2004]. With a TCAM, a 32-bit IP address is presented
to the memory, which returns the content of the forwarding table entry for that address in
essentially constant time. The Cisco Catalyst 6500 and 7600 Series routers and switches
can hold upwards of a million TCAM forwarding table entries [Cisco TCAM 2014].
Once a packet’s output port has been determined via the lookup, the packet can be
sent into the switching fabric. In some designs, a packet may be temporarily blocked
from entering the switching fabric if packets from other input ports are currently using
the fabric. A blocked packet will be queued at the input port and then scheduled to cross
the fabric at a later point in time. We’ll take a closer look at the blocking, queuing, and
scheduling of packets (at both input ports and output ports) shortly. Although “lookup” is
arguably the most important action in input port processing, many other actions must be
taken: (1) physical- and link-layer processing must occur, as discussed previously; (2) the
packet’s version number, checksum and time-to-live field—must be checked and the
latter two fields rewritten; and (3) counters used for network management (such as the
number of IP datagrams received) must be updated.
Let’s close our discussion of input port processing by noting that the input port
steps of looking up a destination IP address (“match”) and then sending the packet into
the switching fabric to the specified output port (“action”) is a specific case of a more
general “match plus action” abstraction that is performed in many networked devices, not
just routers. In link-layer switches, link-layer destination addresses are looked up and
several actions may be taken in addition to sending the frame into the switching fabric
towards the output port. In firewalls—devices that filter out selected incoming packets—
an incoming packet whose header matches a given criteria (e.g., a combination of
source/destination IP addresses and transport-layer port numbers) may be dropped
(action). In a network address translator, an incoming packet whose transport-layer port
number matches a given value will have its port number rewritten before forwarding
(action). Indeed, the “match plus action” abstraction [Bosshart 2013] is both powerful
and prevalent in network devices today, and is central to the notion of generalized.
Switching via memory. The simplest, earliest routers were traditional computers,
with switching between input and output ports being done under direct control of the
CPU (routing processor). Input and output ports functioned as traditional I/O devices in a
traditional operating system. An input port with an arriving packet first signaled the
routing processor via an interrupt. The packet was then copied from the input port into
processor memory. The routing processor then extracted the destination address from the
header, looked up the appropriate output port in the forwarding table, and copied the
packet to the output port’s buffers. In this scenario, if the memory bandwidth is such that
a maximum of B packets per second can be written into, or read from, memory, then the
overall forwarding throughput (the total rate at which packets are transferred from input
ports to output ports) must be less than B/2. Note also that two packets cannot be
forwardedat the same time, even if they have different destination ports, since only one
memory read/write can be done at a time over the shared system bus. Some modern
routers switch via memory. A major difference from early routers, however, is that the
lookup of the destination address and the storing of the packet into the appropriate
memory location are performed by processing on the input line cards. In some ways,
routers that switch via memory look very much like sharedmemory multiprocessors, with
the processing on a line card switching (writing) packets into the memory of the
appropriate output port. Cisco’s Catalyst 8500 series switches [Cisco 8500 2020]
internally switches packets via a shared memory.
Switching via a bus. In this approach, an input port transfers a packet directly to
the output port over a shared bus, without intervention by the routing processor. This is
typically done by having the input port pre-pend a switch-internal label (header) to the
packet indicating the local output port to which this packet is being transferred and
transmitting the packet onto the bus. All output ports receive the packet, but only the port
that matches the label will keep the packet. The label is then removed at the output port,
as this label is only used within the switch to cross the bus. If multiple packets arrive to
the router at the same time, each at a different input port, all but one must wait since only
one packet can cross the bus at a time. Because every packet must cross the single bus,
the switching speed of the router is limited to the bus speed; in our roundabout analogy,
this is as if the roundabout could only contain one car at a time. Nonetheless, switching
via a bus is often sufficient for routers that operate in small local area and enterprise
networks. The Cisco 6500 router [Cisco 6500 2020] internally switches packets over a
32-Gbps-backplane bus.
Switching via an interconnection network. One way to overcome the bandwidth
limitation of a single, shared bus is to use a more sophisticated interconnection network,
such as those that have been used in the past to interconnect processors in a
multiprocessor computer architecture. A crossbar switch is an interconnection network
consisting of 2N buses that connect N input ports to N output ports. Each vertical bus
intersects each horizontal bus at a crosspoint, which can be opened or closed at any time
by the switch fabric controller (whose logic is part of the switching fabric itself). When a
packet arrives from port A and needs to be forwarded to port Y, the switch controller
closes the crosspoint at the intersection of busses A and Y, and port A then sends the
packet onto its bus, which is picked up (only) by bus Y. Note that a packet from port B
can be forwarded to port X at the same time, since the A-to-Y and B-to-X packets use
different input and output busses.
Thus, unlike the previous two switching approaches, crossbar switches are
capable of forwarding multiple packets in parallel. A crossbar switch is non-blocking—a
packet being forwarded to an output port will not be blocked from reaching that output
port as long as no other packet is currently being forwarded to that output port. However,
if two packets from two different input ports are destined to that same output port, then
one will have to wait at the input, since only one packet can be sent over any given bus at
a time. Cisco 12000 seriesswitches [Cisco 12000 2020] use a crossbar switching network;
the Cisco 7600 series can be configured to use either a bus or crossbar switch [Cisco
7600 2020].
More sophisticated interconnection networks use multiple stages of switching
elements to allow packets from different input ports to proceed towards the same output
port at the same time through the multi-stage switching fabric. See [Tobagi 1990] for a
survey of switch architectures. The Cisco CRS employs a three-stage non-blocking
switching strategy. A router’s switching capacity can also be scaled by running multiple
switching fabrics in parallel. In this approach, input ports and output ports are connected
to N switching fabrics that operate in parallel. An input port breaks a packet into K
smaller chunks, and sends (“sprays”) the chunks through K of these N switching fabrics
to the selected output port, which reassembles the K chunks back into the original packet.
If we consider input and output port functionality and the configurations shown,
it’s clear that packet queues may form at both the input ports and the output ports, just as
we identified cases where cars may wait at the inputs and outputs of the traffic
intersection in our roundabout analogy. The location and extent of queueing (either at the
input port queues or the output port queues) will depend on the traffic load, the relative
speed of the switching fabric, and the line speed. Let’s now consider these queues in a bit
more detail, since 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. Recall that in our earlier discussions, we said that packets were “lost within the
network” or “dropped at a router.” It is here, at these queues within a router, where such
packets are actually dropped and lost.
Let’s now return to the question of determining the order in which queued packets
are transmitted over an outgoing link. Since you yourself have undoubtedly had to wait in
long lines on many occasions and observed how waiting customers are served, you’re no
doubt familiar with many of the queueing disciplines commonly used in routers. There is
first-come-first-served (FCFS, also known as first-in-first-out, FIFO). The British are
famous for patient and orderly FCFS queueing at bus stops and in the marketplace (“Oh,
are you queueing?”). Other countries operate on a priority basis, with one class of waiting
customers given priority service over other waiting customers. There is also round-robin
queueing, where customers are again divided into classes (as in priority queueing) but
each class of customer is given service in turn.
c. The Internet Protocol (IP): IPv4, Addressing, IPv6, and More
Recall that the Internet’s network-layer packet is referred to as a datagram. We
begin our study of IP with an overview of the syntax and semantics of the IPv4 datagram.
You might be thinking that nothing could be drier than the syntax and semantics of a
packet’s bits. Nevertheless, the datagram plays a central role in the Internet—every
networking student and professional needs to see it, absorb it, and master it. (And just to
see that protocol headers can indeed be fun to study, check out [Pomeranz 2010]).
Type of service. The type of service (TOS) bits were included in the IPv4 header
to allow different types of IP datagrams to be distinguished from each other. For
example, it might be useful to distinguish real-time datagrams (such as those used by an
IP telephony application) from non-real-time traffic (e.g., FTP). The specific level of
service to be provided is a policy issue determined and configured by the network
administrator for that router.
Identifier, flags, fragmentation offset. These three fields have to do with so-called
IP fragmentation, when a large IP datagram is broken into several smaller IP datagrams
which are then forwarded independently to the destination, where they are reassembled
before their payload data (see below) is passed up to the transport layer at the destination
host. Interestingly, the new version of IP, IPv6, does not allow for fragmentation. We’ll
not cover fragmentation here; but readers can find a detailed discussion online, among the
“retired” material from earlier versions of this book.
Protocol. This field is typically used only when an IP datagram reaches its final
destination. The value of this field indicates the specific transport-layer protocol to which
the data portion of this IP datagram should be passed. For example, a value of 6 indicates
that the data portion is passed to TCP, while a value of 17 indicates that the data is passed
to UDP. For a list of all possible values, see [IANA Protocol Numbers 2016]. Note that
the protocol number in the IP datagram has a role that is analogous to the role of the port
number field in the transport-layer segment. The protocol number is the glue that binds
the network and transport layers together, whereas the port number is the glue that binds
the transport and application layers together.
Header checksum. The header checksum aids a router in detecting bit errors in a
received IP datagram. The header checksum is computed by treating each 2 bytes in the
header as a number and summing these numbers using 1s complement arithmetic. As
discussed , the 1s complement of this sum, known as the Internet checksum, is stored in
the checksum field. A router computes the header checksum for each received IP
datagram and detects an error condition ifthe checksum carried in the datagram header
does not equal the computed checksum. Routers typically discard datagrams for which an
error has been detected. Note that the checksum must be recomputed and stored again at
each router, since the TTL field, and possibly the options field as well, will change. An
interesting discussion of fast algorithms for computing the Internet checksum is [RFC
1071]. A question often asked at this point is, why does TCP/IP perform error checking at
both the transport and network layers? There are several reasons for this repetition. First,
note that only the IP header is check summed at the IP layer, while the TCP/ UDP
checksum is computed over the entire TCP/UDP segment. Second, TCP/ UDP and IP do
not necessarily both have to belong to the same protocol stack. TCP can, in principle, run
over a different network-layer protocol (for example, ATM) [Black 1995]) and IP can
carry data that will not be passed to TCP/UDP.
Options. The options fields allow an IP header to be extended. Header options
were meant to be used rarely—hence the decision to save overhead by not including the
information in options fields in every datagram header. However, the mere existence of
options does complicate matters—since datagram headers can be of variable length, one
cannot determine a priori where the data field will start. Also, since some datagrams may
require options processing and others may not, the amount of time needed to process an
IP datagram at a router can vary greatly. These considerations become particularly
important for IP processing in high performance routers and hosts.
Data (payload). Finally, we come to the last and most important field—the raison
d’etre for the datagram in the first place! In most circumstances, the data field of the IP
datagram contains the transport-layer segment (TCP or UDP) to be delivered to the
destination. However, the data field can carry other types of data, such as ICMP
messages. Note that an IP datagram has a total of 20 bytes of header (assuming no
options). If the datagram carries a TCP segment, then each datagram carries a total of 40
bytes of header (20 bytes of IP header plus 20 bytes of TCP header) along with the
application-layer message.
We now turn our attention to IPv4 addressing. Although you may be thinking that
addressing must be a straightforward topic, hopefully by the end of this section you’ll be
convinced that Internet addressing is not only a juicy, subtle, and interesting topicbut also
one that is of central importance to the Internet. An excellent treatment of IPv4
addressing can be found in the first in [Stewart 1999].
Before discussing IP addressing, however, we’ll need to say a few words about
how hosts and routers are connected into the Internet. A host typically has only a single
link into the network; when IP in the host wants to send a datagram, it does so over this
link. The boundary between the host and the physical link is called an interface. Now
consider a router and its interfaces. Because a router’s job is to receive a datagram on one
link and forward the datagram on some other link, a router necessarily has two or more
links to which it is connected. The boundary between the router and any one of its links is
also called an interface. A router thus has multiple interfaces, one for each of its links.
Because every host and router is capable of sending and receiving IP datagrams, IP
requires each host and router interface to have its own IP address. Thus, an IP address is
technically associated with an interface, rather than with the host or router containing that
interface.
The IP definition of a subnet is not restricted to Ethernet segments that connect
multiple hosts to a router interface. To get some insight here, consider, which shows three
routers that are interconnected with each other by point-to-point links. Each router has
three interfaces, one for each point-to-point link and one for the broadcast link that
directly connects the router to a pair of hosts. What subnets are present here? Three
subnets, 223.1.1.0/24, 223.1.2.0/24, and 223.1.3.0/24, are similar to the subnets we
encountered. But note that there are three additional subnets in this example as well: one
subnet, 223.1.9.0/24, for the interfaces that connect routers R1 and R2; another subnet,
223.1.8.0/24, for the interfaces that connect routers R2 and R3; and a third subnet,
223.1.7.0/24, for the interfaces that connect routers R3 and R1.
From the discussion above, it’s clear that an organization (such as a company or
academic institution) with multiple Ethernet segments and point-to-point links will have
multiple subnets, with all of the devices on a given subnet having the same subnet
address. In principle, the different subnets could have quite different subnet addresses. In
practice, however, their subnet addresses often have much in common. To understand
why, let’s next turn our attention to how addressing is handled in the global Internet. The
Internet’s address assignment strategy is known as Classless Interdomain Routing (CIDR
—pronounced cider) [RFC 4632]. CIDR generalizes the notion of subnet addressing. As
with subnet addressing, the 32-bit IP address is divided into two parts and again has the
dotted-decimal form a.b.c.d/x, where x indicates the number of bits in the first part of the
address.
The x most significant bits of an address of the form a.b.c.d/x constitute the
network portion of the IP address, and are often referred to as the prefix (or network
prefix) of the address. An organization is typically assigned a block of contiguous
addresses, that is, a range of addresses with a common prefix (see the Principles in
Practice feature). In this case, the IP addresses of devices within the organization will
share the common prefix. When we cover the Internet’s BGP routing protocol in, we’ll
see that only these x leading prefix bits are considered by routers outside the
organization’s network. That is, when a router outside the organization forwards a
datagram whose destination address is inside the organization, only the leading x bits of
the address need be considered. This considerably reduces the size of the forwarding
table in these routers, since a single entry of the form a.b.c.d/x will be sufficient to
forward packets to any destination within the organization.
The remaining 32-x bits of an address can be thought of as distinguishing among
the devices within the organization, all of which have the same network prefix. These are
the bits that will be considered when forwarding packets at routers within the
organization. These lower-order bits may (or may not) have an additional subnetting
structure, such as that discussed above. For example, suppose the first 21 bits of the
CIDRized address a.b.c.d/21 specify the organization’s network prefix and are common
to the IP addresses of all devices in that organization. The remaining 11 bits then identify
the specific hosts in the organization. The organization’s internal structure might be such
that these 11 rightmost bits are used for subnetting within the organization, as discussed
above. For example, a.b.c.d/24 might refer to a specific subnet within the organization.
Before CIDR was adopted, the network portions of an IP address were
constrained to be 8, 16, or 24 bits in length, an addressing scheme known as classful
addressing, since subnets with 8-, 16-, and 24-bit subnet addresses were known as class
A, B, and C networks, respectively. The requirement that the subnet portion of an IP
address be exactly 1, 2, or 3 bytes long turned out to be problematic for supporting the
rapidly growing number of organizations with small and medium-sized subnets. A class
C (/24) subnet could accommodate only up to 28 2 2 5 254 hosts (two of the 28 5 256
addresses are reserved for special use)—too small for many organizations. However, a
class B (/16) subnet, which supports up to 65,634 hosts, was too large. Under classful
addressing, an organization with, say, 2,000 hosts was typically allocated a class B (/16)
subnet address. This led to a rapid depletion of the class B address space and poor
utilization of the assigned address space. For example, the organization that used a class
B address for its 2,000 hosts was allocated enough of the address space for up to 65,534
interfaces—leaving more than 63,000 addresses that could not be used by other
organizations.
d. Generalized Forwarding and SDN
Recall that characterized destination-based forwarding as the two steps of looking
up a destination IP address (“match”), then sending the packet into the switching fabric to
the specified output port (“action”). Let’s now consider a significantly more general
“match-plus-action” paradigm, where the “match” can be made over multiple header
fields associated with different protocols at different layers in the protocol stack. The
“action” can include forwarding the packet to one or more output ports (as in destination-
based forwarding), load balancing packets across multiple outgoing interfaces that lead to
a service (as in load balancing), rewriting header values (as in NAT), purposefully
blocking/dropping a packet (as in a firewall), sending a packet to a special server for
further processing and action (as in DPI), and more.
In generalized forwarding, a match-plus-action table generalizes the notion of the
destination-based forwarding table that we encountered. Because forwarding decisions
may be made using network-layer and/or link-layer source and destination addresses, the
forwarding devices are more accurately described as “packet switches” rather than layer 3
“routers” or layer 2 “switches.” Thus, in the remainder of this section, we’ll refer to these
devices as packet switches, adopting the terminology that is gaining widespread adoption
in SDN literature.
Our following discussion of generalized forwarding will be based on OpenFlow
[McKeown 2008, ONF 2020, Casado 2014, Tourrilhes 2014]—a highly visible standard
that has pioneered the notion of the match-plus-action forwarding abstraction and
controllers, as well as the SDN revolution more generally [Feamster 2013]. We’ll
primarily consider OpenFlow 1.0, which introduced key SDN abstractions and
functionality in a particularly clear and concise manner. Later versions of OpenFlow
introduced additional capabilities as a result of experience gained throughmplementation
and use; current and earlier versions of the OpenFlow standard can be found at [ONF
2020].
A set of header field values to which an incoming packet will be matched. As in
the case of destination-based forwarding, hardware-based matching is most rapidly
performed in TCAM memory, with more than a million destination address entries being
possible [Bosshart 2013]. A packet that matches no flow table entry can be dropped or
sent to the remote controller for more processing. In practice, a flow table may be
implemented by multiple flow tables for performance or cost reasons [Bosshart 2013],
but we’ll focus here on the abstraction of a single flow table.
. Recall from that a link-layer (layer 2) frame arriving to a packet switch will
contain a network-layer (layer 3) datagram as its payload, which in turn will typically
contain a transport-layer (layer 4) segment. The first observation we make is that
OpenFlow’s match abstraction allows for a match to be made on selected fields from
three layers of protocol headers. Since we’ve not yet covered the link layer, suffice it to
say that the source and destination MAC addresses are the link-layer addresses
associated with the frame’s sending and receiving interfaces; by forwarding on the basis
of Ethernet addresses rather than IP addresses, we can see that an OpenFlow-enabled
device can equally performas a router (layer-3 device) forwarding datagrams as well as a
switch (layer-2 device) forwarding frames. 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 so-called virtual local area networks that we. The set
of 12 values that can be matched in the OpenFlow 1.0 specification has grown to 41
values in more recent OpenFlow specifications [Bosshart 2014].
Having now considered both the match and action components of generalized
forwarding, let’s put these ideas together in the context of the sample network. The
network has 6 hosts (h1, h2, h3, h4, h5 and h6) and three packet switches (s1, s2 and s3),
each with four local interface. We’ll consider a number of network-wide behaviors that
we’d like to implement, and the flow table entries in s1, s2 and s3 needed to implement
this behavior.
e. Routing Algorithms
In this section, we’ll study routing algorithms, whose goal is to determine good
paths (equivalently, routes), from senders to receivers, through the network of routers.
Typically, a “good” path is one that has the least cost. We’ll see that in practice, however,
real-world concerns such as policy issues (for example, a rule such as “router x,
belonging to organization Y, should not forward any packets originating from the
network owned by organization Z ”) also come into play. We note that whether the
network control plane adopts a per-router control approach or a logically centralized
approach, there must always be a well-defined sequence of routers that a packet will
cross in traveling from sending to receiving host. Thus, the routing algorithms that
compute these paths are of fundamental importance, and another candidate for our top-10
list of fundamentally important networking concepts.
A graph is used to formulate routing problems. Recall that a graph G = (N, E) is a
set N of nodes and a collection E of edges, where each edge is a pair of nodes from N. In
the context of network-layer routing, the nodes in the graph representrouters—the points
at which packet-forwarding decisions are made—and the edges connecting these nodes
represent the physical links between these routers. Such a graph abstraction of a computer
network. When we study the BGP inter-domain routing protocol, we’ll see that nodes
represent networks, and the edge connecting two such nodes represents direction
connectivity (know as peering) between the two networks. To view some graphs
representing real network maps, see [CAIDA 2020]; for a discussion of how well
different graph-based models model the Internet, see [Zegura 1997, Faloutsos 1999, Li
2004].
Typically, an edge’s cost may reflect the physical length of the corresponding link
(for example, a transoceanic link might have a higher cost than a short-haul terrestrial
link), the link speed, or the monetary cost associated with a link. For our purposes, we’ll
simply take the edge costs as a given and won’t worry about how they are determined.
For any edge (x, y) in E, we denote c(x, y) as the cost of the edge between nodes x and y.
If the pair (x, y) does not belong to E, we set c(x, y) = ∞. Also, we’ll only consider
undirected graphs (i.e., graphs whose edges do not have a direction) in our discussion
here, so that edge (x, y) is the same as edge (y, x) and that c(x, y) = c(y, x); however, the
algorithms we’ll study can be easily extended to the case of directed links with a different
cost in each direction. Also, a node y is said to be a neighbor of node x if (x, y) belongs to
E.
Given that costs are assigned to the various edges in the graph abstraction, a
natural goal of a routing algorithm is to identify the least costly paths between sources
and destinations. To make this problem more precise, recall that a path in a graph G = (N,
E) is a sequence of nodes (x1, x2, g, xp) such that each of the pairs (x1, x2), (x2, x3), g,
(xp-1, xp) are edges in E. The cost of a path (x1, x2, g, xp) is simply the sum of all the
edge costs along the path, that is, c(x1, x2) + c(x2, x3) + g+ c(xp-1, xp). Given any two
nodes x and y, there are typically many paths between the two nodes, with each path
having a cost. One or more of these paths is a least-cost path. The least-cost problem is
therefore clear: Find a path between the source and destination that has least cost, for
example, the least-cost path between source node u and destination node w is (u, x, y, w)
with a path cost of 3. Note that if all edges in the graph have the same cost, the least cost
path is also the shortest path (that is, the path with the smallest number of links between
the source and the destination).
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. This then
requires that the algorithm somehow obtain this information before actually performing
the calculation. The calculation itself can be run at one site or could be replicated in the
routing component of each and every router. The key distinguishing feature here,
however, is that the algorithm has complete information about connectivity and link
costs. Algorithms with global state information are often referred to as link-state (LS)
algorithms, since the algorithm must be aware of the cost of each link in the network.
In a decentralized routing algorithm, the calculation of the least-cost path is
carried out in an iterative, distributed manner by the routers. No node has complete
information about the costs of all network links. Instead, 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 or set of destinations. The
decentralized routing algorithm we’ll study below is called a distance-vector (DV)
algorithm, because each node maintains a vector of estimates of the costs (distances) to
all other nodes in the network. Such decentralized algorithms, with interactive message
exchange between neighboring routers is perhaps more naturally suited to control planes
where the routers interact directly with each other.
Recall that in a link-state algorithm, the network topology and all link costs are
known, that is, available as input to the LS algorithm. In practice, this is accomplished by
having each node broadcast link-state packets to all other nodes in the network, with each
link-state packet containing the identities and costs of its attached links. In practice (for
example, with the Internet’s OSPF routing protocol, this is often accomplished by a link-
state broadcast algorithm [Perlman 1999]. The result of the nodes’ broadcast is that all
nodes have an identical and complete view of the network. Each node can then run the
LS algorithm and compute the same set of least-cost paths as every other node.
The link-state routing algorithm we present below is known as Dijkstra’s
algorithm, named after its inventor. A closely related algorithm is Prim’s algorithm; see
[Cormen 2001] for a general discussion of graph algorithms. Dijkstra’s algorithm
computes the least-cost path from one node (the source, which we will refer to as u) to all
other nodes in the network. Dijkstra’s algorithm is iterative and has the property that after
the kth iteration of the algorithm, the least-cost paths are known to k destination nodes,
and among the least-cost paths to all destination nodes, these k paths will have the k
smallest costs.
What is the computational complexity of this algorithm? That is, given n nodes
(not counting the source), how much computation must be done in the worst case to find
the least-cost paths from the source to all destinations? In the first iteration, we need to
search through all n nodes to determine the node, w, not in N′ that has the minimum cost.
In the second iteration, we need to check n - 1 nodes to determine the minimum cost; in
the third iteration n - 2 nodes, and so on. Overall, the total number of nodes we need to
search through over all the iterations is n(n + 1)/2, and thus we say that the preceding
implementation of the LS algorithm has worst-case complexity of order n squared:
O(n2 ). (A more sophisticated implementation of this algorithm, using a data structure
known as a heap, can find the minimum in line 9 in logarithmic rather than linear time,
thus reducing the complexity.)
Whereas the LS algorithm is an algorithm using global information, the
distancevector (DV) algorithm is iterative, asynchronous, and distributed. It is distributed
in that each node receives some information from one or more of its directly attached
neighbors, performs a calculation, and then distributes the results of its calculation back
to its neighbors. It is iterative in that this process continues on until no more information
is exchanged between neighbors. (Interestingly, the algorithm is also self-terminating—
there is no signal that the computation should stop; it just stops.) The algorithm is
asynchronous in that it does not require all of the nodes to operate in lockstep with each
other. We’ll see that an asynchronous, iterative, self-terminating, distributed algorithm is
much more interesting and fun than a centralized algorithm!
f. Intra-AS Routing in the Internet: OSPF
In our study of routing algorithms so far, we’ve viewed the network simply as a
collection of interconnected routers. One router was indistinguishable from another in the
sense that all routers executed the same routing algorithm to compute routing paths
through the entire network.
Scale. As the number of routers becomes large, the overhead involved in
communicating, computing, and storing routing information becomes prohibitive.
Today’s Internet consists of hundreds of millions of routers. Storing routing information
for possible destinations at each of these routers would clearly require enormous amounts
of memory. The overhead required to broadcast connectivity and link cost updates among
all of the routers would be huge! A distance-vector algorithm that iterated among such a
large number of routers would surely never converge. Clearly, something must be done to
reduce the complexity of route computation in a network as large as the Internet.
Administrative autonomy. The Internet is a network of ISPs, with each ISP
consisting of its own network of routers. An ISP generally desires to operate its network
as it pleases (for example, to run whatever routing algorithm it chooses within its
network) or to hide aspects of its network’s internal organization from the outside.
Ideally, an organization should be able to operate and administer its network as it wishes,
while still being able to connect its network to other outside networks.
Both of these problems can be solved by organizing routers into autonomous
systems (ASs), with each AS consisting of a group of routers that are under the same
administrative control. Often the routers in an ISP, and the links that interconnect them,
constitute a single AS. Some ISPs, however, partition their network into multiple ASs. In
particular, some tier-1 ISPs use one gigantic AS for their entire network, whereas others
break up their ISP into tens of interconnected ASs. An autonomous system is identified
by its globally unique autonomous system number (ASN) [RFC 1930]. AS numbers, like
IP addresses, are assigned by ICANN regional registries [ICANN 2020].
OSPF routing and its closely related cousin, IS-IS, are widely used for intra-AS
routing in the Internet. The Open in OSPF indicates that the routing protocol specification
is publicly available (for example, as opposed to Cisco’s EIGRP protocol, which was
only recently became open [Savage 2015], after roughly 20 years as a Cisco-proprietary
protocol). The most recent version of OSPF, version 2, is defined in [RFC 2328], a public
document.
Setting OSPF Weights). The administrator might choose to set all link costs to 1,
thus achieving minimum-hop routing, or might choose to set the link weights to be
inversely proportional to link capacity in order to discourage traffic from using low-
bandwidth links. OSPF does not mandate a policy for how link weights are set (that is the
job of the network administrator), but instead provides the mechanisms (protocol) for
determining least-cost path routing for the given set of link weights.
With OSPF, a router broadcasts routing information to all other routers in the
autonomous system, not just to its neighboring routers. A router broadcasts link-state
information whenever there is a change in a link’s state (for example, a change in cost or
a change in up/down status). It also broadcasts a link’s state periodically (at least once
every 30 minutes), even if the link’s state has not changed. RFC 2328 notes that “this
periodic updating of link state advertisements adds robustness to the link state
algorithm.” OSPF advertisements are contained in OSPF messages that arecarried
directly by IP, with an upper-layer protocol of 89 for OSPF. Thus, the OSPF protocol
must itself implement functionality such as reliable message transfer and link-state
broadcast.
g. Routing Among the ISPs: BGP
We just learned that OSPF is an example of an intra-AS routing protocol. When
routing a packet between a source and destination within the same AS, the route the
packet follows is entirely determined by the intra-AS routing protocol. However, to route
a packet across multiple ASs, say from a smartphone in Timbuktu to a server in a
datacenter in Silicon Valley, we need an inter-autonomous system routing protocol. Since
an inter-AS routing protocol involves coordination among multiple ASs, communicating
ASs must run the same inter-AS routing protocol. In fact, in the Internet, all ASs run the
same inter-AS routing protocol, called the Border Gateway Protocol, more commonly
known as BGP [RFC 4271; Stewart 1999].
BGP is arguably the most important of all the Internet protocols (the only other
contender would be the IP protocol that we studied, as it is the protocol that glues the
thousands of ISPs in the Internet together. As we will soon see, BGP is a decentralized
and asynchronous protocol in the vein of distance-vector routing described. Although
BGP is a complex and challenging protocol, to understand the Internet on a deep level,
we need to become familiar with its underpinnings and operation. The time we devote to
learning BGP will be well worth the effort.
To understand the responsibilities of BGP, consider an AS and an arbitrary router
in that AS. Recall that every router has a forwarding table, which plays the central role in
the process of forwarding arriving packets to outbound router links. As we have learned,
for destinations that are within the same AS, the entries in the router’s forwarding table
are determined by the AS’s intra-AS routing protocol. But what about destinations that
are outside of the AS? This is precisely where BGP comes to the rescue.
As we can see, this simple network has three autonomous systems: AS1, AS2,
and AS3. As shown, AS3 includes a subnet with prefix x. For each AS, each router is
either a gateway router or an internal router. A gateway router is a router on the edge of
an AS that directly connects to one or more routers in other ASs. An internal router
connects only to hosts and routers within its own AS. In AS1, for example, router 1c is a
gateway router; routers 1a, 1b, and 1d are internal routers.
Let’s consider the task of advertising reachability information for prefix x to all of
the routers. At a high level, this is straightforward. First, AS3 sends a BGP message to
AS2, saying that x exists and is in AS3; let’s denote this message as “AS3 x”. Then AS2
sends a BGP message to AS1, saying that x exists and that you can get to x by first
passing through AS2 and then going to AS3; let’s denote that message as “AS2 AS3 x”.
In this manner, each of the autonomous systems will not only learn about the existence of
x, but also learn about a path of autonomous systems that leads to x.
Although the discussion in the above paragraph about advertising BGP
reachability information should get the general idea across, it is not precise in the sense
that autonomous systems do not actually send messages to each other, but instead routers
do. In BGP pairs of routers exchange routing information over semi-permanent TCP
connections using port 179. Each such TCP connection, along with all the BGP messages
sent over the connection, is called a BGP connection. Furthermore, a BGP connection
that spans two ASs is called an external BGP (eBGP) connection, and a BGP session
between routers in the same AS is called an internal BGP (iBGP) connection. Examples
of BGP connections for the network. There is typically one eBGP connection for each
link that directly connects gateway routers in different ASs; thus, there is an eBGP
connection between gateway routers 1c and 2a and an eBGP connection between gateway
routers 2c and 3a.
h. The SDN Control Plane
In this section, we’ll dive into the SDN control plane—the network-wide logic
that controls packet forwarding among a network’s SDN-enabled devices, as well as the
configuration and management of these devices and their services. Our study here builds
on our earlier discussion of generalized SDN forwarding in, so you might want to first
review that section, before continuing on. We’ll again adopt the terminology used in the
SDN literature and refer to the network’s forwarding devices as “packet switches” (or
just switches, with “packet” being understood), since forwarding decisions can be made
on the basis of network-layer source/destination addresses, link-layer source/destination
addresses, as well as many other values in transport-, network-, and link-layer packet-
header fields.
A programmable network. The network is programmable through the network
control applications running in the control plane. These applications represent the
“brains” of the SDN control plane, using the APIs provided by the SDN controller to
specify and control the data plane in the network devices. For example, a routing
network-control application might determine the end-end paths between sources and
destinations (for example, by executing Dijkstra’s algorithm using the node state and
link-state information maintained by the SDN controller). Another network application
might perform access control, that is, determine which packets are to be blocked at a
switch, as in our third. Yet another application might have switches forward packets in a
manner that performs server load balancing.
From this discussion, we can see that 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. This contrasts with the pre-SDN model in which a switch/router (together
with its embedded control plane software and protocol implementations) was monolithic,
vertically integrated, and sold by a single vendor. 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; one hope for SDN is
that it will continue to drive and enable such rich innovation.
Given our understanding of the SDN architecture of, many questions naturally
arise. How and where are the flow tables actually computed? How are these tables
updated in response to events at SDN-controlled devices (e.g., an attached link going
up/down)? And how are the flow table entries at multiple switches coordinated in such a
way as to result in orchestrated and consistent network-wide functionality (e.g., end-to-
end paths for forwarding packets from sources to destinations, or coordinated distributed
firewalls)? It is the role of the SDN control plane to provide these, and many other,
capabilities.
