4.2 What's inside a router? Part 1.

[Music] having over viewed the network layers data and control planes and understanding the difference between routing and forwarding we're ready to now dive down deeply into the forwarding function in the network layer that is how our packets move from a routers input port to the appropriate output port and there's going to be a lot of ground to cover here and so we're going to do this in two parts in the first part we're going to look at a generic router architecture to look at the input ports the output ports and the switching fabric for moving

data grams from input to output in the second part we're gonna dive down deeply into the issues of packet scheduling and packet buffering tremendously important topics so it's a lot to cover here so let's get started the figure that will be developing here shows the major components of router architecture let's start with the input and output ports this is where the physical and the link layers are implemented the link layer and physical layer might be wired Ethernet optical fiber or some kind of wireless technology and of course keep parts of the network layer are also

implemented in the input and output ports the number of ports in a router can vary from very small say half a dozen in a home router to many hundreds of interfaces ports in a backbone router each operating at many gigabits per second packets are moved from the input ports to the output ports under router control through a switching fabric and this really is the heart of a router this is the place to which all packets must pass and as we'll see it's really a network within a network router a router also has a routing processor

often just a regular CPU that performs control plane functions controls the switch fabric and installs forwarding tables at the input ports as shown here on this diagram we can also pretty clearly distinguish the router components that belong to the data plane that operate at high speed and are implemented in hardware in the control plane which is implemented in software and running it's slower timescales let's now zoom in on the input port and starting from the left let's see what we see here shown in green here we see a line termination function this is really the

physical layer it's responsible for receiving the bit level transmissions over the physical medium whether it be copper fiber or Wireless then there's the link layer function shown in blue here where bits are assembled into link layer frames like the Ethernet frames that will study later and finally shown in red here there's the network layer functions at the input port PACA queues may form here we'll cover that shortly but for now the thing to remember is that the most critical network layer function performed at the input port is the lookup and forwarding function determining the appropriate

output port to which the arriving packet will be forwarded through the switching fabric this lookup and forwarding is a type of match plus action behavior in traditional routers the destination address in the packets header that is the IP address of the destination host is going to determine the appropriate output port to which the packet will be forwarded or directed through the switching fabric and we'll take a look at that in just a second a little bit after that we'll take a look at generalized forwarding where the appropriate output port is determined or can be determined

by many fields in the network layer header the link layer frame header or the transport layer segment header for example it's possible under generalized forwarding for packets a containing TCP segments bound for a particular destination and say coming from a particular source host to be directed to one output port but have packets say containing UDP segments from that source IP address to be directed to a different output port or maybe not to be forwarded at all but we're getting ahead of ourselves here so let's get started with destination based forwarding what you see here is

a simple example of a forwarding table and when we think about forwarding tables the first thing to consider is well there are 2 to the 32 almost 4 billion possible destination addresses we certainly don't want a routing table entry for each possible destination address so it probably won't surprise you that routing table entries are often aggregated into ranges as we see here in this particular example any packet with a destination address in this first range of destination addresses goes to output port or interfaces zero packets with a destination address and the second address range going

to interface one and in this third address range going to interface two and otherwise the default outgoing interface is going to be interface three in this example well this all works out pretty nicely and looks pretty simple but of course the devil is in the details as the saying goes what happens for example when say packets with a destination address and some subset of addresses in this first range should go to interface three rather than interface zero well of course we could split the first address range into multiple pieces and then add in this new

sub range with its new destination output port but it turns out there's a much more simple and more elegant way to do this and this is known as longest prefix matching well longest prefix matching is relatively simple instead of using explicit ranges to perform matching as we saw in the previous slide we want to work with address prefixes as shown here here we've got a table with four entries the link to the first prefix here is 21 bits 1 1 0 0 1 0 0 0 0 0 0 1 0 1 1 1 0 0

0 1 0 that's 21 bits the length of the second prefix is 24 bits so it's a longer prefix and the third prefix also has 21 bits the stars at the right they represent wildcards or sort of don't care bits they're not part of the prefix they represent the bits in the address range if you will and so you can see here that address ranges and prefixes really are the same things but as we'll see it's a lot easier to work with address prefixes rather than address ranges and the longest prefix matching rule works as

follows for a 32 bit IP address to match a prefix all the leftmost bits each and every one of that address must match the ones and zeros in the prefix and among all of the prefixes that match we want to find the longest one the longest prefix match is sometimes also called the most specific match since the largest number of leftmost address bits are going to be matched take a look at the addresses here at the bottom can you figure out the prefixes to which they match under the longest prefix matching rule why don't you

