Welcome to lecture thirteen of Networks: Friends, Money, and Bytes.

Now we have been talking quite a bit about social and economic networks.

And we've seen that the predictive power of some of these models can be quite poor,

because it is very difficult to model human beings.

For example, all those demand functions and utility functions we've been talking

about assume that human being will act as a rational agent.

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.

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.

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.

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.

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.

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.

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.

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.

So what's so good about shared path and shared links on multiple paths.

Each link shared by multiple sessions, each session may take multiple path.

We'll see. Now, here's first a pictorial illustration

of that. Graph A is circuit switching.

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?

And also these white ones. Okay.

So some packets traverse one path. Some tra, packets traverse a different

path. And a link, for example this link, can be

shared by multiple, in this case two sessions.

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.

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.

So which one to pick? A or B?

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.

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.

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.

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.

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.

Packet Switching

Networks: Friends, Money, and Bytes

Meet the Instructors