1 of 59

CS 168, Summer 2025 @ UC Berkeley

Slides credit: Sylvia Ratnasamy, Rob Shakir, Peyrin Kao, Iuniana Oprescu

Link-State Protocols, IP Addressing

Lecture 6 (Routing 3)

4.1

4.2

4.3

4.4

4.5

4.6

2 of 59

Link-State Protocols

Lecture 6, CS 168, Summer 2025

Link-State Protocols

Overview
Computing Paths
Learning Graph Topology

IP Addressing

Hierarchical Addressing
Assigning Addresses
Writing Addresses
Aggregating Routes
IPv6 Changes

3 of 59

Routing Protocols – Roadmap

Routing protocols can be classified by:

Where they operate. (Intra-domain or inter-domain.)
How they operate. (Distance-vector, link-state, or path-vector.)

Today, we'll look at link-state protocols.

Very common as an Interior Gateway Protocol.
Major examples:

IS-IS (Intermediate System to Intermediate System).
OSPF (Open Shortest Path First).

	Intra-domain (Interior Gateway Protocol)	Inter-domain�(Exterior Gateway Protocol)
Distance-vector	RIP	–
Link-state	IS-IS, OSPF	–
Path-vector	–	BGP

so as a reminder there are lots of

0:32

different routing protocols out there the one we just saw was the distance Vector protocol and real life has a name

0:38

the routing information protocol so that's what we have written in this box

0:44

and today we'll be looking at a different set of protocols

and remember that if you have a routing protocol we

0:51

can classify it in one of two ways one way to classify it as where they operate do they operate within one network or

0:59

across different networks so we're still going to look at intradomain routing protocols that is protocols that work

1:06

inside a network today so we will not be going outside of the network until next time and the second classification we

1:13

can think of is how they operate what style of operation do they do to

1:19

exchange routes between routers last time we saw the distance Vector protocol this time we'll see some link State

1:25

protocols so we are in this box right here on the grid link state is how the protocol operates inter domain is where

1:32

it is operating these Protocols are often used as interior Gateway protocols for intra domain protocols for reasons

1:40

that we'll see soon as a spoiler it doesn't scale very well so it works best inside a specific domain and there are

1:48

two major examples in real life so we'll show you the conceptual version and it's implemented in one of these to actual

1:54

real life protocols

4 of 59

Link-State Protocols: Definition

Link-state protocols:

Every router learns the full network graph.
Then, each router runs a shortest-path algorithm on the graph to populate the forwarding table.

Distance-vector:

Local data: Each node only knows about part of the network.
Global (distributed) computation: Each node computes part of the solution, working with other nodes.

Link-state:

Global data: Each node knows about the full network graph.
Local computation: Each node computes the full solution by itself.

How do routers learn this?

What algorithm do we run?

so the link State protocols

2:00

actually relatively simple compared to its cousin the distance Vector protocol there's only two things you have to do

2:06

step one it's step two and you're done so the first step is have every router

2:11

learn the entire network graph this is different from distance Vector you're going to give every router a global

2:18

picture of what the network looks like and how you do that is an open question that will solve coming up and once every

2:25

router has the whole network graph in front of them they can just run their favorite shortest path algorithm to

2:31

populate the forwarding table if you know everything there is to know about the network you can just run your favorite shortest paths algorithm and

2:38

that will give you pass through the network so it's just two steps and we'll break them down coming up but before we

2:44

do I want to contrast distance vector and Link State protocols so in distance

2:49

Vector everyone had a little piece of the solution remember how each router didn't know the entire state of the

2:55

network they only knew advertisements coming in from their neighbors and that's all that they could use to build

3:01

their forwarding table so everyone only had little pieces of information about the network in link State protocols

3:07

we're instead going to give every node Global Information every router is going to know everything there is to know

3:13

about the network graph the other thing we can contrast is distance Vector ends

3:18

up Computing things globally and the way I think of that is every node confuses a

3:24

little piece of the solution and if you take everyone solution and put it all together you get a full solution to the

routing protocol so each person contributes a fraction and if you put it

3:35

together you get the whole by contrast in link State protocols each node will

3:41

compute the full Solution by itself so it's a little bit redundant but

3:46

everyone's going to get a copy of the full solution so that's the key difference distance Vector everyone has

3:51

little pieces that form a whole solution and Link State everyone has all the information and computes the entire

3:58

solution by themselves so with this High Lev picture we just have to solve the

4:04

questions of how to do step one how to do step two and that's it to this protocol

5 of 59

Global Data

Suppose R3 has learned the full network graph.

We know all the links, their status (up or down?), and their costs.
We know about all the destinations.

R3 can run a graph algorithm to compute paths.

We can populate the forwarding table with the next-hop (in the computed path).

R3's Table
Destination	Next Hop
A	R2
...	...

How do routers learn this?

What algorithm do we run?

econd one then we'll Circle back to the first one so

4:16

let's say somehow magically R3 has learned the entire network graph so that

4:22

means that you know all the links you know all the routers and who is up who is down you know all of their costs you

4:28

know all the hosts and their destinations and if that's the case then all you have to do is run a graph

4:34

algorithm like lra's algorithm or the bman for algorithm and that lets you

4:39

compute paths through the network so I guess this is an example of Link state in action so the first step is R3

4:46

somehow learns everything there is to know about this network and now that it knows the full picture that you and I

4:51

can see it can just run its favorite shortest paths algorithm dyra algorithm whatever else you like and it will

4:58

compute that the shortest path to a is this one in blue and if this is the shortest path to a that means that my

5:04

next top must be R2 because that's the next top along the shortest path that I

5:10

computed so these are the two steps step one step two and we have to answer these two questions and we are done

6 of 59

Computing Paths

Lecture 6, CS 168, Summer 2025

Link-State Protocols

Overview
Computing Paths
Learning Graph Topology

IP Addressing

Hierarchical Addressing
Assigning Addresses
Writing Addresses
Aggregating Routes
IPv6 Changes

7 of 59

Link-State Algorithms

What graph algorithm do we run to compute paths?

Any single source shortest-path algorithm will work.

Need to find shortest paths from a single source (the router) to every host.

Some possible choices:

Bellman-Ford (the original serial version).
Dijkstra's algorithm.
Breadth-first search.
Dynamic shortest path.
Approximate shortest path.
Parallel single-source shortest path.

8 of 59

Ensuring Consistency

Each router can only influence its next hop.

No guarantee that routers compute the same paths!

We have to ensure that every router is using a "compatible" approach.

R2 forwards to R3.

R3 forwards to R2.

one thing to notice though is even

6:45

though you compute the entire path to the host that is R3 with the full

6:51

picture of the network it computes the entire blue path you cannot influence what other routers do so even though you

6:58

compute this blue path you can't go to R1 and say hey your next top should be this link in blue it doesn't know you're

7:04

only responsible for your own forwarding table so even though you went through all the work of computing this blue path

7:11

the only piece of information that goes into your forwarding table is just my next top to a is R2 that's it you don't

7:19

need to store anything else you don't need to store the rest of the path you don't need to care about what R5 does

7:25

with the packet so even though you've done all the work of calculating the path the only part of the answer you

7:30

need and you can throw the rest away it's just the next top that's the only thing you as R3 have control over you

7:37

don't have control over what happens after R2 gets the packet and this

7:43

actually opens up a problem and the problem is that different routers might compute different paths so check out

7:49

this example where R3 armed with all the information about the network computes this blue path throws away all the

7:56

unnecessary information and just writes down that packets for a should be forwarded via

8:02

R2 and by contrast here we have R2 which also has a full picture of the network

8:08

and it also calculates path through the network and somehow it calculates that this red path is the shortest path to a

8:14

and it throws away the unnecessary information and just writes down that my next hop to a is

8:20

R3 wait a minute R3 is forwarding packets to R2 R2 is forwarding packets to R3 they have formed a routing Loop so

8:28

if we are not careful and different routers are being incompatible in some way it's possible

8:34

that link State protocols introduce unwanted routing Loops like we see here so somehow we need to make sure all the

8:41

routers are thinking about the same thing so that we avoid scenarios like

8:47

this

9 of 59

Ensuring Consistency

Requirements for routers to produce valid, compatible decisions:

Everyone agrees on the network topology.
Everyone is minimizing the same cost metric.
All costs are positive.
All routers use the same tie-breaking rules.

Routers don't necessarily need to use the same shortest-path algorithm, as long as they follow these rules.

In practice, easier to have everyone use the same algorithm.

so it turns out these four properties will allow routers to produce

8:53

valid compatible decisions which basically means everyone is Computing shortest paths and you don't provide

8:59

Loops or dead ends or other unwanted things so here are some things that you

9:04

need in order for that to be true one is everyone had better agree on what the network looks like if somehow router a

9:11

or router R1 has a different picture of the network than router R2 there's a link that R1 knows about but R2 doesn't

9:17

know about well that's a problem now they're going to compute different paths because they're using different input

9:22

graphs and that could cause routing Loops dead ends other things you don't want something else that hopefully is

9:28

true is that everyone is minimizing the same cost metric it'd be really bad if one of these links had cost five From

9:34

r3's perspective but from r2's perspective this link costs seven then they could have scenarios like this

9:40

where they compute different paths through the network as usual we want all costs to be positive because we don't

9:46

want loops and in case you're scared about ties you just have to make sure that everyone breaks ties the same not

9:52

something that's the most important here but you can imagine some edge cases where if you break ties one way and I

9:58

break ties other way we might create loops and that's not so good so it turns

10:04

out as long as you follow these rules and you make sure that all the routers are compatible in some way it's

10:09

technically okay if everyone uses slightly different algorithms for example if you use Spellman for I use

10:16

dkas we're probably going to get the same answer as long as we're using the same graph the same costs and so on and

10:22

so forth so it's probably okay if we use different algorithms but in practice it's just way easier to have all the

10:28

routers use the same algorithm so we don't have to worry about inconsistencies between various

10:34

algorithms so you can imagine if you're programming routers you would just put the same code in all the routers so

10 of 59

Learning Graph Topology

Lecture 6, CS 168, Summer 2025

Link-State Protocols

Overview
Computing Paths
Learning Graph Topology

IP Addressing

Hierarchical Addressing
Assigning Addresses
Writing Addresses
Aggregating Routes
IPv6 Changes

