Packet Transmission

Unit Goals

Why Packets?

In a network we could:

• Allow two computers to monopolize a shared resource for an arbitrarily long time, making all other computers wait, or
• Arrange for data to be broken up into small blocks called packets which are sent individually (and put back together by the receiver.

Computers take turns sending packets, so packets ensure fairness. They also make it easier to do error detection: it is easier to check individual packets for errors and resend only bad packets, than to check a whole message for errors.

Considerations related to packets:

• Reliable or unreliable
• Connection-oriented or connectionless
• Streamed or out-of-order delivery

Frames

Each hardware technology defines the precise format of its packets. When we have a specific layout we speak of frames, and reserve the term packet for the general concept.

A typical frame has a header and a trailer so that the receiver knows where a frame starts and where it ends. Data stuffing is usually used so that the header and trailer bits do not appear in the data portion of the frame.

Error detection

• Parity
• Checksum
• CRC

How are packets (frames) transmitted? Depends on (1) physical characteristics (hardware) of the network and (2) the network topology.

Local Area Networks (LANs)

LANs are characterized by nodes in geographical proximity that uses a single shared communications medium. This is cheaper than point-to-point (mesh) networks.

LAN Topologies

The term topology refers to the general shape of a network. Examples:

To coordinate shared access, bus-based LANs need to employ CSMA/CD or CSMA/CA or other such techniques; rings might pass tokens around.

Examples of LANs

• Ethernet
• LocalTalk
• FDDI
• Token Ring

Wide Area Networks (WANs)

WANs can span many continents. Unlike LANs, these tend not to have a single shared communications medium because they'd spend more time coordinating access to the medium than sending data. WANs are built from packet switches.

Each packet switch performs store and forward packet switching. Each packet switch has a routing table. Routing is source-independent and cares only about the "next hop." WANs can use static or dynamic routing. The routing tables are usually filled by running Dijkstra's algorithm to compute shortest (least-cost) paths.

Examples of WANs

• ARPANET
• X.25
• Frame Relay
• SMDS
• ATM

Four Sources of Packet Delay

• Processing at the Node: Node have to compute CRCs or checksums to detect bit errors, and compute the link for the next hop
• Queueing: If router is congested a packet might wait a long time before it can be processed or transmitted
• Transmission: packet length in bits divided by link bandwith in bits per second
• Propagation: Length of physical link / medium propagation speed

Classwork: A 10-car caravan traveling at 100 km/hr has to pass through a toll booths that handle each car in 12 seconds. There are 100km between toll booths. How long does it take to get the entire caravan from one tollbooth, which begins just before one toll booth, through it and then through the next one?

Packet Switching vs. Circuit Switching

Most computer networks are packet switched as opposed to circuit switched. Circuit switching gives you a dedicated, pre-routed, path between the two parties; packet switching breaks up the message into packets and routes them all independently throughout the network.

In theory, packet switching allows many more users to be on the network at the same time.

What’s the biggest difference bewteen packet switching and circuit switching?

In circuit switching, within a session, all information flows between the source and target flows through the exact same intermediate points. In packet switching, each of the packets in a session can be routed independently.

Circuits are not exclusive

A common misconception is that once a circuit is set up, only one source-target pair can use the circuit. This is not true. A circuit can be shared, either with frequency multiplexing or time multiplexing. But there are is generally a fixed, maximum number of concurrent, multiplexed sessions.

With circuit switching, a good portion of a link may be idle. Packet switching handles bursty data really well. Packet switching is simpler, there’s less overhead in setting up and maintaining a circuit (routers can pretty much be dumb). But packet switching can have congestion; packets can get delayed or even lost; we need software protocols for congestion control and reliable transfer (retransmission, sorting, etc.) It’s hard to give bandwith guarantees for say, audio or video applications. Performance is impacted by congestion, loss, delays, variation on throughput for different links, and the time it takes to reassemble streams from out-of-order packets and the time it takes to retransmit lost packets.

There are so many random variables here. How does one do the math?

Answer: Queueing Theory.

Jacob Aae Mikkelsen has some great notes on throughput you might like to check out.

Summary