Computer Networks: Crash Course Computer Science #28

0:03 Hi, I’m Carrie Anne, and welcome to CrashCourse Computer Science!

0:06 The internet is amazing.

0:07 In just a few keystrokes, we can stream videos on Youtube— Hello!

0:11 read articles on Wikipedia, order supplies on amazon,

0:14 video chat with friends, and tweet about the weather.

0:17 Without a doubt, the ability for computers, and their users,

0:19 to send and receive information over

0:21 a global telecommunications network forever changed the world.

0:25 150 years ago, sending a letter from London

0:27 to California would have taken two to three weeks,

0:29 and that’s if you paid for express mail.

0:31 Today, that email takes a fraction of a second.

0:33 This million fold improvement in latency,

0:35 that’s the time it takes for a message to transfer,

0:38 juiced up the global economy helping the modern world to move

0:40 at the speed of light on fiber optic cables spanning the globe.

0:43 You might think that computers and networks always went hand in hand,

0:47 but actually most computers pre-1970 were humming away all alone.

0:50 However, as big computers began popping up everywhere,

0:53 and low cost machines started to show up on people’s desks,

0:56 it became increasingly useful to share data and resources,

0:59 and the first networks of computers appeared.

1:01 Today, we’re going to start a three-episode arc on how computer networks

1:04 came into being and the fundamental principles and techniques that power them.

1:08 INTRO The first computer networks appeared in the 1950s and 60s.

1:21 They were generally used within an organization– like a company or research

1:24 lab– to facilitate the exchange

1:26 of information between different people and computers.

1:28 This was faster and more reliable than the previous

1:30 method of having someone walk a pile of punch cards, or a reel of magnetic tape,

1:34 to a computer on the other side

1:36 of a building‒ which was later dubbed a sneakernet.

1:39 A second benefit of networks was the ability to share physical resources.

1:42 For example, instead of each computer having its own printer,

1:45 everyone could share one attached to the network.

1:47 It was also common on early networks to have large, shared,

1:51 storage drives, ones too expensive to have attached to every machine.

1:54 These relatively small networks of close-by computers

1:57 are called Local Area Networks, or LANs.

1:59 A LAN could be as small as two machines in the same room,

2:02 or as large as a university campus with thousands of computers.

2:05 Although many LAN technologies were developed and deployed,

2:08 the most famous and succesful was Ethernet,

2:10 developed in the early 1970s at Xerox PARC, and still widely used today.

2:14 In its simplest form,

2:15 a series of computers are connected to a single, common ethernet cable.

2:19 When a computer wants to transmit data to another computer,

2:22 it writes the data, as an electrical signal, onto the cable.

2:25 Of course, because the cable is shared,

2:27 every computer plugged into the network sees the transmission,

2:29 but doesn’t know if data is intended for them or another computer.

2:33 To solve this problem, Ethernet requires that each computer has a unique

2:36 Media Access Control address, or MAC address.

2:38 This unique address is put into a header

2:41 that prefixes any data sent over the network.

2:43 So, computers simply listen to the ethernet cable,

2:46 and only process data when they see their address in the header.

2:49 This works really well; every computer made today comes with its own

2:53 unique MAC address for both Ethernet and WiFi.

2:55 The general term for this approach is

2:58 Carrier Sense Multiple Access, or CSMA for short.

3:00 The “carrier”, in this case, is any shared transmission medium that carries

3:04 data– copper wire in the case of ethernet,

3:06 and the air carrying radio waves for WiFi.

3:08 Many computers can simultaneously sense the carrier,

3:11 hence the “Sense” and “Multiple Access”,

3:13 and the rate at which a carrier can transmit data is called its Bandwidth.

3:16 Unfortunately, using a shared carrier has one big drawback.

3:20 When network traffic is light,

3:21 computers can simply wait for silence on the carrier,

3:23 and then transmit their data.

3:25 But, as network traffic increases,

3:27 the probability that two computers will attempt

3:29 to write data at the same time also increases.

3:33 This is called a collision, and the data gets all garbled up,

3:35 like two people trying to talk on the phone at the same time.

3:38 Fortunately, computers can detect these collisions

3:40 by listening to the signal on the wire.

3:43 The most obvious solution is for computers to stop transmitting,

3:46 wait for silence, then try again.

3:48 Problem is, the other computer is going to try that too,

3:51 and other computers on the network that have been waiting for the carrier

3:54 to go silent will try to jump in during any pause.

3:56 This just leads to more and more collisions.

3:59 Soon, everyone is talking over one another and has

4:01 a backlog of things they need to say,