11 of 59

Steps of Learning Network Graph

Link-state protocols:

Every router learns the full network graph.

Step 1A: Discover my neighbors.
Step 1B: Tell everybody about my neighbors.

Then, each router runs a shortest-path algorithm on the graph to populate the forwarding table.

How do routers learn this?

12 of 59

Steps of Learning Network Graph (1/2) – Learn Neighbors

How do we discover who is adjacent to us and their identity? Say hello!

Routers periodically send hello messages to their neighbors.
If they stop saying hello, assume that they disappeared.
This helps us learn about our direct neighbors, but not the whole network.

R1 does not know about the rest of the network (e.g. R3).

Hello, I'm R2.

Hello, I'm R1.

Hello, I'm R3.

My neighbor is R2.

My neighbors are R1 and R3.

so let's see that in action and remember the ultimate goal is

11:19

for routers R1 R2 and R3 to learn about the full topology they want the picture

11:24

that we are seeing namely that they are connected in a chain so the first thing you should do is figure out who you are

11:30

directly connected to who's to my left who's to my right who are all the people who are one link away from me and that's

11:37

not so bad if you want to know who your neighbor is you just walk up to them and say hello that's the intuition so let's

11:43

do that R1 wakes up and it see it has one outgoing link that way so it's going

11:49

to send a hello packet that way don't know where it's going but we'll just say hello I'm R1 send along this particular

11:54

port and it'll eventually reach R2 R2 will also do the same thing it has two

12:00

links connected to it so it will send hello I am R2 out of both of those links

12:05

and then R3 will send hello I'm R3 out of its one and only link and if I finish this job and everyone exchanges H then

12:13

R1 now knows my neighbors R2 because I received a hello from R2 R2 knows that

12:18

its neighbors are R1 and R3 because it received hellos from R1 and R3 and R3

12:24

knows that his neighbor is R2 because it received a hello from R2 so it works pretty much like you'd expect and one

12:30

thing we do have to watch out for just like in distance Vector this is a best effort Network things can get dropped

12:37

and people can leave the network because topologies can change and we fix all of that using the same little trick we did

12:43

earlier which is the periodically send these hellos so send the same packet every five seconds if someone stopped

12:51

saying hello they probably left so that's our super simple way to guarantee

12:56

reliability and adapt to changing Networks one thing to notice though this helps

13:01

you learn your direct neighbors it does not help you learn indirect neighbors so for example R1 at this point it knows

13:08

that its neighbor is R2 but it does not know about people further in the network like R3 so we haven't solved that

13:14

problem yet but we'll do next

13 of 59

Steps of Learning Network Graph (2/2) – Propagate Neighbor Information

How do we learn about the rest of the network, beyond our neighbors?

Solution: Flood information across the network.
When local information changes, send it to everyone.
When you receive information from your neighbor, send it to everyone.

R1 and R2 are neighbors. Tell everyone!

so now let's do the Second Step the second step is to tell everyone else about your neighbor

13:29

relationships and the way that you'll do this is you'll Flood information across the network so you have a piece of

13:35

information that you care about namely that R1 and R2 are neighbors here's R1 here's R2 we are neighbors we learned

13:42

that from the previous step and since this is a useful piece of information that we want everybody to know remember

13:48

the ultimate goal is to get everyone a full picture of the network this is information that everyone wants to know

13:54

so what we do is we just flood it out of every link that we have I hypthetically if R1 had a bunch of links what it would

14:01

do is it would send this exact packet out of every single link tell the world that R1 and R2 are neighbors and if R2

14:08

hears the same thing it will also blast this information to everyone and if R3 hears this information it will also

14:14

blast it to everyone so by having this information propagate through the network anytime you hear a piece of

14:19

information that says please tell everyone this fact you send it to everyone you know all of your direct

14:25

neighbors if you repeat this enough times this piece of information should spread to everybody across the network

14:31

and that's sometimes called flooding so this one also works kind of like you'd expect any neighborly relationship that

14:38

you know about you your neighbor and you two are neighbors that's information that you want to tell everyone so you

14:44

flooded across the network and if everybody does this hopefully you end up learning all of the neighbor

14:50

relationships and that allows you to reconstruct the full Network graph

14 of 59

Avoiding Infinite Flooding

Flooding: When you receive an update, send it to everybody.

We have to be careful of the same update being sent repeatedly.

R5 and R9 are neighbors.

there is one we have to be really careful about and that's avoiding infinite flooding so let's take a look

15:04

at an example where flooding can go wrong so let's say R1 and R2 both have some piece of information it's from

15:10

somewhere else in the network I haven't shown where it's from but let's say that R1 knows that R5 and R9 are neighbors

15:16

that's a fact that everyone should know so R1 receives this information and sends it to everyone that is directly

15:23

connected to which includes R2 and R2 hears this information and says that's a piece of information that everyone

15:29

should know so I will also blast it out to all of my neighbors and then R1 gets this and blast it out to all of his

15:36

neighbors and r two gets it and blast it to all of his neighbors do you see the problem here this packet is going to get

15:41

forwarded back and forth between them forever and that's going to waste a lot of bandwidth and it's very pointless

15:48

given that they both know this information already so we have to avoid a problem like this and sometimes they

15:54

call it infinite flooding

15 of 59

Avoiding Infinite Flooding

Amplification: When there's a loop, copies of the same message get multiplied.

Does this animation make any sense or am I just hallucinating?

actually infinite flooding gets even worse if

16:43

there's a loop so this SL is a little bit hard to follow but it the idea hopefully is clear so let's say that R1

16:50

has a piece of information that it wants to tell everyone so it sends it to all of its neighbors R2 and R3 at this point

16:56

R2 has the information and must flood it R3 has the information and must flood so what does R2 do it floods it to both of

17:03

its neighbors what does R3 do it also floods it to both of its neighbors so if

17:08

you stare at this a little bit carefully what happened on this next time step is R1 got that message twice R2 and R3 R2

17:16

got the message from R3 R3 got the message from R2 so everyone has a copy of this message and they have to send it

17:23

out further so R1 got the message twice so it needs to blast it out once twice

17:28

R2 got the message once so it has to blast it at once R3 got the message once so it has to flood it once this is going

17:35

to blow up very quickly so now at this point from this green time step we can

17:40

see that R1 received the packet twice R2 received the packet once twice three

17:46

times and R3 received the packet once twice three times so if you receive

17:51

three of those packets you got to send it out three different times at least according to the protocol we've seen so far when you receive a piece of

17:57

information send it to all your neighbors so R1 sends out two copies R2

18:03

sends out three copies R3 sends out three copies this is blowing up very

18:08

quickly so when you have a loop in the topology like this what actually happens

18:14

is the packet gets Amplified one copy gets two copies which then blows up to

18:19

four copies and so on and so forth

16 of 59

Avoiding Infinite Flooding

Amplification: When there's a loop, copies of the same message get multiplied.

This edge means, R1 sends the message to R2.

Then, R2 sends it to R1, and so on.

if this picture doesn't make sense I tried to draw a different one so let me know

18:26

if this is better here's a picture where r one has the packet and it sends it to R2 and R3 so just for this slide only

18:33

I'm using links in a slightly different way this uh line means that R1 sent the

18:39

message to R2 it's not that R1 has a link to R2 although it does this is just R1 sending the packet to its neighbor so

18:46

then what does R2 do R2 sends the packet to R1 and R3 and R3 receives the packet sends it to R1 and R2 again this tree is

18:53

not a network it's just showing you who sends packets to whom so R3 sends a packet to one of two R2 sends a packet

19:00

to one and three when R1 receives the packet it sends to its neighbors when R3 sends it receives the packet it sends to

19:06

its neighbors when R1 receives the packet it sends to its neighbors when R2 receives the packet it sends to its

19:11

neighbors and this goes on for a very long time and you can see a single advertisement blowing up as it gets

19:18

forwarded around in a loop because of this amplification problem

19:27

does so

17 of 59

Avoiding Infinite Flooding

Problem: Naive solution (send to all neighbors) causes amplification.

Solution:

When local information (about yourself) changes, send it to all neighbors.
When you receive a packet from a neighbor, send it to all neighbors...
...unless you've already seen the packet before.

To identify packets you've seen before, add a timestamp.

Or some other unique identifier, e.g. strictly increasing sequence numbers.

✓ Seen it.

so the solution to this amplification and infinite flooding problem is to not send packets if you've

19:35

seen them before so if you receive a packet twice you should flood it the first time but don't flood it the second

19:42

time so that's that's all we got to do and if you go back to the loop topology and we try the same amplification trick

19:49

it's not going to work anymore if we only send a packet once so R1 has an

19:55

advertisement and it remembers I've seen this before now it sends out the advertisement to R2 and R3 R2 now has

20:01

seen it so it checks off the fact that it's seen this advertisement before and sends a copy to R1 and R3 and then R3

20:09

receives the advertisement from R1 says yeah I've seen it before and sends it to R1 nr2 and at this point because

20:16

everyone has seen it before they are not going to resend the advertisement again so all you have to do is just keep track

20:22

of advertisements that you have seen before if you've already seen them do not resend them because you will end up

20:28

doing infinite flooding and how do you keep track of packets that you've seen before you have to add some sort of

20:34

unique identifier for example maybe add a Tim stamp in the advertisements and say R2 and R3 are neighbors this message

20:42

was sent at this particular time and if you see that exact same message with the exact same timestamp don't send it a

20:49

second time or you can use sequence numbers or something else that uniquely identifies the

20:55

packets

18 of 59

Ensuring Reliability

The network is still best-effort. Updates could get dropped.

Recall: We need all routers to agree on topology, or else paths might be invalid.

Solution: Periodically re-send the update.

a couple more things we need to fix about link State before we're all done so we have avoided the infinite Loop problem uh and the infinite

21:37

advertisement problem one more thing we need to fix is that the network is best effort and updates can get dropped and

21:44

that would be bad because if updates get dropped people have different views of the topology and the paths might be

21:50

invalid so to fix this we play our usual trick of periodically resending advertisements one thing to note by the

21:57

way the checking of duplicate advertisements this avoids infinite flooding where a single advertisement

22:04

gets flooded forever but periodically you do have to reflood it so infinite

22:10

