0:42
But pretty much, no human being is actually a rational agent, so the
economist may say gee, human beings are not nice, they do not behave according to
my model. But in reality, you have to face the fact
that a lot of these assumptions simply do not hold.
So what kind of model can be tractable and still have predictive power in economics?
I don't know. But in the upcoming few lectures, we'll be
turning our attention back to technological networks.
1:19
Similar to the Qualcomm and Google stories back in lectures one, two and three,
especially in lecture one. And we're going to see the predicted power
to be much, much higher, because it's much easier to model, machines, that we have
actually designed. So we're going to move into a few
lectures. Starting with the basic principles of the
Internet. And then we will go into routing,
How does traffic go through the Internet. So that's the plan.
And therefore this is going to be a long lecture.
2:01
It's sort of like as long as lecture four, if you remember how long that was.
Because we have to talk about two things. One is, give a brief introduction of the
Internet design principles. And then we'll talk about the specifics of
routing protocols. So this lecture serves two major purposes.
Now it is very tricky to talk about the historical evolution of technology such as
the Internet. Part of that was based on design.
And we would love to think that the historical evolution all follow from
design. But there's lot of influence from simply
historical legacy of accident, accidents. Okay?
Ranging from some very important principles, such as backward
compatibility. Okay?
Your new design have to be able to be compatible with all the previous
generations, such as incremental deployability.
You can deploy this new software or hardware, in an incremental way, and still
start to see the benefits without turning the whole network upside down.
Overnight, such as economic incentives. You have to provide the right incentives,
as we saw last lecture, to all the parties involved.
But there are also other sort of silly reasons like lack of coffee in one morning
when somebody in IETF one of the major internet standardization body wanted to
argue for or against a case. Okay, or political and economic reasons of
supporting or vetoing certain standards. So there's a lot of historical legacy of
simple accidents. So it is even more amazing to see that the
internet had thrived so well. There must be some robustness not just in
the internet itself but also in the evolution of the internet.
So here's a very brief history, history of what we have gone through.
Back in the 1950's and before we were all looking at was called a PSTN.
It's got a funny name a plain simple telephone network.
And it is what we call a circuit switch. We'll soon be contrasting circuit switch
with packet switch. Then in the 1960s researches have started
look at packet switch network, which is a lot more efficient, when you have bursty
arrival and departures of traffic. And this culminated in 1969's creation of
the ARPANET. Arpa stands for Advanced research project
agency. And it's one of the US federal funding
agencies, funding fundamental research. And they're following developments.
So, and it's called Arbornet. There were many important milestones
since'69. One of which a highlight is the invention
of TCP/IP protocol. Okay?
Transmission Control Internet Transmission Control Protocol/Internet Protocol.
It started that as a single protocol. And then it later split it into TCP and
IP. We'll soon be talking about TCP and IP in
great detail today and in the next lecture, as well as the interplay between
the two. And TCPIP was really special case of a
general principles. Of protocol stat That is layered.
5:54
Well what is a protocol? Well a protocol basically is a sequence of
computation and communication to control the behavior of a network.
Layered stack of protocols provides a modularization that can divide and conquer
the big problem into smaller pieces And then in 1985, the evolution of ARPANET
turned into was called NSFNET. Nsf stands for National Science
Foundations is another US Federal funding agency of fundamental research.
It took over the development of the Internet, which buy that point has indeed
developed into, a network of networks. Along this long history, actually, not
that long, maybe, you know 50 years of evolution, there were many important
figures. Such as so-called forefathers of the
internet, or sometimes people call eight or twelve fathers and one mother of the
internet. But no single person sort of invented one
monolithic object called the internet. Okay.
Internet really is interworking of a network of networks.
Okay, your computer connected through the ethernet, my phone is connected through
the cellular network, and some routers in between.
It's a network of networks. And then in, 1990 or 89, depending on
which event you count The world wide web was invented.
Now, it is very important to have some kind of user interface UI, that is
friendly. And world wide web started doing that with
a protocol, to do, the right user interface followed by a browser, followed
by a portal. Okay?
Browser like Netscape, back in the mid 90's.
Portal like Yahoo and other services such as eBay,
Amazon, Hotmail.
If you recognize some of these like Hotmail it means that you're, are as old
as I am. Or older.
But some of these clearly stayed on over the last almost twenty years such as eBay
and Amazon. Right?
One of the first set of most important portals is Yahoo.
Okay. So by 1994, 95, the internet has taken off
commercially. Okay, the government decommissioned the
NSF net, the commercial interest, took that into, ridiculously fast exponential
growth. Now we are in the age of 2012.
And it's projected by 2020, there will be six times more connected devices to the
internet than there are people on this planet.
So that is an incredible, if you count all the way to 2020 let's say.
Okay? An incredible half a century of
development. Now this course is not a technology
history course. So we're going to switch into the three
fundamental ideas behind the design of the Internet.
9:30
These are not specific artifacts of engineering but they are ideas and very
powerful ideas. The first one I'll highlight is packet
switching. Now, the basic idea as in many powerful
ideas are actually simple once you state them in the right way.
It says that if the users don't require dedicated resources, okay, no need for
dedicated resources, then don't dedicate resources, share them.
9:59
When we say a user in this lecture at least, a user is equivalent to a session,
or what I call a simple session. What is a simple session?
Well, a session, for example here is you, right, holding your phone, and here is a
YouTube server in Google's cloud. It go through actually many, many hobs as
we'll see in a minute, okay? But actually once when you pull something
okay whether its a video or webpage often times you pull other things.
For example a server with advertisement okay.
Or a server with cookies or other control messages okay.
So when we say there's session or a user, we really mean just the primary session if
you will. Often when you download a movie, a stream,
a movie actually comes from many different servers.
The 1-hour movie, let's say, actually could come from ten different servers with
different segments. We ignore that, we say, well, in that
case, just say there's ten sessions. Okay?
So, for us, today, a user is a session, is a simple session, is also a unicast
session, meaning that there is only one source and one destination.
11:19
Later we'll see one source but N destinations, all requiring the same
content at about the same time. That's multicast.
But today it's simple uni-cast session. Now before the early 60's was the phone
networks, which was another remarkable, remarkable invention in human history, and
it was circuit switch. What does that mean?
It means from this source to this destination we use, usually use S and T to
denote these two nodes. Inside there is a network, you could to
establish a whole tube, okay, a circuit, between the source and the destination,
and this is only for you, okay. For example, blah, blah, blah, I'm
talking, alright, it goes over there. The, say, digitally encoded signals of my
voice, okay. And you say, blah, blah, blah, it comes
back. When I have nothing to say, you have
nothing to say, silence. Now, this tube, this tube is reserved for
us, whether we are using it or not. And once we're done with this phone call,
you have to tear down the session, like we have to establish it at the time of
initiating the conversation. Now, you can probably already smell
something good about this, for example, quality guarantee, because no one else is
sharing this pipe with you. But, you probably also sense something not
so good for example, what if I'm not using it?
And it takes quite a lot of effort to establish a circuit, and then tear it
down. So, people started in 1960, started
wondering what if we do something called packet switching.
There are three smart ideas behind packet switching.
Number one, let's cut this message into smaller granularities called packets.
13:20
Instead of thinking the whole user or session as one logical unit, I'm going to
think of this as many logical units. Each pack is could be quite small.
Example 100 kilobytes. And the different packets can now actually
go through a different path in this network.
Okay, so you can have multiple paths for the same session.
Okay, some of the packets go this path, some of the packets go this.
So will go this path. And furthermore, each link along each path
is actually possibly shared by many sessions.
Okay, so here's one link. This session goes through this link,
taking up some of capacities. There could be another session going
through this link, taking up another part of this capacity.
14:32
Now, the physical manifestation of a circuit can be, different.
For example, a typical one is you get one time slot.
I get another time slot. You get your slot.
I get my slot. Time slot.
So even when you have nothing to say your time slot is still yours, nobody is using
it. Another one is frequency domain.
Okay. You get this part of the spectrum.
I get that part of the spectrum. And, I will have a dedicated tube between
my source and destination. Graph B In contrast, is a packet switch.
These little blue things are the packets, okay?
15:32
Now this actually is a debate that runs far and deep.
We are talking about circuit versus packet switch.
Back in lecture one, we talk about orthogonal versus non-orthogonal
allocation of radio resources of wireless cellular networks.
For example FEMA or PDMA versus a, a practical CDMA, even though in ideal
situations CDMA is also orthogonal. We will talk about client server versus
P2P in lecture, I guess, fifteen coming up.
16:12
We will talk about local storage in a dedicated machine versus shared and rented
cloud in lecture sixteen. We will talk about in lecture eighteen
contention free, centralized the scheduling in Wi-Fi versus the more often
used random access in Wi-Fi. All these comparison, A versus B,
represent a tension between a dedicated, orthogonal versus a shared a
non-orthogonal resource allocation in a network.
16:51
Well, To those who loves circuit switching or in
general, orthogonal and dedicated resource allocation, say Scott a guarantee of
quality. Okay? Cuz nobody's fighting with you.
As opposed to, in packet switching, you really have no guarantee, unless you
impose a certain particular resource allocation mechanisms on top of the basic
features, as we will see in lecture seventeen, for video traffic.
But, in general, what you have is what the internet community, jokingly, I guess,
called the "best effort". The best effort, here, refers really to,
really, no guarantee on effort. I will try my best.
So when you, you know say can you please tell me this, you know, depending on who's
answering that question if, you know, Bob says I'll try my best and you know the
type of person Bob is, you may say, gee that really means that you can not going
to really try hard at all. And indeed, the Internet, at least IP
layer, does not provide any guarantee on the amount of effort he will provide.
Part of that is because you really cannot guarantee by the design in that layer.
So they call that best effort. And that doesn't imply best result.
So you may say, I love guarantee of quality, so I love circuit switching.
On the other hand, those who like packet switching, would, probably come up with
the top two reasons being the following. Number one, ease of connectivity.
I do not have to, establish one before I can talk.
18:41
I do not have to tear it down. I do not have to maintain the status of
the circuit. Okay.
I can easily establish connectivity. Number two is scale-ability.
We have briefly touched upon this, and in the coming lectures we'll be talking a lot
about scale-ability, in various kinds of technology networks.
In this case scale-ability refers to the efficiency game in packet switching.
There are actually two types of games. Number one is called statistical
multi-plexing. Okay?
It said the following: if Alice's traffic look like this and Bob's traffic look like
that then if I put them together, I'll get some traffic like this.
All right. So I can have this pipe actually serves
two users. Now of course you say well gee, the peak
and the valley actually are exactly complementary between Alice and Bob, no
wonder you can do that. Sure, this is extreme case but imagine in
many cases, if you can put 10000 users together, okay, and they fluctuate in the
traffic demand you will have some gain of the flavor of statistical multiplexing.
But what if they indeed all peak at the same time?
Then you need something like time dependent pricing to smoothen some of that
out and leverage the resulting statistical multiplexity.
That's what we mentioned early on in the last lecture.
So when will this be useful? It will be useful if there's a lot of
dynamic traffic on demand with a lot of burstiness.
If this traffics keeps on going. Okay, even though there's some up and
downs it just keeps on going. Then, you may just say well, let me just
waste a little bit resource and get this pipe to it, but if the traffic is like
this come and then go, come and then go and another one is also like that.
20:51
This is burst of traffic. Okay.
When it arrives then it will arrive with quite a bit of demand, then it will be
silent for a bit of time, then it will come back up again.
For burst of traffic you give a dedicated pipe, then you're guaranteed to loose a
lot of efficiency, all these slots are gone.
The resources are not being fully utilized.
And so for dynamic arguments in there with burst of traffic, you won't, packet
switching, to help you with statistical multiplexing.
Number two reason for efficiency is resource pooling.
This one takes a little more effort. In the homework problem, you will do a
little exercise. Actually, to illustrate, resource pooling
is even important for telephone networks. But you can intuitively understand, if you
go to the cashier, check-out counter of your favorite, your country's favorite
supermarket. You know, say, Walmart.
Right? So there are say three queues, okay, three
cashiers. Okay.
And if there are three separate queues a lot of times you say gee you know, the
other queues are moving so fast and my queue is moving so slow which might be
true or just perception. But you may say this is not fair.
Where as if there is actually one queue to all of them just one queue.
Everybody just queue up here. And when ever there's an available cashier
one can go there, here, here or here. Okay.
22:22
Then you may feel that, this is more fair cuz you know, even if I'm in the wrong
queue it's alright. So similarly you can say that if there's a
certain capacity, Okay? Say this is actually collection of five
cashier counter five, collect, cashier count five, cashier counters and if you
divide them, divide the pipe without allowing them to share the queue then you
may actually have a fully occupied set of counters here and start turning away
people or making them wait even though when the other sets are actually a vacant
cashier counters. Okay?
So, by pulling resource together, you gain some efficiency.
23:09
All right. So, as you can see, this is when you allow
a multiple path and this is when you allow shared links.
These two features of packet switching lead to two different root causes for
efficiency, and thereby scalability afforded by packet switching.
Now, in the end what wins? The guarantee of quality or the ease of
connectivity plus scalability and efficiency.
As you might guess, the ease of connectivity and the scalability and
efficiency won the day, because it pays to at least have a large network to start out
with. And then let's worry about quality of
service with other methods. So packet switching won the day, although
that wasn't entirely clear, even all the way to the late 90s.