CS | Computer Networks Notes (NO.4)

---

• 1-5 Principle: Packet Switching

  • 1.5.1 What is Packet Switching
  • 1.5.2 Two Consequences
  • 1.5.3 No Pre-flow State Required
  • 1.5.4 Efficient Sharing of Links
  • 1.5.5 Summary

---

1-5 Principle: Packet Switching

1.5.1 What is Packet Switching

When the lnternet was designed, it was based on a controversial and revolutionary idea: packet switching. Nowadays it seems straightforward and the obvious way to build networks. But that wasn't always the case. lt's a very simple idea, but of course as it is with simple ideas, there are many interesting implications that arise once you put itinto practice.

• A self-contained unit of data that carries information necessary for it to reach its destination.
  Packet switching is the idea that we break our data up into discrete, self-contained chunks of data. Each chunk, called a packet, carries sufficient information that a network can deliver the packet to its destination.

So let's say we have asource and a destination, and a network of packet switches A, B, and C between them. When A receives a packet for the destination, it sends it along the link to B. When B receives a packet for the destination, it sends it along to C. When C receives a packet for the destination, it sends it to the destination. In the simplest form of packet switching, each packet is routed separately and independently. For example, let's say there's another switch connected to B, called D. Immediately after sending a packet to C, B can send the nextpacket to D. Or, if the next packet were also to the destination, it would send two packets back-to-back to C.

• Packet switching: Independently for each arriving packet, pick its outgoing link. If the link is free, send it. Else hold thepacket for later.

Here's one example of how packet switching can work: each packet contains an explicit route, specifying the IDs of eachpacket switch along the way. We call this "self routing" or "source routing," because the source specifies the route. When the source sends a packet, it puts in the packet A, B,C, destination. It then forwards the packet to A. A looks inside the header and sees the next hop is B. So it forwards the packet to B. B sees the next hop is C, and C sees the last hop is the destination. It turns out the Internet supports source routing, but it's generally turned off because it raises big security issues. People owning routers don't want you telling them how to send packets, because maybe you can trick them to sending them somewhere they shouldn't, such as secure computers.

• One simple optimization, and what the Internet mostly does today, is to place a small amount of state in each switch which tells it which next hop to send packets to.

For example, a switch can have a table of destination addresses and the next hop. When it receives a packet, it looks up theaddress in the table, and sends the packet to the appropriate next hop. In this model, all the packet needs to carry is the destination address. Using the address, each switch along the way can make the right decision. For example, in our network here, A's table says that packets to destination should go to switch B, switch B's table says packets to destination should go to switch C, and so on.

1.5.2 Two Consequences

Packet switching has two really nice properties.

• The first isthat a switch can make individual, local decisions for each packet. It doesn't need to keep extra state on the packets its seen or whether two packets go to the same destination. Even if many packets are part of some larger transfer or protocol, the switch doesn't need to know or care. The switch doesn't need to know that some packets are a Skype call, others are a web request, and others still are a firmware update for your computer. lt just forwards packets. This greatly simplifies the switch.

• The second is that it lets a switch efficiently share a link between many parties. For example, consider a wireless router in a home with two people browsing the Internet on their laptops. If one person is reading a page, then the other person can download a file at the full speedof the link. If the first person starts loading a new web page, the link can be shared between the two of them. Once the download completes, the first person can use the full speed of the link.

1.5.3 No Pre-flow State Required

Of course when we communicate we don't usually sendonly one packet, we send many; for example a voice call consists of many consecutive packets all part of the same communication. We call this sequence of packets a flow.

More specifically: Flow: A collection of datagrams belonging to the same end-to-end communication, e.g. a TCP connection.

Let's first look at each packet being routed independently.

Because each packet is self-contained, a switch doesn't need to know about groups of packets, or flows of packets. Imagine if every switch had to keep track of every single web connection passing through it. This would require a huge amount of state that would be hard to manage! Instead, treating each packet independently means the switch can be much simpler to build, manage, and trouble shoot.

• The switch doesn't need to worry about adding or removing this per-flow state. Imagine if every time you wanted to loada web page, you had to communicate with every switch along the path to set up state so your request would work. This could make things much slower. Instead, you can just send packets and the switches forward them appropriately.

• The switches also don't need to store this state. Because switches have to be fast, they'd need to store this state invery fast memory, which is expensive. This lets switches focus on doing one thing, forwarding packets quickly.

• Finally, it means switches don't have to worry about failures. Imagine, for example, what happens when you start a web request but then your tablet runs out of energy. The switch is going to keep the per-flow state for the request, but if one of the nodes that created the state fails, the switch needs to know how to clean up after it. Otherwise you can have millions, billions of dead flows eating up your memory. With packet switching, a switch has no per-end point state. If your tablet dies, the switch doesn't care, it just means that it stops receiving packets from it. In this way the switch is more functionally independent of the computers sendingtraffic through it.

1.5.4 Efficient Sharing of Links

Think about how you typically use the Internet - your use isbursty. You load a web page, then read it, then load another one. You download a few songs from iTunes, then listen to them. You stream a show from Netflix for forty five minutes, then stop. Data traffic is bursty: rather than always sending and receiving data at a fixed rate, usage jumps and drops, goes up and down, over time.

While there are large-scale changes and peaks in data traffic - 3PM is typically high, as is 8PM, while 2AM is low, on a smaller scale it is very bursty and these bursts are often independent. Let's say you and your friend are both browsing the web in a coffee shop. When you load a new page and when your friend loads a new page are mostlyindependent. Sometimes they might overlap, but often they won't. By treating all of your traffic as just packets, the wireless router can very effectively and simply share its capacity between you. If you're loading a page while your friend is reading, the wireless router can give all of its capacity to your packets. Similarly, if your friend is loading apage and you're reading, the router can give all of its capacity to your friend's packets. The link doesn't need to go partially idle because one of you isn't using it, and if you're both using it then the link can be shared between you.

This idea of taking a single resource and sharing it across multiple users in a probabilistic or statistical way is called statistical multiplexing. It's statistical in that each user receives a statistical share of the resource based on how much others are using it. For example, if your friend is reading, you can use all of the link. If both of you are loading a page, you receive half of the link capacity.

1.5.5 Summary

So those are the two major benefits of packet switching: it makes the switches simple because they don't need to know about flows of packets.

And second, it lets us efficiently share the capacity among many flows sharing alink. This simple building block was revolutionary at the time, but it's now accepted as the common way to build networks.