pause and think about that well the first example here only matches the prefix in the first row of the table so that's easy the second address those more interesting it's 21 leftmost bits match this third table entry but its first 24 bits that's the second table entry the longest prefix matches thus the second table entry and a packet with this address would be forwarded to interface one associated with the second table injury rather than to interface two if you understand these examples you've definitely got the longest prefix matching rule down we'll see shortly that longest

prefix matching dovetails really nicely and very naturally with Network addressing well as we mentioned earlier this match plus action is usually carried out in hardware the matching is often done using what are called ternary content addressable memories T Kam's where address is presented to the T cam and the matching values returned in one clock cycle regardless of table size T Cam's thus result in really really fast look ups once a packets appropriate output port has been determined by longest prefix matching the packets ready to be forwarded into the switching fabric let's take a look at

what happens inside that switching fabric the switching fabric is at the very heart of a router it's job is to transfer a packet from the input side of the switching fabric to the output side of the switching fabric that is to move a packet from the input port to the output port that's been determined by the longest prefix match one of the most important characteristics of the switching fabric is its switching rate that is the maximum rate at which packets can be moved from an input port to an output port if there are n inputs

with incoming rate R and the switch has a switching rate of n times R then all of the packets that arrive in some unit of time can be switched in their output ports during that much time in this case packets won't experience much of a significant weight on the input side of the switch this is known as a non-blocking switch but high speed non blocking switches are more expensive than switches that might say only occasionally block packets and force them to wait at the inputs and so not all routers have non-blocking switch fabrics if there's

blocking then packets are going to have to wait their turn to be transferred through the switch fabric in these red boxes here on the input side of the switch fabric and this is known as input port queuing now the topic of how to build high speed efficient economical switching fabrics is itself a field study actually there are entire courses dedicated to this topic and so you might want to take one if you find this interesting so here we're only going to touch very lightly on this topic as shown here we can broadly identify three approaches

towards switching switching via memory switching via bus and switching via an interconnection network and it's really this latter approach that's probably the most widely adopted in practice well way back in the day that's to say in the 1970s and 1980s the first routers were really pretty much traditional computers with switching between input and output ports being done under direct control of a CPU which you could sort of think of as a routing processor input and output ports functioned as traditional IO devices in a traditional operating system an input port with an arriving packet would signal

the CPU via an interrupt the packet could then be copied from the input port buffers into processor memory the CPU would then use the destination address to look up the appropriate output port the output device in the forwarding table and then write that packets contents into the output devices buffers and so in many ways you can see the network ports were really just another type of i/o device rather than moving a packet from an input port to memory and then from memory to an output port switching via bus skips that intermediate transfer to memory and

allows an input port to write the packet directly into the output port buffers this means a packet only has to cross the bus or the backplane once rather than twice and in this case the switching speed is limited to be the bus bandwidth the third type of switching fabric are interconnection networks and really these are the most interesting interconnection fabrics and routers share a lot in common with interconnection networks that have been used for decades to connect processors together in multiprocessor computing systems there are crossbar switches that directly connect in inputs and outputs through N

squared interconnection points but more typically when connecting n inputs to n outputs multistage switching networks know generally as clost networks are used these multistage switching networks are made up by interconnecting smaller sized switch elements both serially that is in multiple linear stages and in parallel across a given stage in the example shown here and 8x8 switching network is made up of four four by four and four two by two smaller switches will seek lost networks again when we learn about how hosts are interconnected in data center networks because these switching fabrics have parallel paths from

their input side to their output side we want to be able to leverage these paths in parallel and so it's common with these switching fabrics to divide a single data graham into multiple smaller fixed length units sometimes called cells and to switch these cells along parallel paths from the input to the output side of the switching fabric the original Datagram is then reassembled from those component cells that it was divided into at the output port after all the data grams pieces of a well so far we've thought of a switching fabric really is a single

entity but as we just saw with interconnection networks parallelism can be exploited to build high-performance switches and this idea can be generalized to taking multiple switching fabric planes and using them in parallel as shown here in this diagram here is actually a schematic of Cisco's carrier routing system and has a basic unit with eight parallel switching planes each of which internally has a three-stage interconnection network as you can see by exploiting parallelism hundreds of terabytes of switching capacity can be achieved within a single router so that wraps up our first of two parts on what's

inside a router we took a look a broad-brush view of what a router architecture looks like we saw the input ports switching fabrics and output ports and we looked at addressing in some detail what we're going to do next is we're going to dive down deep into the output ports in particular and take a look at packet buffering and packet scheduling [Music] [Music]