Introduction to Computer Networking
Here we look at the most basic features of networking and packets.
- Computer Networks are like a phone system for computers
- A "call" is just sending data between computers
- Basic outline is surprisingly simple, complex details
- Worth knowing the basics, you use this constantly
The details of networking -- like anything really -- can be quite complicated. But the basic ideas of how it all works are surprisingly simple, and that's what we're going to study.
The Internet is like a global phone system for computers: a computer can "call" another computer on the internet to get or send a little information. Suppose your laptop is connected to the internet, and you type "http://www.nytimes.com" into your browser -- what happens? Your computer contacts the computer "www.nytimes.com" -- placing a "call" in effect -- and sends a request for the main web page. The request is small, about 1KB (1 kilobyte). The www.nytimes.com machine sends back a large response which is the web page -- maybe 200KB -- and ends the call. Your browser gets back all this data and formats it for your screen so you can read the text, click links etc. We'll look at this fetch-web-page example a few different ways to see how the internet works.
LAN - Local Area Network
- Start with small scale
- LAN - Local Area Network
- One house, one floor of a building
- Later, show scale up to world-wide internet
- e.g. Ethernet, wired LAN
- e.g. Wi-Fi, wireless LAN
We'll start by looking at LAN (local area network) technology -- connecting 2-50 computers in a house or on one floor of a building.
- Very ubiquitous wired LAN technology
- Wires about as thick as a drinking straw
- 100 meter max wire length -- local
- Wires often yellow or blue
- RJ-45 plug, like a big phone plug
Ethernet RJ45 plug
Ethernet cables plugged into the back of a Wi-Fi router (Linksys WRT54g)
Ethernet is an extremely common and influential wired LAN standard, so we'll start there. Ethernet cable lengths are typically limited to 100 meters, in keeping with its "local" orientation. A typical LAN application is networking the computers in one room or in one floor of a building. The most common form of ethernet wiring is 100base-T (100 megabit) with "RJ-45" connectors on the ends. An RJ-45 connector is about the size of your pinkie finger, like a wide phone wire plug.
Packets - Data From Here to There
- Send image from one computer to another on ethernet
- This is the "one hop" case (scale up to whole world later)
- e.g. 50KB image.jpg
- 50,000 bytes
- How to send the image.jpg on the wire?
- Divide bytes of image.jpg into packets
- Say each packet is 1500 bytes (varies)
- Then image.jpg divides into about 32 packets
- Ethernet: transmit one packet between computers
We'll start with the simplest case of two computer connected with an ethernet cable, and we want to send a 50KB jpeg image file from one computer to the other. This is the "one-hop" case .. networking between two computers separated only by an ethernet cable. Later we'll scale this up to the full Internet case of two computers on separate sides of the world. The first question is: how are the bytes of the image file on one computer sent to the other computer over the ethernet cable (or over Wi-Fi)?
For transmission, the 50KB of the image is divided into packets. The packet is the natural unit of transmission within networking. In this case, say each packet is about 1500 bytes (a typical packet size), then the bytes of the 50KB image could be divided into about 32 packets of around 1500 bytes each. It is not required that all the packets be the same size, just that every byte of the image is sent in one packet or another.
Ethernet -- Sending One Packet
- Look at transmission of one 1500 byte packet
- Each byte is 8 bits, e.g. 0 1 1 0 1 0 1 0
- Send each byte (slight simplification):
Go through 0/1 bits, from left to right
--For each 1, put 3 volts on the wire
--For each 0, put 0 volts on the wire
--Follow along the pattern of 3 volts / 0 volts coming down the wire
--Assemble the 0's and 1's to make each byte
- digital transmission - just 0's and 1's
- Happens at about 1/3 the speed of light in the wire
Ethernet provides a basic facility to transmit a packet between two computers connected by the ethernet cable. Say we have a packet of 1500 bytes of information we want to send. Each byte is 8 bits, so that's 12000 bits to send, where each bit is a 0 or 1. Here's an oversimplification that captures how it works: the ethernet cable contains two wires connecting the computers. The sending computer could read through the 12000 bits in order, and for each 1 bit, put 3 volts between the wires, and for each 0 bit, put 0 volts between the wires. The receiving computer can follow along, noting the 3v/0v pattern on the wires over time and so receive the 12000 bits. In reality the most recent ethernet contains 4 pairs of wires and supports sending information in both directions and with a more complex voltage scheme. However, this pattern of going through the bits and varying the voltage to "send" each bit is essentially how it all works.
Checksum vs. Errors
- 1 Gigabit - 1 billion bits per second
- Detect the occasional error
- Checksum - receiver can detect that the packet was received correctly
- Example checksum scheme:
--Sender adds up all packet's bytes, say the sum is 157231
--Take the last 2 digits, 31, as the "checksum" of the packet
--Sender appends the checksum at the end of the packet
--Receiver: add up the bytes received, check that the checksum matches
Checksum not matching indicates data corruption
Receiver asks the sender to re-send that packet
- Very likely to detect errors
- Not perfect - 2 errors could cancel out
- Actual checksum schemes used are better than just the sum
- Checksums are widely used in computer systems
- How your file transfers get every bit correct
Each packet includes extra checksum bytes, so the receiver of the packet can detect if some of the bits in the packet got corrupted in transmission. A simple example checksum scheme would be: go through all the bytes, and add them all up. The checksum is the last 2 digits of the sum of all the bytes; send that checksum as an extra byte along with the rest of the packet data. The receiver can do the same computation -- adding up all the bytes -- to check that they get the same checksum. The actual checksum algorithm is more complex than just adding up the bytes, and is more capable of detecting errors. The checksum is probabilistic, not detecting 100% of errors; there is a microscopic chance that an error occurs but the checksum does not catch it.
The checksum allows the receiver to notice that a packet did not come through right, and get the sender to re-send that packet. Most packets get through fine, but re-sending a few packets happens all the time in your life. In this way, when you send a JPEG file from one place to another, it comes through correctly, down to every last bit.
Multiple Computers -- Ethernet Design
- Ethernet -- historic, elegant design
- One wire shared by all the computers
- No central control -- distributed, collaborative
- Like talking at a party
- Suppose one computer wants to send to another on the wire
- How to send:
--Every computer has a unique address on the wire
--Packet includes to:addr of recipient
--Sender waits for period of silence on the wire, sends packet
--Packet spreads out on wire, reaching all computers
--More "broadcast" than "send"
--All computers listen to the wire all the time
--Pick out packets addressed to them, ignore other packets
- "Collision" happens in rare cases
- Two computers transmit at the same time
- --Data collides on the wire, hopelessly garbled
- --Senders notice the collision, stop sending
- --Both senders wait a random amount of time, then try again
- --What if both senders tried to send again immediately?
Ethernet, even in its original simple form, is an interesting and elegant design for a LAN network, connecting a bunch of local computers together with one shared wire. It demonstrates the paradigm of getting many actors to collaborate without any central control. Ethernet was created by Bob Metcalfe at Xerox PARC in 1975. Here is how the original Ethernet worked, although newer versions are more complex and have higher performance.
- There is one wire, and all the computers are connected to it -- they share the wire -- this is what makes it "broadband" as they all share the one medium. This is a simple and cheap configuration; the computers just connect to a dumb, shared wire. To add a computer, just connect it to the wire.
- Each computers on the LAN has a unique address. This is know as its MAC address (Media Access Control). The MAC address is burned in at the factory, thankfully not something you need to set or maintain manually.
- Only one computer should transmit at a time
- All computers listen to the wire all the time, picking up packets addressed to them and ignoring packets not for them
- To send data, the sender divides their message into small "packets" of, say, around 1500 bytes. Every packet begins with the address of the recipient.
- To send, the sender listens, waiting for a period of silence on the wire. When there's a period of silence, the sender sends their packet on the wire, effectively broadcasting it over the whole wire.
- Sometimes two senders send at the same time, and so their packets "collide" on the wire and get garbled. The network hardware can usually detect this "collision" and so know to stop transmitting, as those sends are ruined.
- The senders follow a "wait/re-transmit" protocol to re-send packets -- wait a random amount of time after a collision -- one of Metcalfe's breakthrough ideas -- and then try again when the wire is quiet. If the senders each tried to re-send immediately, the sends would just collide again! By waiting a random amount of time, the two senders coordinate that one goes first, then the other.
- If we have multiple computers using the network at the same time .. this all makes ethernet a little unpredictable in terms of performance; it's hard to say precisely how long it's going to take to get a packet through. In practice, it works incredibly well, getting great performance with very little networking hardware.
Wi-Fi -- Same Strategy
- Wi-Fi wireless networking
- Similar strategy to Ethernet (simplifying)
--Every computer has a radio
--The radio-channel used is the shared medium
--One computer transmits at a time
Ethernet Design Summary
Ethernet is a nice example of getting multiple distributed actors to collaborate without relying on a central authority. This theme re-appears at the larger, world wide internet scale.
- Shared -- there's just the one wire and everybody uses it (cheap)
- Distributed and Collaborative -- no central control, depends on each computer following the collaborative protocol in good faith
- Insecure -- not to hard to listen and pick up packets not intended for you (shared)
- Performance degrades but does not break as more computers use the shared medium
- Incredibly successful design strategy -- getting great performance out of minimal hardware
- Wi-Fi is very similar