4:03 like breaking up with a boyfriend over a family holiday dinner.

4:06 Terrible idea!

4:07 Ethernet had a surprisingly simple and effective fix.

4:10 When transmitting computers detect a collision,

4:12 they wait for a brief period before attempting to re-transmit.

4:16 As an example, let’s say 1 second.

4:18 Of course, this doesn’t work if all the computers use

4:21 the same wait duration— they’ll just collide again one second later.

4:24 So, a random period is added:

4:26 one computer might wait 1.3 seconds, while another waits 1.5 seconds.

4:30 With any luck, the computer that waited 1.3 seconds will wake up,

4:33 find the carrier to be silent, and start transmitting.

4:37 When the 1.5 second computer wakes up a moment later,

4:39 it’ll see the carrier is in use, and will wait for the other computer to finish.

4:43 This definitely helps, but doesn’t totally solve the problem,

4:46 so an extra trick is used.

4:48 As I just explained, if a computer detects a collision while transmitting,

4:51 it will wait 1 second, plus some random extra time.

4:54 However, if it collides again, which suggests network congestion,

4:57 instead of waiting another 1 second, this time it will wait 2 seconds.

5:02 If it collides again, it’ll wait 4 seconds, and then 8,

5:05 and then 16, and so on, until it’s successful.

5:08 With computers backing off, the rate of collisions goes down,

5:10 and data starts moving again, freeing up the network.

5:13 Family dinner saved!

5:14 This “backing off” behavior using an exponentially

5:17 growing wait time is called Exponential Backoff.

5:20 Both Ethernet and WiFi use it, and so do many transmission protocols.

5:24 But even with clever tricks like Exponential Backoff,

5:26 you could never have an entire university’s

5:28 worth of computers on one shared ethernet cable.

5:31 To reduce collisions and improve efficiency,

5:33 we need to shrink the number of devices

5:35 on any given shared carrier— what’s called the Collision Domain.

5:38 Let go back to our earlier Ethernet example,

5:41 where we had six computers on one shared cable, a.k.a.

5:44 one collision domain.

5:45 To reduce the likelihood of collisions,

5:47 we can break this network into two collision domains by using a Network Switch.

5:51 It sits between our two smaller networks,

5:53 and only passes data between them if necessary.

5:56 It does this by keeping a list of what

5:58 MAC addresses are on what side of the network.

6:00 So if A wants to transmit to C,

6:01 the switch doesn’t forward the data to the other network– there’s no need.

6:05 This means if E wants to transmit to F at the same time,

6:08 the network is wide open, and two transmissions can happen at once.

6:11 But, if F wants to send data to A, then the switch passes it through,

6:14 and the two networks are both briefly occupied.

6:17 This is essentially how big computer networks are constructed,

6:20 including the biggest one of all– The Internet–

6:23 which literally inter-connects a bunch of smaller networks,

6:26 allowing inter-network communication.

6:27 What’s interesting about these big networks,

6:29 is that there’s often multiple paths to get data from one location to another.

6:33 And this brings us to another fundamental networking topic, routing.

6:36 The simplest way to connect two distant computers, or networks,

6:40 is by allocating a communication line for their exclusive use.

6:43 This is how early telephone systems worked.

6:45 For example, there might be 5

6:47 telephone lines running between Indianapolis and Missoula.

6:49 If John picked up the phone wanting to call Hank, in the 1910s,

6:52 John would tell a human operator where he wanted to call,

6:55 and they’d physically connect John’s phone line

6:57 into an unused line running to Missoula.

6:59 For the length of the call, that line was occupied,

7:01 and if all 5 lines were already in use,

7:03 John would have to wait for one to become free.

7:06 This approach is called Circuit Switching,

7:07 because you’re literally switching whole circuits

7:09 to route traffic to the correct destination.

7:11 It works fine, but it’s relatively inflexible and expensive,

7:15 because there’s often unused capacity.

7:17 On the upside, once you have a line to yourself– or if you have the money

7:20 to buy one for your private use– you can use it to its full capacity,

7:24 without having to share.

7:25 For this reason, the military, banks and other high importance operations still

7:29 buy dedicated circuits to connect their data centers.

7:32 Another approach for getting data from one

7:34 place to another is Message Switching,

7:35 which is sort of like how the postal system works.

7:38 Instead of dedicated route from A to B,

7:40 messages are passed through several stops.

7:42 So if John writes a letter to Hank, it might go from Indianapolis to Chicago,

7:46 and then hop to Minneapolis, then Billings,

7:48 and then finally make it to Missoula.