advertisements means that without any sort of time constraint you're just flooding this thing as fast as you possibly can creating tons and tons of

22:17

copies and adding a time stamp solves that but even with the time stamp you

22:22

still have to resend the update every five seconds or so so for example you might have an advertisement that says R5

22:29

and R9 are neighbors written at 6:30 pm and that gets flooded out and no one ref

22:35

floods it avoiding infinite looping but then at 6:35 five minutes later you have to restate that R5 and R9 are neighbors

22:42

you send that out that gets flooded all over again but you don't want to infinite flood any of them so no

22:48

individual advertisement should get Amplified and infinite looped or infinite advertised but you still have

22:56

to periodically resend them every couple of minutes

19 of 59

Ensuring Convergence

The network could change. What happens if a link goes down?

Wait for routers to detect the failure.
Wait to flood new information.
Wait to recompute paths.

While waiting for convergence, the routing state might be invalid.

Dead ends and loops. Packets using longer routes.

Link is down, but R1 doesn't know!

R1 forwards to R3.

R3 knows about the link failure!

R3 forwards to R1.

23:02

we'll quickly talk about convergence because remember that the network topology can change links can go down

23:09

new hosts can join they can leave and this can actually cause routes to temporarily be invalid it's kind of

23:15

similar to what you saw on the distance Vector protocol when something changes about the network the routing state

23:21

becomes invalid and we have to wait a little bit for the routing to converge again to a new valid state so when

23:27

something breaks everyone has to take some time to adjust to the failure and only after everyone

23:33

adjusts do we arrive at a new steady state and a new valid routing State and

23:38

that exact same pattern happens in link State protocols so for example let's say that the a to R3 link goes down and

23:46

let's say R3 knows about it but at this point R1 doesn't know about it yet maybe r1's further away and it hasn't heard

23:52

about the link going down yet so r1's picture is that all four links are valid

23:57

and in that case if it needs to compute the shortest path to a it might perhaps compute R1 R3 a the path in blue so

24:05

we'll forward packets to R3 by contrast R3 knows that the link has gone down

24:10

because it knows about that fact so it will instead using its full information

24:16

about the network compute this path in red and its next top will be R1 and we are once again in a loop R1 sends

24:23

packets to R3 R3 sends packets to R1 this will eventually get fixed once the

24:29

information about this dead link propagates to everyone else but for now it is not fixed and we have a routing

24:35

Loop until everyone reestablishes agreement of what the network graph looks like so this can happen sometimes

24:42

just like in the distance Vector protocol and we have to deal with

24:48

it so

20 of 59

Link-State vs. Distance-Vector

Link-state is relatively simple. All the complexity is in the details!

Everyone floods link/destination information.
Everyone has a global map of the network.
Everyone independently computes next-hops.

Why might we want to use link-state over distance-vector?

Link-state gives routers more control over the path they choose.

Distance-vector: We have to trust what our neighbor says, and we don't know the path they're using.

Link-state might be better at converging.

Distance-vector: Wait for neighbor to recompute and re-advertise path.
Link-state: Flood information before recomputing.

Real networks often use a combination of path/distance-vector and link-state.

so to quickly summarize link State versus dist inspector link State I would

24:53

say is probably the simpler of the two protocols if you think about how long it took us to explain one distance Vector

24:59

took like two hours to explain link state has taken 25 minutes in counting

25:05

so I think it's somewhat simpler there are some details though to make sure that it actually works and that you

25:11

don't run into bugs like infinite advertisements but at a very high level everyone floods the information that

25:17

they receive this gives everyone a global map of the network and everyone independently runs their own shortest

25:24

path algorithm to compute the next tops and to compare which which one is better

25:29

which one you might want to use here are some reasons why you might want to choose one over the other so one thing

25:35

that's nice about link state is that routers have a bit of control over the path that they choose so for example if

25:42

you really dislike R2 for some reason not sure why you would but if R1 thinks

25:47

I really hate R2 it can just send packets using R3 because it has a full picture of the network by contrast in

25:55

distance Vector you have to trust what your neighbor says if your neighbor says I can reach with path two but I can

26:01

reach a with cost two you have to trust what they say maybe they have a bug that

26:06

gets introduced and now you're stuck using incorrect information you don't know what path they're using so link

26:12

State because you have a global picture of the network you get a little bit more control over what path you want to

26:19

choose and compare with distance Vector where you receive advertisements from your neighbors you're not sure if

26:24

they're accurate or not you're not sure exactly what happens to the packet after the next top you just have to trust what

26:30

they say and pick whatever you think is best and arguably this one is kind of

26:35

debatable and depends on your network topology there are some cases where links made is a little bit better at

26:40

converging and the idea would be that in distance Vector the propagation involves computation at every single step so you

26:48

propagate information that a link has gone down you send poison and you have to wait a little bit for everyone to

26:54

compute and update their forwarding tables with a new poison and then they send out that that poison we have to

26:59

wait a little bit for all those routers to accept the poison change their forwarding tables and send out more

27:05

poison so there's a bit of computation and depending on how slow your routers are maybe that computation slows down

27:12

the propagation and by contrast in link State when something goes down that information can propagate faster because

27:18

you just say links down and the next router says oh links down let me tell my friends links down and they receive

27:26

links down message and they tell their friends so forth so they don't have to stop and compute things before they tell their neighbors

27:32

again not always true kind of depends on how fast your routers are at Computing New Paths but under certain assumptions

27:38

it could be the case that link state is a little bit more efficient in real life which do people use turns out it's often

27:45

a mixture of both some networks use one some networks use the other there are some protocols that sort of sit in the

27:50

middle between these two that you can use so you have a bit of a choice

21 of 59

Hierarchical Addressing

Lecture 6, CS 168, Summer 2025

Link-State Protocols

Overview
Computing Paths
Learning Graph Topology

IP Addressing

Hierarchical Addressing
Assigning Addresses
Writing Addresses
Aggregating Routes
IPv6 Changes

22 of 59

Scaling Routing

Can we really scale routing and forwarding to every host on the Internet?

Distance-vector: How many routing calculations does each router do?
Link-state: Can we really store the entire network graph in every router?
How long does it take to re-converge?

The secret to scaling routing is how we do addressing.

R3's Table
Destination	Port
A	0
B	1
C	1
D	2
...	...

One entry for every possible destination.

The trick: Use more informative names than A, B, C, D for destinations.

Disclaimer: Today is about IP (Layer 3) addresses. Other layers use different addressing systems.

so to motivate why we are doing this talking about

28:39

addressing let's think about the two protocols we've seen so far distance vector and linking and a question that

28:45

you have probably had as you've been watching this is how do you actually scale this stuff up to the entire

28:52

internet imagine trying to use Link State on the entire internet that's not going to be very fun

28:58

because how many calculations do you have to do you're receiving advertisements from your neighbors for every single destination on the internet

29:06

that's probably not going to be feasible and likewise link State scaling is even

29:11

worse you have to throw the entire network graph and that means that your computer has to store a list of all the

29:17

routers and all the hosts on the internet and all the links that's not happening either and imagine trying to

29:24

reconverge routes when we try to scale these protocols up if there's a link failure somewhere that has to propagate

29:30

outwards and outwards across the entire world who knows how long that's going to take so hopefully we can already see

29:36

that both of these protocols scale pretty poorly and if we actually try to implement these protocols at a global

29:43

level it would just not happen you can also see why this is annoying because if you look at the

29:49

table it has one entry per destination and if you have one destination or one

29:56

entry for every destination in the entire world this table is going to be billions of entries long there's no way

30:03

you're storing that and constantly keeping it updated so we need to fix

30:08

this and it turns out that the trick to actually make routing a scalable process

30:14

is the way that we assign these addresses so right now and so far we've been showing these destinations as a b c

30:21

d but it turns out if instead of ABCD you pick more informative names about

30:27

these destination and where they are you actually might be able to scale routing up more efficiently so by uncovering the

30:35

secrets behind why these are labeled ABCD and what they're really labeled in real life we just might be able to make

30:42

our routing protocols scale better and this is going to be useful because even though distance vector and Link State

30:48

work in local networks when we talk about bgp which works across many networks we are going to have to rely a

30:54

lot on this trick to help us scale routing up o we're seeing it now it can be applied to any protocol you want but

31:01

it's extremely useful when we talk about bgp because that's the one that connects the entire world together

23 of 59

Hierarchical Addressing – Conceptual

Recall: The Internet is a network of networks.

Leads naturally to a hierarchy of addresses.
Each network gets a number. Then, each host gets a number inside the network.

4.1

4.2

4.3

4.4

4.5

4.6

2.5

2.4

2.6

2.7

2.1

2.2

2.3

1.1

1.2

3.1

3.2

3.3

Network 2

Network 1

Network 3

Network 4

so the key here is to remember that the internet is a network of networks

31:16

remember each network has its own internal routing protocol its own settings whatever and then each Network

31:22

connects to each other to form this big network of networks so if that's the case this this actually already gives us

31:29

a very intuitive way to assign names to each of these end hosts so far we've

31:35

just been saying a CDE e FG but that didn't really tell us anything about host and where they are so maybe

31:42

something more intelligent to do is what if I gave each of these networks a number your network one your two and

31:48

your three and your four and now what I can do is inside of network one instead of calling these A and B or some

31:55

arbitrary number what if I called them 1.1 and 1.2 and the first one represents

32:02

the fact that they are in network one and network two gets numbers 2.1 2.2 2.3

32:09

all the way to 2.7 and maybe you see where this is going Network Three gets

32:14

addresses that start with three and network four gets addresses that start with four that seems like a pretty

32:20

natural way to assign numbers to these hosts so this is kind of what we're going to do but at a more at a bigger

32:28

scale so let's do it

24 of 59

Hierarchical Addressing – Conceptual

R9 can summarize all hosts in another network with a single table entry.

Huge scaling improvement! Tables are smaller now.

4.1

4.2

4.3

4.4

4.5

4.6

2.5

2.4

2.6

2.7

2.1

2.2

2.3

1.1

1.2

3.1

3.2

3.3

Network 2

Network 1

Network 3

Network 4

R9's Table
Destination	Next Hop
1.*	R6
3.*	R6
4.*	R8
...	...

so why is this useful by the way this is useful because

32:33

it allows us to summarize table entries so instead of having one table entry for

