YT YouTube2Text

YouTube2Text → Transcripts → 4.2 What's inside a router? Part 1.

4.2 What's inside a router? Part 1. — Transcript

by JimKurose · 2,366 words · 359 segments · language en · Watch on YouTube

Open in transcriber Summarize with AI Download SRT/VTT

Full transcript

0:00[Music]
0:09having over viewed the network layers
0:12data and control planes and
0:14understanding the difference between
0:16routing and forwarding we're ready to
0:18now dive down deeply into the forwarding
0:21function in the network layer that is
0:23how our packets move from a routers
0:25input port to the appropriate output
0:28port and there's going to be a lot of
0:30ground to cover here and so we're going
0:31to do this in two parts in the first
0:33part we're going to look at a generic
0:35router architecture to look at the input
0:37ports the output ports and the switching
0:40fabric for moving data grams from input
0:42to output in the second part we're gonna
0:45dive down deeply into the issues of
0:47packet scheduling and packet buffering
0:50tremendously important topics so it's a
0:53lot to cover here so let's get started
0:55the figure that will be developing here
0:57shows the major components of router
0:59architecture let's start with the input
1:02and output ports this is where the
1:04physical and the link layers are
1:05implemented the link layer and physical
1:08layer might be wired Ethernet optical
1:10fiber or some kind of wireless
1:12technology and of course keep parts of
1:14the network layer are also implemented
1:17in the input and output ports the number
1:20of ports in a router can vary from very
1:22small say half a dozen in a home router
1:24to many hundreds of interfaces ports in
1:27a backbone router each operating at many
1:29gigabits per second packets are moved
1:32from the input ports to the output ports
1:34under router control through a switching
1:36fabric and this really is the heart of a
1:39router this is the place to which all
1:40packets must pass and as we'll see it's
1:43really a network within a network router
1:45a router also has a routing processor
1:48often just a regular CPU that performs
1:52control plane functions controls the
1:53switch fabric and installs forwarding
1:56tables at the input ports as shown here
1:58on this diagram we can also pretty
2:01clearly distinguish the router
2:03components that belong to the data plane
2:05that operate at high speed and are
2:07implemented in hardware in the control
2:09plane which is implemented in software
2:11and running it's slower timescales
2:16let's now zoom in on the input port and
2:19starting from the left let's see what we
2:20see here shown in green here we see a
2:23line termination function this is really
2:25the physical layer it's responsible for
2:27receiving the bit level transmissions
2:29over the physical medium whether it be
2:31copper fiber or Wireless then there's
2:34the link layer function shown in blue
2:36here where bits are assembled into link
2:38layer frames like the Ethernet frames
2:40that will study later and finally shown
2:43in red here there's the network layer
2:45functions at the input port PACA queues
2:48may form here we'll cover that shortly
2:50but for now the thing to remember is
2:52that the most critical network layer
2:54function performed at the input port is
2:56the lookup and forwarding function
2:59determining the appropriate output port
3:01to which the arriving packet will be
3:03forwarded through the switching fabric
3:05this lookup and forwarding is a type of
3:08match plus action behavior in
3:11traditional routers the destination
3:13address in the packets header that is
3:16the IP address of the destination host
3:18is going to determine the appropriate
3:20output port to which the packet will be
3:23forwarded or directed through the
3:25switching fabric and we'll take a look
3:27at that in just a second a little bit
3:29after that we'll take a look at
3:30generalized forwarding where the
3:32appropriate output port is determined or
3:34can be determined by many fields in the
3:37network layer header the link layer
3:38frame header or the transport layer
3:40segment header for example it's possible
3:43under generalized forwarding for packets
3:45a containing TCP segments bound for a
3:48particular destination and say coming
3:50from a particular source host to be
3:53directed to one output port but have
3:55packets say containing UDP segments from
3:57that source IP address to be directed to
4:00a different output port or maybe not to
4:02be forwarded at all but we're getting
4:05ahead of ourselves here so let's get
4:07started with destination based
4:08forwarding what you see here is a simple
4:12example of a forwarding table and when
4:14we think about forwarding tables the
4:16first thing to consider is well there
4:18are 2 to the 32 almost 4 billion
4:21possible destination addresses
4:24we certainly don't want a routing table
4:26entry for each possible destination
4:28address so it probably won't surprise
4:30you that routing table entries are often
4:33aggregated into ranges as we see here in
4:36this particular example any packet with
4:39a destination address in this first
4:41range of destination addresses goes to
4:44output port or interfaces zero packets
4:47with a destination address and the
4:49second address range going to interface
4:51one and in this third address range
4:53going to interface two and otherwise the
4:56default outgoing interface is going to
4:58be interface three in this example well
5:02this all works out pretty nicely and
5:04looks pretty simple but of course the
5:06devil is in the details as the saying
5:08goes what happens for example when say
5:11packets with a destination address and
5:13some subset of addresses in this first
5:16range should go to interface three
5:18rather than interface zero well of
5:22course we could split the first address
5:24range into multiple pieces and then add
5:27in this new sub range with its new
5:29destination output port but it turns out
5:32there's a much more simple and more
5:34elegant way to do this and this is known
5:36as longest prefix matching well longest
5:41prefix matching is relatively simple
5:43instead of using explicit ranges to
5:46perform matching as we saw in the
5:48previous slide we want to work with
5:50address prefixes as shown here here
5:53we've got a table with four entries the
5:55link to the first prefix here is 21 bits
5:571 1 0 0 1 0 0 0 0 0 0 1 0 1 1 1 0 0 0 1
6:060 that's 21 bits the length of the
6:08second prefix is 24 bits so it's a
6:11longer prefix and the third prefix also
6:14has 21 bits the stars at the right
6:17they represent wildcards or sort of
6:19don't care bits they're not part of the
6:22prefix they represent the bits in the
6:24address range if you will and so you can
6:26see here that address ranges and
6:28prefixes really are the same things but
6:30as we'll see it's a lot easier to work
6:33with address prefixes rather than
6:35address ranges
6:36and the longest prefix matching rule
6:38works as follows for a 32 bit IP address
6:42to match a prefix all the leftmost bits
6:45each and every one of that address must
6:48match the ones and zeros in the prefix
6:51and among all of the prefixes that match
6:54we want to find the longest one the
6:56longest prefix match is sometimes also
6:58called the most specific match since the
7:01largest number of leftmost address bits
7:03are going to be matched take a look at
7:05the addresses here at the bottom can you
7:08figure out the prefixes to which they
7:10match under the longest prefix matching
7:12rule why don't you pause and think about
7:15that well the first example here only
7:19matches the prefix in the first row of
7:21the table so that's easy the second
7:23address those more interesting it's 21
7:26leftmost bits match this third table
7:28entry but its first 24 bits that's the
7:31second table entry the longest prefix
7:34matches thus the second table entry and
7:36a packet with this address would be
7:38forwarded to interface one associated
7:41with the second table injury rather than
7:43to interface two if you understand these
7:46examples you've definitely got the
7:48longest prefix matching rule down we'll
7:52see shortly that longest prefix matching
7:54dovetails really nicely and very
7:56naturally with Network addressing well
7:59as we mentioned earlier this match plus
8:02action is usually carried out in
8:03hardware the matching is often done
8:06using what are called ternary content
8:08addressable memories T Kam's where
8:11address is presented to the T cam and
8:13the matching values returned in one
8:15clock cycle regardless of table size T
8:18Cam's thus result in really really fast
8:20look ups once a packets appropriate
8:24output port has been determined by
8:26longest prefix matching the packets
8:28ready to be forwarded into the switching
8:30fabric let's take a look at what happens
8:32inside that switching fabric the
8:34switching fabric is at the very heart of
8:37a router it's job is to transfer a
8:39packet from the input side of the
8:41switching fabric to the output side of
8:43the switching fabric that is to move a
8:45packet from the input port to the output
8:48port that's been determined by the
8:49longest
8:50prefix match one of the most important
8:53characteristics of the switching fabric
8:54is its switching rate that is the
8:57maximum rate at which packets can be
8:59moved from an input port to an output
9:02port if there are n inputs with incoming
9:05rate R and the switch has a switching
9:07rate of n times R then all of the
9:09packets that arrive in some unit of time
9:11can be switched in their output ports
9:14during that much time in this case
9:16packets won't experience much of a
9:18significant weight on the input side of
9:20the switch this is known as a
9:22non-blocking switch but high speed non
9:25blocking switches are more expensive
9:27than switches that might say only
9:28occasionally block packets and force
9:30them to wait at the inputs and so not
9:33all routers have non-blocking switch
9:35fabrics if there's blocking then packets
9:38are going to have to wait their turn to
9:40be transferred through the switch fabric
9:42in these red boxes here on the input
9:44side of the switch fabric and this is
9:46known as input port queuing now the
9:49topic of how to build high speed
9:51efficient economical switching fabrics
9:54is itself a field study actually there
9:56are entire courses dedicated to this
9:58topic and so you might want to take one
10:00if you find this interesting so here
10:02we're only going to touch very lightly
10:04on this topic as shown here we can
10:08broadly identify three approaches
10:10towards switching switching via memory
10:12switching via bus and switching via an
10:16interconnection network and it's really
10:18this latter approach that's probably the
10:20most widely adopted in practice well way
10:23back in the day that's to say in the
10:251970s and 1980s the first routers were
10:28really pretty much traditional computers
10:31with switching between input and output
10:33ports being done under direct control of
10:36a CPU which you could sort of think of
10:38as a routing processor input and output
10:41ports functioned as traditional IO
10:43devices in a traditional operating
10:45system an input port with an arriving
10:48packet would signal the CPU via an
10:50interrupt the packet could then be
10:52copied from the input port buffers into
10:54processor memory the CPU would then use
10:57the destination address to look up the
10:59appropriate output port
11:01the output device in the forwarding
11:03table and then write that packets
11:05contents into the output devices buffers
11:08and so in many ways you can see the
11:10network ports were really just another
11:12type of i/o device rather than moving a
11:15packet from an input port to memory and
11:18then from memory to an output port
11:20switching via bus skips that
11:22intermediate transfer to memory and
11:25allows an input port to write the packet
11:27directly into the output port buffers
11:30this means a packet only has to cross
11:32the bus or the backplane once rather
11:34than twice and in this case the
11:37switching speed is limited to be the bus
11:39bandwidth the third type of switching
11:41fabric are interconnection networks and
11:43really these are the most interesting
11:45interconnection fabrics and routers
11:47share a lot in common with
11:49interconnection networks that have been
11:50used for decades to connect processors
11:53together in multiprocessor computing
11:55systems there are crossbar switches that
11:58directly connect in inputs and outputs
12:01through N squared interconnection points
12:04but more typically when connecting n
12:06inputs to n outputs multistage switching
12:09networks know generally as clost
12:11networks are used these multistage
12:14switching networks are made up by
12:16interconnecting smaller sized switch
12:19elements both serially that is in
12:21multiple linear stages and in parallel
12:24across a given stage in the example
12:26shown here and 8x8 switching network is
12:29made up of four four by four and four
12:32two by two smaller switches will seek
12:35lost networks again when we learn about
12:37how hosts are interconnected in data
12:39center networks because these switching
12:41fabrics have parallel paths from their
12:43input side to their output side we want
12:46to be able to leverage these paths in
12:48parallel and so it's common with these
12:50switching fabrics to divide a single
12:52data graham into multiple smaller fixed
12:55length units sometimes called cells and
12:57to switch these cells along parallel
13:00paths from the input to the output side
13:03of the switching fabric the original
13:05Datagram is then reassembled from those
13:07component cells that it was divided into
13:10at the output port after all the data
13:12grams pieces of a
13:16well so far we've thought of a switching
13:19fabric really is a single entity but as
13:22we just saw with interconnection
13:23networks parallelism can be exploited to
13:26build high-performance switches and this
13:29idea can be generalized to taking
13:30multiple switching fabric planes and
13:33using them in parallel as shown here in
13:36this diagram here is actually a
13:38schematic of Cisco's carrier routing
13:40system and has a basic unit with eight
13:42parallel switching planes each of which
13:45internally has a three-stage
13:47interconnection network as you can see
13:49by exploiting parallelism hundreds of
13:52terabytes of switching capacity can be
13:54achieved within a single router so that
13:58wraps up our first of two parts on
14:00what's inside a router we took a look a
14:02broad-brush view of what a router
14:04architecture looks like we saw the input
14:06ports switching fabrics and output ports
14:09and we looked at addressing in some
14:11detail what we're going to do next is
14:13we're going to dive down deep into the
14:15output ports in particular and take a
14:17look at packet buffering and packet
14:19scheduling
14:21[Music]
14:34[Music]

About this transcript

This page contains the full transcript of 4.2 What's inside a router? Part 1. by JimKurose, generated from the public captions YouTube serves with the video. The transcript has 2,366 words across 359 segments, with the original timestamps preserved so you can click any line to jump to that moment in the embedded player.

What you can do with it

Use the transcript to take notes, quote the speaker, build a study guide, generate a summary with ChatGPT or Claude via the YouTube Summary tool, or export it as a timed subtitle file with YouTube to SRT. You can also re-open it in the transcriber to translate the transcript into 100+ languages.

Free YouTube transcript tool

YouTube2Text is a free YouTube transcript generator — no signup, no daily limit. Paste any YouTube link and get the full transcript instantly, with timestamps, click-to-jump, translation to 100+ languages, AI prompts for ChatGPT, Claude, and Gemini, and exports to TXT, SRT, VTT, or Markdown.