7:50 Each stop knows where to send it next because they keep

7:53 a table of where to pass letters given a destination address.

7:56 What’s neat about Message Switching is that it can use different routes,

7:59 making communication more reliable and fault-tolerant.

8:02 Sticking with our mail example,

8:03 if there’s a blizzard in Minneapolis grinding things to a halt,

8:06 the Chicago mail hub can decide to route the letter through Omaha instead.

8:10 In our example, cities are acting like network routers.

8:13 The number of hops a message takes along a route is called the hop count.

8:16 Keeping track of the hop count is

8:18 useful because it can help identify routing problems.

8:20 For example, let’s say Chicago thinks

8:22 the fastest route to Missoula is through Omaha,

8:25 but Omaha thinks the fastest route is through Chicago.

8:27 That's bad, because both cities are going to look at the destination address,

8:31 Missoula, and end up passing the message back and forth between them, endlessly.

8:34 Not only is this wasting bandwidth,

8:35 but it’s a routing error that needs to get fixed!

8:38 This kind of error can be detected because the hop

8:40 count is stored with the message and updated along its journey.

8:43 If you start seeing messages with high hop counts,

8:45 you can bet something has gone awry in the routing!

8:48 This threshold is the Hop Limit.

8:50 A downside to Message Switching is that messages are sometimes big.

8:53 So, they can clog up the network,

8:55 because the whole message has to be transmitted from one

8:57 stop to the next before continuing on its way.

9:00 While a big file is transferring, that whole link is tied up.

9:04 Even if you have a tiny, one kilobyte email trying to get through,

9:07 it either has to wait for the big file

9:09 transfer to finish or take a less efficient route.

9:11 That’s bad.

9:12 The solution is to chop up big

9:14 transmissions into many small pieces, called packets.

9:16 Just like with Message Switching,

9:18 each packet contains a destination address on the network,

9:20 so routers know where to forward them.

9:22 This format is defined by the “Internet Protocol”,

9:24 or IP for short, a standard created in the 1970s.

9:28 Every computer connected to a network gets an IP Address.

9:31 You’ve probably seen these as four, 8-bit numbers written with dots in between.

9:35 For example,172.217.7.238 is an IP Address for one of Google’s servers.

9:41 With millions of computers online, all exchanging data,

9:43 bottlenecks can appear and disappear in milliseconds.

9:46 Network routers are constantly trying to balance the load across

9:49 whatever routes they know to ensure speedy and reliable delivery,

9:53 which is called congestion control.

9:55 Sometimes different packets from the same

9:56 message take different routes through a network.

9:58 This opens the possibility of packets

10:00 arriving at their destination out of order,

10:02 which is a problem for some applications.

10:04 Fortunately, there are protocols that run on top of IP,

10:07 like TCP/IP, that handle this issue.

10:10 We’ll talk more about that next week.

10:11 Chopping up data into small packets,

10:13 and passing these along flexible routes with spare capacity,

10:16 is so efficient and fault-tolerant, it’s what the whole internet runs on today.

10:20 This routing approach is called Packet Switching.

10:22 It also has the nice property of being decentralized,

10:25 with no central authority or single point of failure.

10:28 In fact, the threat of nuclear attack is

10:30 why packet switching was developed during the cold war!

10:33 Today, routers all over the globe work cooperatively to find efficient routings,

10:38 exchanging information with each other using special protocols,

10:41 like the Internet Control Message Protocol

10:43 (ICMP) and the Border Gateway Protocol (BGP).

10:46 The world's first packet-switched network,

10:47 and the ancestor to the modern internet, was the ARPANET,

10:50 named after the US agency that funded it, the Advanced Research Projects Agency.

10:55 Here’s what the entire ARPANET looked like in 1974.

10:58 Each smaller circle is a location,

11:00 like a university or research lab, that operated a router.

11:03 They also plugged in one or more computers– you can see PDP-1’s,

11:07 IBM System 360s, and even an ATLAS in London connected over a satellite link.

11:12 Obviously the internet has grown by leaps and bounds in the decades since.

11:15 Today, instead of a few dozen computers online,

11:18 it’s estimated to be nearing 10 billion.

11:20 And it continues to grow rapidly, especially with the advent of wifi-connected

11:24 refrigerators and other smart appliances, forming an “internet of things”.

11:29 So that’s part one– an overview of computer networks.

11:32 Is it a series of tubes?

11:34 Well, sort of.

11:35 Next week we’ll tackle some higher-level transmission protocols,

11:38 slowly working our way up to the World Wide Web.

11:41 I’ll see you then!