32:39

every single router or and every single end host sorry that you see on this graph we can actually summarize some

32:46

information so for example let's say you are R9 if we are doing this naively

32:51

you'd have to have an entry for 1.1 and 1.2 and 4.1 and 4.2 and 4.3 and 4. 4 4.5

32:58

4.6 you would need eight table entries to represent 1 2 3 4 5 six seven eight

33:04

end hosts but if you look at those table entries a lot of them say the same thing how do you get to 4.1 R8 how do you get

33:12

to 4.2 R8 how do you get to 4.3 also R8 it turns out the only way to get to

33:18

network 4 is via R8 or rather that is the shortest way to get to R4 so what we

33:23

can do is instead of writing one entry for 4.1 4.2 4 .3 and they all say that

33:29

the next toop is R8 you can just summarize this and say any destination that's 4 something and it doesn't matter

33:37

what that something is whatever it is the next top is R8 so you have summarized six entries into one and if

33:44

we play this trick enough times we can start to summarize and make our tables more scalable and we can play the same

33:50

trick over here instead of writing an entry for 1.1 and 1.2 both of which

33:56

would have a next toop of r we can just say if you want to reach one point anybody just send it to R six and

34:02

you're done and likewise instead of writing 3.1 3.2 3.3 we can see by

34:08

inspection that the next top is R six so you just say if you want to reach 3 point something go to R six I haven't

34:15

told you how to fill in this table yet you can imagine that this is the end goal is to have a table that's more

34:21

scalable like this and the higher archical addressing the fact that these

34:27

had two numbers in them is kind of what enabled this because we could say if the first number is three send it to R six

34:34

so the hierarchical addressing enabled this if the host had just said ABCD EFG

34:40

this would not have been possible

25 of 59

Hierarchical Addressing – Conceptual

Hierarchical addressing limits table churn.

Changes inside a network don't affect tables in other networks.

4.1

4.2

4.3

4.4

4.5

2.5

2.4

2.6

2.7

2.1

2.2

2.3

1.1

1.2

3.1

3.2

3.3

Network 2

Network 1

Network 3

Network 4

R9's Table
Destination	Next Hop
1.*	R6
3.*	R6
4.*	R8
...	...

4.6 left the network!

No change in table entry!

something else that's really

34:45

nice about Hier archol addressing is the fact that the tables change less often

34:51

sometimes people call this table churn so for example if host 4.6 leaves the

34:57

net Network and we were doing this naively and we had an entry for every single end host R9 would have to update

35:03

its table to indicate that 4.6 is gone and no longer reachable and if anyone

35:09

joins and leaves R9 has to update it table entry by contrast look at what

35:15

happens if we use aggregated table entries like this this table entry says if you need to reach 4 point something

35:21

go to R8 if 4.6 leaves the network do you have to change this entry

35:28

no it's still correct to reach 4. anything you still go via R8 so the fact that 4.6 left the network doesn't

35:35

require R9 to change its table entry at all the fact that everyone four point something is a link to R8 stays the same

35:44

so this is nice it means that changes in other networks for example if Network 4

35:50

has more people joining and leaving it doesn't affect R9 at all R9 just always keeps the same information of 4 point

35:57

something something go to R8 that's always true regardless of who joins and leaves Network for so this is nice it

36:04

means that tables change less often and changes in one network don't necessarily have to be propagated into the other one

26 of 59

Hierarchical Addressing – Conceptual

Size of the forwarding table scales with number of hosts in the current network, plus number of other networks.

Big scaling improvement! Much better than listing every single host.

Network 4

...

Network 2

R4's Table
Destination	Next Hop
2.1	R3
2.2	R3
2.3	R3
2.4	R3
2.5	R3
2.6	R5
2.7	R5
1.*	R9
3.*	R9
4.*	R9

2.1

2.2

2.3

2.5

2.4

2.6

2.7

Network 1

...

Internal destinations.

External destinations.

okay so to reiterate the point we just made about routers and the scaling

36:50

of their tables we can see that the size of the forwarding table now scales based

36:56

on two things so if you're R4 you are responsible for two sets of entries in

37:02

your table so some of your entries are about ways to get to hosts inside your

37:07

own network so R4 is in network 2 and because you're inside Network 2 you have

37:13

to keep track of different ways to reach 2.1 2.2 2.3 all the way to 2.7 you can

37:20

see that these are internal destinations and R4 has to keep separate entries for

37:25

every internal destination it has to remember if I want to go to 2.4 send it

37:31

to R3 but if I want to go to 2.7 send it to R5 so R4 needs to keep track of one

37:37

entry for every internal destination to other hosts inside the same network and

37:44

the second type of Entry that R2 or R4 needs to keep track of is external

37:49

destinations and these are the aggregated ones that we saw earlier so for example everyone in network one is a

37:56

long path the next top of R9 so if I want to send anything to someone who is 1 something I just send it to R9 and

38:04

they will take care of it likewise anyone in 4 point something or 3 point something not shown here all of them

38:11

have next cops of R9 so I have one entry per external destination so o overall in

38:18

this somewhat conceptual model we can see that you need one entry for every internal destination those cannot be

38:24

combined as of right now and then you need one for every external network and that's how these tables

38:31

scale but this is much better than listing every single host if you listed every single host you have to write 1.1

38:37

1.2 1.3 that's too much and

27 of 59

Implications of Hierarchical Addressing

Inter-domain routing computes routes between networks.

No need to think about churn inside networks.
Just think about network 1, network 2, etc.

Intra-domain routing computes routes inside a network.

No need to think about churn in other networks.
Just think about 2.1, 2.2, etc.

R4's Table
Destination	Next Hop
2.1	R3
2.2	R3
2.3	R3
2.4	R3
2.5	R3
2.6	R5
2.7	R5
1.*	R9
3.*	R9
4.*	R9

Internal destinations.

External destinations.

so this also shows us the

38:44

difference between inter domain and intradomain routing and we'll actually put these two together at the very end

38:49

of the unit so once you learn about inter domain routing we're able to put both of them together so this is just

38:55

kind of a preview but for later what you'll see eventually is that inter domain routing is responsible for these

39:01

routes in green and in sorry intra domain is responsible for these routes in green and Inter domain is responsible

39:09

for these routes in blue so for example you could run something like distance

39:14

Vector inside the network that would give you all of these green entries and then you can run something like bgp to

39:21

talk to other networks and that would give you these entries in blue again we'll probably make more sense once you

39:26

know what BG p is but what's great about this again is that it separates out churn in other networks so for example

39:34

if you are thinking about a route to one point something it doesn't matter if people are joining and leaving Network

39:40

one this entry stays the same and likewise if someone joins and leaves Network 4 it's not your problem this

39:46

entry stays the same it's less table churn you just have to think about Network one network 3 Network 4 and it

39:53

doesn't matter what's inside of those networks which is kind of nice and likewise the distance Vector

39:59

protocol doesn't have to worry about other networks it just focus on the host inside of its own network so by dividing

40:06

up the work in this way we get tables that scale more efficiently more on this

40:12

coming soon

28 of 59

Aggregation – Conceptual

Sometimes, we can aggregate several rows into a single row.

From R4, any packet to an external network has a next-hop of R9.
*.* wildcard says: For any destination not in the table, forward to R9.

Network 4

...

Network 2

2.1

2.2

2.3

2.5

2.4

2.6

2.7

Network 1

...

R4's Table
Destination	Next Hop
2.1	R3
2.2	R3
2.3	R3
2.4	R3
2.5	R3
2.6	R5
2.7	R5
.	R9

R4's Table
Destination	Next Hop
2.1	R3
2.2	R3
2.3	R3
2.4	R3
2.5	R3
2.6	R5
2.7	R5
1.*	R9
3.*	R9
4.*	R9

and actually we can get even more aggressive when it comes to aggregation

40:19

so maybe you noticed that in this picture right here the only way to leave this network seems to be R9 if you want

40:26

to go to network one it's via R9 if you want to go to network 3 anyone with IP

40:32

address 3 something go to R9 if you want to go to anyone with address 4 point something go to R9 you have three

40:39

entries and they all say R9 so actually you can get even more aggressive and summarize all of these and say actually

40:47

I will have a single entry that says R9 and that's something you can do and later we'll see how address aggregation

40:54

works you can get more aggressive with aggregating a doesn't have to be one entry per Network you can also get more

41:01

creative like this and by the way this star point star it's basically saying

41:08

anything Point anything and so what it's saying is if the destination is one of

41:14

these in the table send it to these Next Tops but if you don't see it in the table just send it to R9 more on this

41:21

later but you can already see that aggregation can actually work more aggressively than just one3 Network you

41:28

can even have one entry for lots of networks at once and if you apply this trick over and over again we're

41:34

eventually able to scale to everyone in the internet

29 of 59

Aggregation – Conceptual

From R2, everything is reached through R3, so we can aggregate entries.

The *.* wildcard (everything not in the table) is the default route.
Most hosts only have the default route!

Network 4

...

Network 2

2.1

2.2

2.3

2.5

2.4

2.6

2.7

Network 1

...

R2's Table
Destination	Next Hop
2.4	Direct
2.5	Direct
.	R3

R2's Table
Destination	Next Hop
2.4	Direct
2.5	Direct
2.1	R3
2.2	R3
2.3	R3
2.6	R3
2.7	R3
1.*	R3
3.*	R3
4.*	R3

and in fact aggregation can

41:41

even work like this so for example let's say you are R2 well if you're R2 the decision is even simpler for you so you

41:48

still have to build this table to understand routes to everyone but once you build this table you notice

41:54

something kind of interesting if it's the 2.4 that's Direct directly connected if it's to 2.5 that's directly connected

42:01

but look at everyone else everyone else inside Network to and also everyone else

42:06

inside other networks it all goes to R3 check it out if I want to go to 2.1 next stop is R3 if I want to go to 4.7 next

42:14

toop is also R3 so you can actually get more aggressive like this and just say 2.4 and 2.5 are directly connected

42:22

everyone else just send it to R3 so this wild card is kind of useful it basically

42:27

says everything else that's not in my table just send it to R3 sometimes people call it a default route because

42:34

this is the default if it's not overridden by other table entries so

42:40

when you see this star wild card it's basically saying for every other host not listed here send it to R3 and in

42:47

