Introduction to Network Routing and Switching

So far in this course we have studied techniques to engineer a point-to-point communication link. Two important considerations were at the heart of most everything we studied:
1.
Improving link communication reliability:
Inter-symbol interference (ISI) and noise con-
spired to introduce errors in transmission. We developed techniques to select a suit-
able sampling rate and method using
eye diagrams
and then reduced the bit-error rate
using
channel coding
(block, Reed-Solomon, and convolutional codes).
2.
Sharing a link:
We wanted to share the same communication medium amongst
k
different receivers, each tuned to a different frequency. To achieve this goal, we used
digital modulation
, and learned that understanding the frequency response of an LTI
system and designing filters are key building blocks for this task.
We now turn to the study of communication networks—systems that connect three or
more computers (or phones)
1
together.
The key idea that we will use to engineer communication networks is
composition
: we
will build small networks by composing links together, and build larger networks by com-
posing smaller networks together.
The fundamental challenges in the design of a communication network are the same
as those that face the designer of a communication link:
sharing
and
reliability
. The big
difference is that the sharing problem is considerably more challenging, and many more
things can go wrong in networking
2
many computers together, making communication
more unreliable than a single link’s unreliability. The next few lectures will show you these
challenges and you will understand the key ideas in how these challenges are overcome.
In addition to sharing and reliability, an important and difficult problem that many
communication networks (such as the Internet) face is
scalability
: how to engineer a very
large, global system. We won’t say very much about scalability in this course, leaving this
important issue to future courses in EECS.
1
The distinction between a phone and a computer is rapidly vanishing, so the difference is rather artificial.
2
As one wag put it: “Networking, just one letter away from not working.” the links, the switches themselves have some resources (memory and computation) that
will be shared by all the communicating computers.
Figure
15-2
shows the general idea. A switch receives bits that are encapsulated in
data frames
(in some networks, these are called
packets
, as explained below) arriving over
its links, processes them (in a way that we will make precise later), and forwards them
(again, in a way that we will make precise later) over one or more other links.
We will use the term
end points
to refer to the communicating computers, and call the
switches and links over which they communicate the
network infrastructure
. The resulting
structure is termed the
network topology
, and consists of
nodes
(the switches and end points)
and links. A simple network topology is shown in Figure
15-2
. We will model the network
topology as a
graph
to solve various problems.
Figure
15-3
show a few switches of relatively current vintage (ca. 2006).
￿
15.1.1  Three Problems That Switches Solve
The fundamental functions performed by switches are to multiplex and demultiplex data
frames belonging to different computer-to-computer information transfer sessions, and to
determine the link(s) along which to forward any given data frame. This task is essen-
tial because a given physical link will usually be shared by several concurrent sessions
between different computers. We break these functions into three problems:
1.
Forwarding:
When a data frame arrives at a switch, the switch needs to process it,
determine the correct outgoing link, and decide when to send the frame on that link.
2.
Routing:
Each switch somehow needs to determine the topology of the network,
so that it can correctly construct the data structures required for proper forwarding.
The process by which the switches in a network collaboratively compute the network
topology, adapting to various kinds of failures, is called routing. It does not happen
on each data frame, but occurs in the “background”.
3.
Resource allocation:
Switches allocate their resources—access to the link and local
memory—to the different communications that are in progress.