case you're wondering what hosts do for routing they usually just have one route like this so for example 2.1 if it had a

42:54

routing table what would it say it would just say send everything to R1 it would have one entry that says everyone goes

43:00

to R1 that's why hosts don't have to participate in routing so to close that loop from yesterday

43:07

hosts don't have to participate in routing because they just have to forward everything to their directly connected router and they can use a

43:14

default route to achieve that now you know

30 of 59

Assigning Addresses

Lecture 6, CS 168, Summer 2025

Link-State Protocols

Overview
Computing Paths
Learning Graph Topology

IP Addressing

Hierarchical Addressing
Assigning Addresses
Writing Addresses
Aggregating Routes
IPv6 Changes

31 of 59

Assigning Addresses

Hierarchical addressing makes routing scalable.

Hosts that are "close to each other" (in some sense) share part of their address.
Analogy: All third-floor room numbers start with the digit 3.

When a host joins the network, it's assigned an IP address based on its location in the network.

Analogy: When you move to a new house, your address changes.
How do we assign addresses to hosts?

44:05

we've already seen is that if Two Hosts are somewhat close to each other for

44:10

some definition of that phrase they should somehow share part of their address that's why everyone in network 4

44:17

was 4 something and the analogy I use here if you're thinking about our favorite post office analogy is that all

44:24

the rooms on the third floor are three something something that first digit tells you what floor you're on and

44:30

that's pretty useful for navigating buildings so we're going to use that same kind of trick to help us assign

44:36

addresses if Two Hosts are somehow close to each other they should share some part of their address whatever that

44:42

means and something else to note since we're here is that when hosts join the network their address is based on where

44:49

they are because we just saw that the addresses have to reflect your location

44:55

people who are nearby should have similar address addresses people who are further away have addresses that are very different so what this means is

45:01

that your address is based on your location and what that also means is when you join the network you receive a

45:08

new IP address based on where you are so it's not the case that your computer has the same IP address everywhere if I

45:15

packed up right now and I got on a plane and I went somewhere in Asia I would get a totally different IP address when I

45:22

rejoin the internet and the analogy here is if you move to a new house your address changes you don't move to the

45:28

new house and keep the address that would be very weird so the question we have to ask ourselves now is where do

45:35

these addresses come from who comes up with these numbers and what does it mean for hosts to be close that's something

45:41

that someone has to Define so let's do that now

32 of 59

Assigning Addresses, Attempt 1/3 – Early Internet

Addresses are 32 bits long.

Top 8 bits = network ID.
Bottom 24 bits = host ID.

Each organization gets a unique network ID.

AT&T = ID 12.
Apple = ID 17.
Ford = ID 19.
US Department of Defense = IDs 6, 7, 11, 21, 22, 26, 28, 29, 30, 33, 55, 214, 215.

Bob's address: 11010110 10000100 00111010 01101110

Joe's address: 11010110 10010001 00000000 01001101

Network ID

Host ID

Same network ID, so they must be in the same network.

start with one attempt

45:46

and this is actually what people in the earliest internet did and then we will evolve this to what the modern internet

45:53

does so there's three attempts we're going to make let's start with the very first one that people did in the very

45:58

old days so in the old very old days what people did is they wrote addresses

46:03

as a 32-bit number 32 ones and zeros and they said the top eight bits identify

46:08

the network the bottom 24 bits identify the host this is basically what we just did when we had addresses like

46:16

4.5 these numbers in red would be the four and then these numbers in blue would be the five so they basically did

46:22

the same trick that we just did intuitively and that means that each Network needs a unique ID so for example

46:29

here are some actual numbers that we pulled out AT&T that was an early internet company any computer in AT&T's

46:35

network got id12 so if you signed up to AT&T and connected to the internet your

46:42

address would be something like 12 100 or something Apple got ID 17 Ford

46:48

got 19 whatever something interesting is that the US Department of Defense got quite a few at IDs so it seems like they

46:54

had a lot of networks um not that important but something that we found kind of interesting and what's useful

47:00

about this is we can play the same tricks as before so if we have two people Bob and Joe we notice that they

47:06

have the same network ID so they must be part of the same network just like we saw earlier 4.1 and 4.10 must be in the

47:14

same network similarly here these red bits are the same so they must be in the same

47:21

network

33 of 59

Assigning Addresses, Attempt 1/3 – Early Internet

Addresses are 32 bits long.

Top 8 bits = network ID.
Bottom 24 bits = host ID.

Problems:

Only 2⁸ = 256 different network IDs.

And we already gave the US Department of Defense 13 of them.

Imagine a tiny network (Joe's Tire Shop) with 10 hosts.

If we give them an ID, we're giving them 2²⁴ = 16,777,216 addresses!

We're going to run out!

there's already a problem here maybe you spotted it8 bits gives you 2 to the 8 Network IDs that is 256

47:29

different networks that's not a lot and we already burned 13 of them on the US

47:35

Department of Defense so we are running out very quickly so if you imagine some

47:40

new network that starts up you're running a tire shop for some reason and it's got 10 hosts you're going to claim

47:46

one of those 256 iids that's not a lot to give out to the entire world and if

47:52

we give them an ID even worse is this tire shop now has access to um let's say

47:59

if they get network number 20 they get everything from 20.0 to 20.11 111111 241s so how many

48:09

host IDs live in network number 20 two to the 24 so even this tiny little tire

48:15

shop now has 16 million addresses even though they only have 10 computers that

48:21

the needs to give addresses to so this is very wasteful you just wasted 16 million addresses

48:27

for a network that only has 10 people inside and this is going to run out really quickly so even though this

48:32

worked on the very early internet people very quickly realized that this is probably doomed we're going to move on

48:39

to attempt number two to try and fix this this was the simplest thing they did it's exactly like the intuitive

48:45

thing we saw only problem is it didn't scale very well

34 of 59

Assigning Addresses, Attempt 2/3 – Classful Addressing

Idea: Allocate different network sizes based on need.

The top bits (0, 10, or 110) tell us how to split up the rest of the bits.

0	Network (7 bits)							Host (24 bits)

10		Network (14 bits)														Host (16 bits)

110			Network (21 bits)																					Host (8 bits)

Class A:

Class B:

Class C:

~128 networks

~16m hosts per network

~16k networks

~65k hosts per network

~2m networks

~256 hosts per network

Technically, 254 hosts, not 256, because the all-zeroes address and all-ones address are reserved for special purposes.

so this is try number two what they

48:53

started to realize is that some organizations are larger and some organizations are smaller US

48:59

Department of Defense very big millions of computers joon's tire shop 10 computers very small so now what they've

49:07

done is they've said actually there are three types of addresses some addresses have a seven bit network ID some

49:13

addresses have a 14bit network ID and some addresses have a 21 bit network ID

49:19

and what's nice about this is you can see for example the class c network

49:25

addresses they have only eight bits of host and so what that means is each of

49:31

these networks only can support 256 hosts so if you're a tiny little tire

49:36

shop guess which one you're going to want you're probably going to want Class C and if you're the US Department of

49:41

Defense you probably want Class A because here each Network that you

49:47

allocate has 16 million hosts so basically the idea here is that we're uh

49:52

defining more networks some are larger some are smaller and by allocating the bits in this way

49:59

turns out we get a lot of class C networks millions of them compared to 256 from before now we have millions of

50:06

networks we can support and 16,000 of these somewhat larger networks that can support 65,000 hosts and only 128 of

50:14

these very big networks that can support 16 million hosts per Network and how do

50:19

you tell which type of address you're looking at you look at the top bits and we use this little bit encoding trick where if this is zero it's Class A if

50:26

it's 10 it's Class B if it's 110 it's Class C so that's what the second

50:32

attempt was sometimes called class full addressing because there are three classes and everyone who wants a network

50:39

picks one of the three classes depending on their size

35 of 59

Assigning Addresses, Attempt 2/3 – Classful Addressing

0	Network (7 bits)							Host (24 bits)

10		Network (14 bits)														Host (16 bits)

110			Network (21 bits)																					Host (8 bits)

Class A:

Class B:

Class C:

Bob's address: 10010110 10000100 00111010 01101110

Joe's address: 10010110 10000100 00000000 01001101

Host ID

The top bits indicate this is Class B...

Network ID

...so read the next 14 bits as the network ID...

...and read the last 16 bits as the host ID.

36 of 59

Assigning Addresses, Attempt 2/3 – Classful Addressing

Class A: ~128 networks. ~16m hosts per network.
Class B: ~16k networks. ~65k hosts per network.
Class C: ~2m networks. ~256 hosts per network.

Problems:

Class A is way too big for most organizations.
Class C is way too small for most organizations.
Class B is the best option for many.

~65k hosts is still too big for most organizations.
~16k is still not enough networks. We're running out again!

1989

1990

1991

1992

1993

1994

20,000

10,000

Number of inter-domain routes by year (approximate)

but it turns out the internet kept growing and it kept growing and

51:38

things started to run out again so let's do the math to see why it ran out the

51:44

main reason it ran out is because it turns out the way that these bits were

51:50

split actually did not work so well because most people don't need Class A

51:55

they don't need a network with 16 million people in and actually most people don't want Class C either because

52:01

Class C only allows you to support 256 hosts and maybe if you're a company you

52:06

want more than that so actually it turns out most people just ended up using Class B and A and C were not really used

52:13

so we ended up back in the situation where we're mostly using one class namely Class B and Class B we saw

52:20

earlier support 16,000 networks and turns out 16,000 is not

52:25

enough so as time went on this number crept closer and closer and we saw that

52:31

if this curve continues going upwards we're going to run out of class B networks as well so once again we have

52:38

another scaling problem although this was a better attempt it's still not great and the reason why we ran out by

52:44

the way is because most people don't need 65,000 posts so we gave you a Class B

52:50

network if you only have 500 posts you're wasting 64,500

52:56

unused addresses that someone else could have used that's our second attempt still not

53:03

great

37 of 59

Assigning Addresses, Attempt 3/3 – CIDR

With classful addressing, we tried to use convenient 8-bit boundaries.

Class A: 8 bits for class/network. 24 bits for host.
Class B: 16 bits for class/network. 16 bits for host.
Class C: 24 bits for class/network. 8 bits for host.

What if we could assign network IDs of any length?

Leads to CIDR (Classless Inter-Domain Routing).
This is what the Internet uses today.

0	Network (7 bits)							Host (24 bits)

10		Network (14 bits)														Host (16 bits)

110			Network (21 bits)																					Host (8 bits)

Class A:

Class B:

Class C:

so let's move to the third and final attempt this is the one that we use today and the idea is why do we have

53:09

to create these arbitrary splits why do we have to split Network and host here and here and here what if I split it

53:16

here or here or anywhere in the middle so that's what we're going to do next instead of defining a b c and defining

53:24

three specific split points between Network and host what if I could assign

53:30

a network ID that's 8 Bits 12 13 15 if I

53:35

can use any number I want instead of just 7 14 21 that can give me more

53:41

control over the size of my network and that allows me to allocate just enough for what I need so if I only need nine

53:48

bits of host I can create a 20 bit network ID for example and this leads to what the modern internet uses it's

53:54

called classless in domain routing here is classless earlier it was class full

53:59

and that idea here is that we are removing the notion of specific classes we making things more

54:07

flexible

38 of 59

Assigning Addresses, Attempt 3/3 – CIDR

Suppose Joe's Tire Shop has 450 hosts.

Classful addressing:

Class C gives us ~256 hosts. Not enough!
Class B gives us ~65k hosts. Too many!
We have to use Class B (and waste tons of addresses).

Classless (CIDR) addressing:

8 host bits = 256 bits. Not enough!
9 host bits = 512 bits.
Still not exactly 450, so still some wasted addresses.
But much less wasteful!

Network ID (23 bits)																							Host ID (9 bits)

so how would you do this you'd have to do a little bit of math so for example let's say you have a tire shop

54:13

with 450 hosts in the classful addressing approach you have to choose a

54:18

BC there's multiple choice if you choose C you get 256 hosts that's not enough

54:24

you have 450 if you Class B you get 65,000 that's way too many you're

54:29

wasting lots of unused addresses but you're forced to use B not so great in

54:35

classless addressing you don't have to choose ABC you can say eight bits are not enough but nine bits are enough so

54:42

yeah you do waste some addresses you waste 72 62 addresses but that's okay

54:49

this is still much better than class full addressing so now this boundary doesn't have to be at a fixed Point

54:55

instead of choosing 7 14 21 here we chose 23 because that was the best fit

55:01

for this particular use

39 of 59

Granular Hierarchical Assignment with CIDR

CIDR enables multi-layered hierarchical assignment of addresses.

ICANN. (Internet Corporation for Names and Numbers)

Top-level organization that owns all the IP addresses.
They allocate blocks to...

RIRs. (Regional Internet Registries)

Representing Europe (RIPE), North America (ARIN), Asia/Pacific (APNIC), South America (LACNIC), and Africa (AFRINIC).
They give out portions to...

Large organizations or ISPs.

Sometimes called Local Internet Registries (especially in Europe).
They give out portions to...

Small organizations and individuals.

Examples: UC Berkeley, Joe's Tire Shop.

and something else that's very nice

55:06

about the classless version of addressing is you can actually create multi-layered hierarchal assignment so

55:13

instead of just writing 4.2 that is Network 4 Post Number Two you can

55:19

actually get more specific you can say 4.2.1 or you can say 4.2.1 point2 you

55:26

can create multiple layers and play the same trick of hierarchy across multiple layers and in fact that's what we do

55:33

there's actually a very natural hierarchy so let's see it in action so the very top level of the hierarchy is

55:41

the internet Corporation for names and numbers it's some organization that manages IP address IP addresses and they

55:48

own all the IP addresses so at the very start every IP address from all zeros to

55:53

all ones is owned by I can and if you want one you have to go ask them but in fact they're not going to service

56:00

addresses to everyone so instead what they did is they took the address space and they cut it up and they said this

56:06

part goes to Europe this part goes to North America this part goes to Asia this part goes to South America so they

56:13

took the whole pie and they cut it up into slices and each continent got a specific slice and those are called

56:20

Regional internet registries you don't have to remember that but you can imagine those are organizations

56:25

represent pres ing each specific continent and again we don't want one organization handling all the addresses

56:32

in Europe that's pretty bad so instead uh it's not scalable so instead Europe will take its slice of the pie and cut

56:39

it up into even smaller slices and give those out to local internet registries

56:44

and those are organizations like uh UC Berkeley or isps like AT&T so the

56:51

continent level registry then cuts it up and then gives it out to organization

56:56

and those organizations can give out smaller portions to even smaller organizations so for example maybe the

57:03

UC system cuts out a slice and gives it to UC Berkeley UC Berkeley cuts out a slice gives it to the eeks department so

57:09

you don't have to memorize this exact hierarchy but what this is showing is that in real life hierarchies are

57:16

multi-layer you splits into a bunch of universities each University splits into a bunch of departments each department

57:23

splits into a bunch of classes and so on so just like how real life hierarchies are multi-layered addresses can also be

57:30

multi-layered to model those real life hierarchies which is kind of useful

40 of 59

Granular Hierarchical Assignment with CIDR

ICANN owns all addresses: ................................

ARIN (North America) owns: 1101............................

4 bits fixed, 2²⁸ ≈ 268m addresses.

AT&T (large ISP) owns: 110111001.......................

9 bits fixed, 2²³ ≈ 8m addresses.

UC Berkeley owns: 110111001110100010..............

18 bits fixed, 2¹⁴ ≈ 16k addresses.

Soda Hall owns: 110111001110100010011010........

24 bits fixed, 2⁸ ≈ 256 addresses.

Prof. Ratnasamy owns: 11011100111010001001101001011101

All bits fixed, 1 address.

57:36

here's an example of addresses being allocated I can owns the whole Pi so

57:41

here you can imagine a DOT is not fixed so 32 dots means they own every address

57:47

each of these can be a one or a zero and it's originally owned by Ian and then what Ian does is it says I'm going to

57:54

fix the top bits to 1 one0 one the bottom bits can be anything from all zeros to all ones this range this SCE of

58:01

the pi belongs to North America it's yours now do whatever you want with it so the North American registry now owns

58:08

all the addresses starting with 1 one01 that is 268 million addresses because

58:13

you have 28 unfixed bits and then North America says I don't want to handle 268

58:19

million addresses so I am going to give some of them to AT&T in particular I

58:25

will fix five more bits and anything that starts with these nine bits belongs to AT&T so go ask them if you want an

58:32

address in this range now AT&T controls 8 million addresses and this goes on

58:38

AT&T fix some more bits and sends anything starting with this sequence of

58:43

bits to UC Berkeley so now they own this and maybe UC Berkeley fix some more bits

58:48

now anything starting with these 24 bits that's only 256 addresses is owned by

58:53

soda hall and then maybe a specific Prof profess owns a specific address of all

58:58

32 bits fixed so this is a hierarchy it's not real soal doesn't really own

59:04

any IP addresses but you can see that hierarchies in addressing kind of work like hierarchies in real life that we

59:11

see all the time so that's how you assign addresses

41 of 59

Writing Addresses

Lecture 6, CS 168, Summer 2025

Link-State Protocols

Overview
Computing Paths
Learning Graph Topology

IP Addressing

Hierarchical Addressing
Assigning Addresses
Writing Addresses
Aggregating Routes
IPv6 Changes

42 of 59

Writing IPv4 Addresses

We could write an IP address as a 32-bit number: 11011100111010001001101001011101

Nobody wants to read that.

Dotted quad notation:

Split into groups of 8 bits.
Write each 8-bit number in decimal, separated by dots.

11011100 11101000 10011010 01011101

220

232

154

his is really just formatting more so than any

59:36

conceptual thing but we should talk about it because you'll have to write these addresses all the time so if you

59:41

want to to you can write 32 bits 32 ones and zeros that's an address I don't want

59:47

to read that you don't want to read that it's really gross so instead what people often do is they use something called

59:53

dotted quad notation you've probably already seen this before and what they do is they take the first eight bits

59:59

convert it into a decimal number then the next eight then the next eight then the next eight so you get four numbers

1:00:05

separated by dots each number ranges from 0 to 255 that's all zeros to eight

1:00:11

ones and it's basically what you'd expect but this is how people write IP addresses but when they write this it's

1:00:18

not because they really want these four numbers it's just a short hand for those 32 bits that are quite hard to

1:00:24

read

43 of 59

Writing IPv4 Address Ranges

Slash notation for writing ranges of addresses:

Set all unfixed bits to 0. Write as a dotted quad.
After the slash, write how many bits are fixed.

Examples:

192.168.1.0/24 means 24 bits are fixed. Range is 192.168.1.0 – 192.168.1.255.
192.168.1.0/29 means 29 bits are fixed. Range is 192.168.1.0 – 192.168.1.7.
192.168.1.1/32 means 32 bits are fixed. A single address.
0.0.0.0/0 means no bits are fixed. All addresses.

11011100 11101000 10010000 00000000

220

232

144

11011100 11101000 1001.... ........

Set all unfixed bits to 0.

/20

Number of fixed bits.

something else is writing ranges of IP addresses so you could actually just

1:00:31

go out and write the ranges explicitly you might go out and say I own all the IP addresses from

1:00:39

192.168.1.0 all the way to 192.168.1.254 you can go out and say

1:00:45

that but it's kind of a mouthful to write two IP addresses and say you have a range so in real life what people do

1:00:52

is they use something called slash notation and all you have to do here is take the bits that are not set set them

1:00:58

all to zero so look this is the prefix that I care about these are the bits that are unset so I force them to all be

1:01:05

zeros convert that into an IP address which is 2202 32.1

1:01:11

144.000 then I'll write a slash and then after the slash I'll write how many bits were fixed so when you read this read it

1:01:18

like this the top 20 bits are fixed translate this IP address into bits and

1:01:24

write out the top 20 bits those are are fixed everything else is variable from all zeros all ones so it's kind of a

1:01:31

notational note but this is how people write IP ranges here are some examples that I won't say out loud something to

1:01:37

notice is that the boundaries don't have to be exactly on the dots so for example

1:01:42

if you have a slash 29 it means that the top 29 bits are fixed and only the

1:01:48

bottom two bits can change from 00 0 to 111 represents this range if you write

1:01:54

it out if you put sl32 it means all the bits are fixed if you say 0.0.0.0

1:02:00

sl0 that represents all of the addresses so again it's kind of a notational footnote but since you'll see it a lot

1:02:07

it's good to know what they mean and how people write ranges

44 of 59

Writing IPv4 Address Ranges

Netmask is an alternative to the number after the slash..

Set all fixed bits to 1, and all unfixed bits to 0. Write as a dotted quad.
Useful in code: To extract network ID, bitwise AND the address and netmask.
Slash notation is more convenient for humans.

Slash notation: 220.232.144.0/20

Netmask notation: 220.232.144.0 (netmask 255.255.240.0)

11111111 11111111 11110000 00000000

255

240

11011100 11101000 1001.... ........

Set all bits to 0 or 1.

okay a little bit more notational

1:02:14

notes sometimes people don't like writing slash notation so they instead write something called a net mask and

1:02:21

here all you're doing is replacing the slash with a net mask so the original

1:02:26

range you still have to write the prefix so let me try that again you are still

1:02:32

representing a range to write the range you still have to start with the prefix and the way you write the prefix is just

1:02:37

like before you take the prefix you set all the remaining bits to zero and you write it as a dotted quad so notice that

1:02:44

in both notations you write 220 232 1 1440 that has not changed a net mask

1:02:50

only changes the slash so we no longer write slash2 what we instead do is we

1:02:56

set all the fixed bits to one all the unfixed bits to zero we write this as a quad and that's the net mask so this net

1:03:03

mask of 255 255 240 it represents the exact same thing as 20 someone just

1:03:10

wrote it differently they just wrote 21s followed by 12 zeros put a bunch of dots

1:03:16

in between them this rep uh this net mask replaces the 20 it does not replace

1:03:22

everything else here why is this useful by the way I think 20 is easy to read for humans but this is useful because

1:03:28

and we'll see this a little bit later in the class as well this allows you to do bitwise operations let's say you only

1:03:34

care about the network ID and you want to throw away the bottom bits you can just perform a bitwise and and if you

1:03:41

know your bitwise operations that will keep all of the top bits intact and zero out all the bottom bits so computers

1:03:48

often like to use net masks oras humans like to slashes but all of this is just

1:03:53

fancy notation for writing ranges of IP addresses

45 of 59

Aggregating Routes

Lecture 6, CS 168, Summer 2025

Link-State Protocols

Overview
Computing Paths
Learning Graph Topology

IP Addressing

Hierarchical Addressing
Assigning Addresses
Writing Addresses
Aggregating Routes
IPv6 Changes

46 of 59

Inter-Domain Routing

In inter-domain routing, we're looking for routes to other networks.

Each destination is a network, represented by an IP prefix.
Already better than one entry per host...but we can do even better!

AT&T

4.0.0.0/8

UC Berkeley

130.0.0.0/8

Stanford

146.0.0.0/8

Orange (France)

R6's Table
Destination	Next Hop
4.0.0.0/8	R2
130.0.0.0/8	R2
146.0.0.0/8	R2
...	...

so we're

1:05:18

starting to move a little bit toward in domain routing so consider this a bit of a preview for the in domain routing that

1:05:24

we're going to see coming up next time and we'll see how aggregating routes is

1:05:29

able to help us make these tables more scalable so let's say you're R six and

1:05:36

you're building a table in the naive version you would have to build one entry for every single destination in

1:05:42

France in the US UC Berkeley and Stanford that is way too much it's not happening so instead what happens is

1:05:50

we'll play the same tricks as before each network instead of having a number like before where we said four .2 that

1:05:56

would have been true in the very early internet but we now know that there's actually multi-layer hierarchies going

1:06:02

on so each organization whether it's UC Berkeley or AT&T they own a range of

1:06:09

addresses so we've generalized the idea of having numbers like 5.3 and 10.2

1:06:16

we've generalized that using class list addressing to say that everyone has a range and remember we can use slash

1:06:22

notation to write the range so AT&T owns all of the addresses with the top eight

1:06:29

bits fixed and if you're wondering what those bits are turn this into ones and zeros you'll find out and you see

1:06:34

Berkeley owns all of the addresses with the top eight bits fixed where the top

1:06:39

eight bits are the top eight bits of this address whatever they are write it out and find out so as before every

1:06:46

network has a range of addresses using classist addressing and when you write

1:06:52

entries in your table all you have to do is write range anybody in the range

1:06:57

4.0.0 sl8 please send it to R2 and anyone in UC Beres range send it to R2

1:07:04

as well and anyone in Stanford's range also send to R2 so it's the exact same

1:07:10

thing as we saw earlier but instead of using the simpler version of hierarchy where there's just two layers we now

1:07:16

have multiple layers of hierarchy to reflect the fact that real life also has multi-layer

1:07:23

hierarchical relationships we can actually do even better than this

47 of 59

Inter-Domain Routing

With CIDR, AT&T allocates parts of its ranges to UC Berkeley and Stanford.

We can aggregate many networks into a single entry!
4.0.0.0/8 represents AT&T, and all its subordinates.

AT&T

4.0.0.0/8

UC Berkeley

4.12.0.0/16

Stanford

4.29.0.0/16

Orange (France)

R6's Table
Destination	Next Hop
4.0.0.0/8	R2
4.12.0.0/16	R2
4.29.0.0/16	R2
...	...

so let's do that one thing we'll notice

1:07:30

is that actually what happened here is these numbers didn't really come out of nowhere like here where I just made up

1:07:36

4.0. z.0 sl8 that's all totally made up in real life we already saw that what

1:07:42

actually happens is that addresses get allocated to different people so you cut a slice of your pie and you give it to

1:07:48

someone else so maybe what happened is not that AT&T and UC Berkeley have randomly generated prefixes what really

1:07:56

happened is that AT&T took its range cut a little slice gave it to UC Berkeley

1:08:01

cut another Little Slice gave it to stard and that's what we see here so

1:08:06

actually maybe a more realistic depiction of the relationships is that AT&T owns this whole range gives a small

1:08:13

piece to UC Berkeley gives a different small piece to Stanford and now what we

1:08:18

can do is we'll notice that all three of these ranges they fall in the same

1:08:24

larger range because all of this is just AT&T's range these are just two small slices of it so instead of writing three

1:08:31

separate entries for AT&T and UC Berkeley and Stanford we can just write one entry for anybody in AT&T's range of

1:08:38

which UC Berkeley is a slice and Stanford is a slice please send all of that stuff to R2 so now this represents

1:08:45

AT&T and every organization that AT&T handed a slice of its address range out

1:08:51

to this is all of AT&T's range smaller slices went to other people we can see

1:08:56

already that this is three networks represented by one entry and if AT&T had

1:09:02

millions of slices that it gave out this could be millions of networks represented by a single entry which is

48 of 59

Inter-Domain Routing

Now, Stanford wants to connect to multiple networks. This is called multi-homing.

We need an entry for both AT&T and Stanford (one of its subordinates).
Multi-homing limits aggregation!

AT&T

4.0.0.0/8

UC Berkeley

4.12.0.0/16

Stanford

4.29.0.0/16

Orange (France)

R6's Table
Destination	Next Hop
4.0.0.0/8	R2
4.12.0.0/16	R2
4.29.0.0/16	R7
...	...

somewhat annoying point though and it's something we'll come

1:09:14

back to later as well is the idea of multihoming and what multihoming means

1:09:19

is that maybe Stanford doesn't just want to have a slice of or doesn't want to just be serviced by AT&T so yeah it has

1:09:27

the addresses from AT&T but maybe it also wants to be connected to this network in France well in that case it's

1:09:34

no longer enough to say everyone AT&T's network and all of its subordinates should go to R2 in this case you

1:09:42

actually have a shortcut directly to Stanford because R six has a direct link to R7 so in a topology like this where

1:09:49

Stanford is served by both AT&T and this company in France maybe R six has a

1:09:54

shortcut to reach Stanford so now when you read these entries you have to be a little bit more careful because if you

1:10:01

look at this entry what does it really say it says well actually all of AT&T

1:10:07

and its subordinates go to R2 except for one subordinate Stanford it's special that when you have a shortcut go to R

1:10:14

seven so when you have multihoming it limits aggregation and this is something we'll see more we me talk more about

1:10:20

inter domain routing but basically what this is showing is that aggregation works but sometimes you don't want to

1:10:26

aggregate all the way here's the case where if you aggregated all the way you would have lost this neat little

1:10:31

shortcut and by not aggregating Stanford and saying actually Stanford is a separate range you get to keep the

1:10:37

shortcut around that might be useful there's a bit of a tension between multihoming and

1:10:46

aggregation

49 of 59

Inter-Domain Routing

Ranges in the table might overlap.

Longest prefix matching: If a destination matches many ranges, pick the most specific range.
Example: 4.29.1.2 matches both 4.0.0.0/8 and 4.29.0.0/16 (more specific).

AT&T

4.0.0.0/8

UC Berkeley

4.12.0.0/16

Stanford

4.29.0.0/16

Orange (France)

R6's Table
Destination	Next Hop
4.0.0.0/8	R2
4.12.0.0/16	R2
4.29.0.0/16	R7
...	...

and one thing you'll notice in multihoming cases and in general is

1:10:51

that these prefixes sometimes overlap and that can be a problem so if you actually write out the ones and zeros

1:10:57

which I will not do here but try it at home if you're interested you will see that actually this range is a super set

1:11:04

of this range put it another way this range 4.29 16 that's a little slice of

1:11:10

4.0.0 point0 so if you want to send a packet to someone in Stanford technically both of these are valid

1:11:16

entries it falls in this range and it also falls in this range because this lower range is a small slice of the

1:11:23

larger range so both of these are valid entries which one do you use to forward

1:11:29

packets to your friend in Stanford you could use either of them and it turns out what you have to do is something

1:11:35

called longest prefix matching so pick the most specific one in this case the

1:11:40

sl16 is more specific it's a smaller range so use that one and don't use the more General one that's something we'll

1:11:46

see again later as well so in the case that an address matches multiple ranges

1:11:52

please pick the most specific one and that allows you to forward packets to a

1:11:58

host that matches multiple entries that's in multiple

1:12:05

ranges

50 of 59

IPv6 Changes

Lecture 6, CS 168, Summer 2025

Link-State Protocols

Overview
Computing Paths
Learning Graph Topology

IP Addressing

Hierarchical Addressing
Assigning Addresses
Writing Addresses
Aggregating Routes
IPv6 Changes

51 of 59

Running Out of IPv4 Addresses

IPv4 addresses are 32 bits long. 2³² ≈ 4 billion addresses. Is that enough?

2017: Every regional registry had fewer than 2²⁴ ≈ 16m addresses left.

2021: We're running out!

https://ipv4.potaroo.net

so something you might have already

1:12:17

started to worry about is that ipv4 addresses are 32 bits long remember we

1:12:22

showed 32 bits and how they got allocated and if you actually do the math 2 to the 32 is 4 billion

1:12:29

addresses if you asked this question in the 1990s four billion seemed like quite a lot if you ask this question in 2025 4

1:12:38

billion suddenly doesn't seem that much we have what like 8 billion people on Earth that's not a very big number

1:12:44

compared to the number of people on Earth or the number of computers on Earth and it turns out we have actually

1:12:50

been running out of IP addresses for about 10 years now so what this graph shows is the number of IP addresses that

1:12:56

have not been allocated yet and we can see that in 2013 there were some left

1:13:01

and each of these lines by the way represents a different continent and what you see is that as we go from 2013

1:13:07

to 2017 everyone is running out by 2017 everyone had 16 million or fewer

1:13:14

addresses left out of their original range and now we're in 2021 and we are

1:13:21

quickly running out and if I extended this to 2025 the lines would get even closer to zero this is bad we are in

1:13:29

trouble we're running out of addresses to gift to computers as they signed onto the network

52 of 59

Running Out of IPv4 Addresses

A ceremony where the last range of IPv4 addresses was allocated. (February 2011)

53 of 59

Introducing IPv6

IPv6 was introduced in 1998 to deal with IPv4 address exhaustion.

Main difference: Addresses are now 128 bits, instead of 32.
Fundamentally, same addressing structure as IPv4.
Some other minor changes (won't discuss here).

Is 128 bits enough?

2¹²⁸ ≈ 3.4 × 10³⁸ possible addresses.
Assigning an address to every second of the universe's history uses 0.000000000000001% of the addresses.
We won't run out again.

IPv5 was an experimental protocol from the 1990s. It was never widely implemented.

so to fix that we need a new version of Ip and that's what people started to build they actually started

1:14:06

building this in the 1990s because they started to realize that this is going to happen and so the real the main

1:14:13

difference between ipv4 which is what we've been seeing so far and IPv6 is just that addresses are no longer 32

1:14:19

bits they are now 128 bits so IPv6 is mostly the same they didn't really

1:14:25

change that much the main thing that they changed is just the fact that addresses are now 128 bits instead of 32

1:14:33

later we'll see some other very minor changes but for now that's the one you have to know um but overall the

1:14:38

addressing structure is still the same it's still higher archical you can still do multi-layer hierarchy it's all the

1:14:44

same things you just do it with 128 bits instead of 32 so one question you might ask is is

1:14:51

this going to run out are we headed for ipv 8 or n sometime in the future I don't think so

1:14:57

if you do the math 2 to the 128 is an astronomically large number this is like

1:15:03

number of atoms in the universe type number this is enormous and even if you

1:15:08

gave an address to like every second of History you barely use them so these

1:15:14

numbers are mindboggling and it basically means that for the foreseeable future we are never running out of

1:15:19

addresses again IPv6 has solved the problem of running out of addresses and

1:15:25

if you care about what happened to five it was a draft and it never got implemented so it went from four to

1:15:32

six

54 of 59

IPv6 Addresses

IPv6 uses hexadecimal instead of decimal.

2001:0DB8:CAFE:BEEF:DEAD:1234:5678:9012
Colon between every 4 hex digits (16 bits).

Shorthand:

Omit leading zeros per block:�2001:0DB8:0000:0000:0000:0000:0000:0001 → 2001:DB8:0:0:0:0:0:1
Omit a long string of zeros, once per address:�2001:DB8:0:0:0:0:0:1 → 2001:DB8::1

Can still use slash notation for ranges.

2001:0DB8::/32 has 32 bits fixed, and 2⁹⁶ addresses.

so a little bit of notation on IPv6 they change the way you write addresses just a little bit and again this is not

1:15:39

the most important thing is just how you write these addresses so instead of using decimal they switch to using

1:15:44

heximal and what that means is you have to write four heximal digits for every

1:15:50

32 or for every 16 bits I can't do math four hex digits represent 16 bits you

1:15:55

write eight of them that gives you 128 bits so this is just a long HEX number

1:16:01

if you convert every hex digit into bits you'll get 128 bits so these are longer

1:16:07

and because they're long sometimes you can get lazy you don't want to write the whole thing you can already see this is quite long so sometimes what people do

1:16:15

is if you have z0000 Z within two colons you can just write one zero and everyone

1:16:21

knows what you're talking about so this zero is really 32 zeros but no one wants

1:16:26

to write that so we just wrote a single zero and sometimes what people do is they can also emit a bunch of zeros so

1:16:32

instead of writing zero colon zero colon zero colon zero they just write a double colon and everyone knows you know I know

1:16:39

we all know that in between these double colons you just fill in zeros to get 128

1:16:44

bits in total you can only do this once if you do it twice it's not clear how many zeros to put in each omitted range

1:16:50

but if you do it once we all know that there these bits on the right these on the left put zeros in between and you

1:16:57

get your address so again not the most important thing but if you go out into the wild and you see addresses now you

1:17:03

know this is the way that they are written and just like an ipv4 you can use slash notation so you write a range

1:17:10

here we use the double colons to be lazy and not write all the zeros and the SL 32 means the top 32 bits are fixed and

55 of 59

IPv6 Addresses

IPv6 generally uses the same hierarchical addressing approach as IPv4.

Some changes:

Instead of someone (e.g. ICANN) giving you a prefix, you can pick your own prefix.

Uses a protocol called SLAAC (Stateless Address Autoconfiguration).
Pick a random prefix. If someone else is using it, pick another one.
Works in IPv6 (not IPv4) because there are so many prefixes.

In practice, prefixes usually fix at most 64 bits.

Even the smallest network has 2⁶⁴ hosts.

again the hierarchy is generally the same but something nice

1:17:28

about IPv6 is that the range is so enormous like astronomically big that

1:17:35

actually we don't have to play some of those tricks that we did before remember earlier we had to be really careful with

1:17:40

the way we addressed because Class A Class B Class C didn't give us enough 128 is so big that you're basically

1:17:47

never running out no matter what you do within reason so actually there are some

1:17:52

tricks you can play in IPv6 that you cannot do in ipv4 because of the gigantic number of prefixes so something

1:17:59

you can actually do in IPv6 is you can pick your own prefix instead of other people handing you one like they did in

1:18:06

ipv4 where space is limited and someone has to give you one IPv6 the space is so

1:18:12

big that you can just pick your own and there's actually a pretty good probability that no one else is using it

1:18:17

you pick it and with like 99% probability no one else is using it so it's yours and if someone else is using

1:18:24

it just pick another one so we'll actually see this again later in the class but it's a trick that you can play

1:18:29

an IPv6 but not four it's giving yourself a prefix not the most important

1:18:35

thing but kind of cool and in practice because the space is just so big it's

1:18:41

often the case that you just use 64 bits for the network ID 64 bits for the host

1:18:46

ID and that's totally fun you're G to have way more than you need for the number of hosts and the number of

1:18:52

networks on the internet so if only the early internet designers had written 128

1:18:58

instead of 32 we probably wouldn't have had to do any of this but because they chose 32 bits we have to go through all

1:19:04

this redesign

56 of 59

IPv6 Adoption

IPv6 introduced in the 1990s, but wide adoption started in the 2010s.

Today, ~40% of hosts have adopted IPv6.

https://www.google.com/intl/en/ipv6/statistics.html

IPv6 adoption really quick note IPv6

1:19:11

is actually not used by everyone so it turns out introducing a new protocol is pretty hard if a computer refuses to

1:19:18

update it software it might be stuck using ipv4 and it doesn't understand IPv6 so actually even even though this

1:19:25

verticle was developed in the 1990s as of 2010 basically nobody used it but as

1:19:32

addresses started to run out people started to realize we probably need to be upgrading our software to understand

1:19:38

IPv6 so newer computer started to understand IPv6 we started to install

1:19:43

IPv6 into older servers and adoptions slowly increased but even as of

1:19:49

2024 it's actually still less than half so over half of all computers still only speak iv4 so you can see that adopting a

1:19:57

new protocol is quite slow especially if you need everybody on Earth to

1:20:03

understand it

57 of 59

IPv6 Adoption

Adoption generally correlated with areas where there are many Internet users.

58 of 59

IPv6 Adoption – Challenges

Why is IPv6 adoption hard?

Requires software and hardware upgrades, from both hosts and routers.
IPv4 and IPv6 are not compatible with each other.

To support both, you need 2 forwarding tables.
No way to convert between IPv4 and IPv6.

If I support both IPv4 and IPv6, which should I use?

IPv6 usually faster, but other factors could affect your choice.

Main driver for IPv6 adoption: We're running out of IPv4 addresses!

why is it hard by the way why

1:20:21

hasn't everyone just immediately switched to IPv6 well one reason is you have to upgrade your computer some

1:20:27

servers are very old and it's just very hard to upgrade them or people are lazy they don't want to update them so you

1:20:32

got to update your software to understand IPv6 the two Protocols are not compatible so you actually have to

1:20:39

support both it's not one or the other so if you want to speak both ipv4 and IPv6 you have to support both there is

1:20:45

no way for six to work with four or anything they're two basically separate

1:20:51

protocols and you would need for example two forwarding tables and if you support both which one should you use it's not

1:20:57

immediately clear maybe you want to use one maybe you want to use the other something you have to think about if

1:21:02

you're installing both but again it's still important that we do this because if the world doesn't move to IPv6 we're

1:21:08

going to run out of addresses it's important that we do this even though it's kind of

1:21:14

painful

59 of 59

Summary: IP Addressing

Hosts on the Internet have addresses (IPv4, IPv6, or both).
These addresses are hierarchical.

They are assigned in groups to specific organizations.

Wildcard matching means that this can help our forwarding and routing scale better.