Tutor knowledgeComputer NetworksLLM Files / Knowledge Files127 KB
{0}------------------------------------------------
June 12, 2025
In this chapter, we first introduce the concept of network layers where each layer realizes certain services and only communicates with the layer above and below. The layers run on all machines involved in communication.
The most important part discussed in the introduction is the OSI model. You need to know that it has seven layers, with the Session and Presentation layer not really having any protocols associated with it nowadays. For the remaining five layers, you should be able to state their purpose and place in the model:
Last, the introduction mentions an alternative network layer model, , which differs from OSI by a) merging physical and data link layer into one layer and b) not having the session and presentation layer. TCP/IP was designed based on existing protocols while OSI was designed on how protocols should be classified to properly separate the different purposes.
{1}------------------------------------------------
June 12, 2025
The purpose of the data link layer is to a) detect or correct errors made by the physical layer and b) allow multiple parties to share a physical medium. This chapter deals with a) while b) is treated when discussing the MAC-Sublayer. The data link layer acts on a link, so sender and receiver are in the same network.
The data link layer groups data received from the network layer into frames. The three parts we explore in the course are: i) constructing a frame, ii) sending and receiving a frame, and iii) dealing with lost frames.
Constructing a frame: A frame consists of header, payload (body), and trailer. The header has information about the frame, we do not discuss any concrete examples in-depth in this chapter but include some for the MAC-Sublayer. The payload contains the data received from the network layer. Note that data may have to split over multiple frames if there is a maximal frame size, but splitting data is discussed in the context of fragmentation for the network layer and not in this chapter. The trailer contains information that allows detecting or correcting bittlips, a common type of error during transmission. We discuss the following error detection algorithms: parity bit, parity words, checksums, and cyclic redundancy checks (CRCs). For error correction, we discuss parity blocks and Hamming codes. Furthermore, we introduce the concept of burst errors and how they affect the design of error detection/correction algorithms<sup>1</sup>.
Sending and receiving a frame: When sending a frame, the physical layer transmits it bit by bit. When multiple frames are transmitted, the receiver has to be able to tell where one frame ends and the next one starts. Framing methods add information to a frame that enables the receiver to determine the start and end of frames. Byte stuffing and bit stuffing are the framing methods discussed in class.
Dealing with lost frames: Frames can be lost during transmission or discarded at the receiver due to the detection of an error. In both cases, frames need to be retransmitted. In order to trigger retransmissions, receivers send acknowledgments. If an acknowledgment is not received within a certain time after sending a frame, the sender retransmits the frame. Sliding window protocols manage the retransmissions and also ensure that the receiver is not overloaded by limiting the amount of data that can be unacknowledged. We discuss three different sliding window protocols: Stop-and-wait, Go Back N, and Selective Repeat.
The data link layer is the first layer we discuss in class. Thus, we also use this chapter to introduce terminology that is used throughout the course: connection, connection-oriented, connectionless, latency, round trip time, transmission delay, bandwidth, throughput, and goodput. While we will not ask you to define these terms during the exam, you need to know the definition of these terms to solve some of the exercises throughout the course and the exam.
Error detection and correction is treated in the first self-study assignment and not in the lectures
{2}------------------------------------------------
June 12, 2025
This chapter has three parts: First, we introduce general methods for handling collisions that occur on the physical medium. Second, we provide two concrete realizations of physical layer+datalink layer, namely Ethernet and IEE802.11. Last, we introduce how local area networks (e.g., within a home or office) can be realized.
Channel Allocation A collision happens if the transmission periods of two or more frames on the physical medium overlap. The interference caused by a collisions means that the frames are not correctly received and need to be retransmitted. Channel allocation protocols enable parties to share a channel and handle collisions. In all protocols, parties back off after a collision, i.e., they wait a random delay before retrying. We assume dynamic channel allocation, i.e., it should be possible to vary the share of the channel provided to each party over time as demands change. We then differentiate between protocols that have carrier-sense and those that do not. In the second group, we discuss two protocols, namely ALOHA and slotted ALOHA. In the second group, there are a number of carriersense multiple access (CSMA) protocols: 1-Persistent CSMA, Nonpersistent CSMA, and p-persistent CSMA. Furthermore, we state that if devices can detect collisions before they finish transmitting a frame, they should stop as soon as they detect the collision, a variant called CSMA/CD.
After introducing these common protocols, we consider wireless communication and observe that it does not quite fit into the classification of with or without carrier-sense. Concretely, parties can sense whether the medium is in use if the party sending is within their range but not otherwise. This results in the Hidden Terminal Problem where two parties that are not in range of each other send at the same time to a party within range of both of them, causing a collision that could be avoided if there was real carrier-sense. It can also result in parties not sending despite it being possible, the Exposed Terminal Problem. We introduce — Multiple Access Collision Avoidance — to mitigate the issue: Parties send short Ready-to-Send (RTS) and Clear-to-Send (CTS) messages to agree on who is allowed to send, which inform all parties in the ranges of the two communication partners that there is an ongoing communication.
Standardized Protocols We first introduce Ethernet. While we detail how the frames look, the key issue to remember is Ethernet's use of collision detection. Ethernet uses 1-Persistent CSMA/CD with a binary exponential backoff. In order to reliably detect collisions — in contrast to noise on the channel -, Ethernet requires a minimal frame size and hence uses padding if the frame is shorter. Ethernet does not use a sliding window protocol as collision detection leads to automatic retransmission without the need for acknowledgments; bitflips are rare and captured by the higher layers.
Our second protocol discussed in detail is 802.11 (WiFi) but we also shortly mention other wireless protocols. 802.11 uses a Stop-and-Wait protocol. For collision detection, CSMA/CA, Carrier Sense Multiple Access with Collision Avoidance, a variant of MACA. The key modification of MACA is to include the transmission duration to tell others how long the channel will be occupied. RTS/CTS are optional in 802.11. A variant of p-persistant CSMA is applied, with the same binary exponential backoff that Ethernet uses. Depending on the situation, the number of addresses in the frame can vary, as it can be necessary to include both the final destination in a small wireless network and the
{3}------------------------------------------------
party acting as a forwarder. Note that 802.11 has an infrastructure and an ad-hoc mode; the latter does not require wireless routers.
Switched Networks In this part, we consider small local area networks. We introduce the concepts of hubs and switches. The backward learning algorithm enables switches to learn about the network structure by storing information about addresses they have previously seen.
Redundant cabling is used to deal with failures. However, it creates loops in the network. We show an example how such a loop can lead to frames being forwarded repeatedly, eventually causing the network to overload. Afterwards, we introduce the Spanning Tree Protocol, STP, which resolves the issue by building a spanning tree and only uses cables that are links in the tree. If a cable fails, the tree adjusts.
{4}------------------------------------------------
June 12, 2025
In this chapter, we are concerned with how to get data from one party in a network to another party in a potentially different network. For this purpose, we introduce the different parties involved in internet routing: hosts, routers, gateways, autonomous systems, and internet exchange points.
IP protocol The IP protocol uses IP addresses, which are assigned using a 4-step protocol, namely Dynamic Host Configuration Protocol (DHCP). The structure of IP packets for both IPv4 and IPv6 is discussed. The most important fields are the source and destination address, the checksum, and the time-to-live/hoplimit counter. You do not need to remember the exact structure of the packets.
Routing The key part of this chapter lies in the introduction of routing protocols. First, there are general approaches: distance vector routing, path vector routing, link state routing, and hierarchical routing such as CIDR, which are treated in detail. Second, the key idea of the internet routing protocol is that there is intra- and inter-domain routing. Intra-domain routing can vary, depending on the decisions made by the provider. The most common choice is Open Shortest Path First (OSPF), a link state routing protocol. Inter-domain routing applies the Border Gateway Protocol (BGP), a path vector protocol.
Fragmentation The internet is made up of smaller networks, which may vary in the maximum packet size they allow. Fragmentation divides packets in smaller parts, so called fragments, to allow compatibility. We discuss three approaches: Transparent fragmentation, nontransparent fragmentation, and MTU discovery. IPv4 uses nontransparent fragmentation or MTU discovery while IPv6 always uses MTU discovery.
Other Protocols There are more protocols than IP that play a role in the context of the network layer or IP addresses. Internet Control Message Protocol (ICMP) has routers provide information to hosts, i.e., in case of failures. Address Resolution Protocol (ARP) is a datalink layer protocol that enables obtaining a MAC address from an IP. While it acts on the datalink layer, it makes more sense to discuss it in the context of internet routing as it only becomes relevant once IP addresses are involved. Network Address Translation (NAT) allows parties to share one IP address.
Congestion Control Last, we discuss approaches to handle congestion on the network layer. Two concrete protocols are important: Explicit Congestion Notification (ECN), which allows routers to set a bit in the IP header to indicate congestion, and Random Early Detection (RED), which has routers drop packets. Note that congestion control is handled together with the transport layer: the network layer sends signals to which the transport layer reacts, as we discuss in the corresponding chapter.
{5}------------------------------------------------
In this chapter, we consider how end hosts handle the traffic they send to and receive from the network. Depending on how exactly they handle it, they can achieve a reliable data stream between applications or not.
In the beginning of the lecture, we introduce the concept of ports and how ports are mapped to applications. The Berkeley socket primitives are explained as well as concepts such as multiplexing and process servers.
The remainder and majority of the lecture considers concrete transport layer protocols. We note that units of data at the transport layer are called segments and consist of a header and body.
User Datagram Protocol (UDP) is a very thin layer on top of IP that merely includes a header with the source and destination ports as well as the length of the segment and a checksum. Received segments that fail the checksum test are discarded and not automatically retransmitted. So, but for the small chance that the checksum does not not detect an error, UDP ensures that no incorrect data is forwarded to the application but does not guarantee that data arrives.
In contrast, Transmission Control Protocol (TCP) achieves reliability. It sets up a connection using the three-way handshake consisting of a SYN, SYN-ACK, and ACK. Sequence and acknowledgement numbers are used to track how many bytes have been sent and received, respectively. Like UDP, it uses a checksum but it does retransmit: TCP makes use of a sliding window protocol with selective repeat: retransmissions are triggered by a timeout or three duplicate acknowledgements, which act as a negative acknowledgement. TCP chooses an initial sequence number that is different from 0, in order to distinguish segments sent before and after a crash. We introduce clock-based initial sequence numbers as one option to choose the initial sequence number. Furthermore, we explain why sequence number resynchronization is necessary but do not discuss the resynchronization protocol in detail. TCP also terminates connections with a three-way message exchange using the FIN flag if possible. Crashes need to be handled on the application layer.
TCP also implements flow control and congestion control is implemented jointly with the network layer. Flow control is implemented by communicating the window size, i.e., the available space in the buffer at the receiver side, via TCP headers. A TCP client cannot have more unacknowledged data than the window size specifies. For congestion control, TCP has a congestion window that a client maintains locally. Again, the client cannot have more unacknowledged data than the window size specifies. The window initially is a very low value and is then increased exponentially until a threshold. Afterwards, it is increased additively. If the client receives a congestion signal, which are provided by the network layer as discussed in the corresponding chapter, the window is multiplicatively decreased. We illustrate TCP Tahoe and TCP Reno as two concrete congestion control protocols and mention that the congestion control protocol depends on the TCP variant.
{6}------------------------------------------------
June 12, 2025
In this chapter, we introduce various internet applications.
DNS The domain name system (DNS) maps domain names, which are easy to remember and static, to IP addresses. Domain names have a hierarchical structure. The hierarchy in the domain names is mirrored through a hierarchy of names servers, which manage information about domain names corresponding to the part of the name space they are responsible for.
In order to find a corresponding IP addresses, there are two types of DNS lookups: recursive and iterative. In both cases, a client contacts their local name server, e.g., the one provided by their ISP, and requests information about the domain name.
In a recursive lookup, the local name server contacts other name servers to find the IP. When asks for an IP address corresponding to a domain name, a name server either responds with an IP corresponding to the domain or with an IP of a name server lower in hierarchy that is responsible for the domain name. The first name server queried is the root name server that knows about all top-level domains. Caching can be used to speed up the process.
An iterative lookup follows the same principle but the client has to contact the name servers rather than the local name server. The local name server only provides the address of the root name server. DNS uses UDP on the transport layer as it needs to be fast and for that reason, parties cannot set up a connection with every name server involved in the lookup.
Email Emails are handled by transfer agents on email servers. SMTP is used for sending email to a server and between servers. Clients request their emails using IMAP, POP3, a proprietary protocol, or webmail. DNS is leveraged to obtain the IP address of the involved servers.
An email consists of an envelope, which is used to forward the email, a header, which provides information to the receiver about the email, and a body, which is the actual content of the email.
One of the key challenges in using email is that email servers originally only used ASCII and the encoding needs to be used to turn arbitrary binary data (in bytes) into ASCII.
World Wide Web HTTP is used to handle communication with websites whereas HTML is used to render webpages in the browser. HTTP consists of requests and responses, with each response corresponding to a code. We discuss the most common HTTP request types. Webpages are located using Universal Resource Locators (URLs), consisting of the protocol used, the domain name, and the path. The path depends on the server's folder structure.
In order to not establish a new TCP connection for each request, persistent connections are used. Parallel requests are achieved by pipelining (HTTP 1.1) or multiplexing with request identifiers (since HTTP 2). Multimedia content can be handled using browser plugins or separate applications.
Video Streaming Video streaming is challenging as it involves a lot of data, both visual and auditory. Compression algorithms are applied to reduce the data. Moreover, videos consist of a sequence of frames that do often not change much from one frame to the next. As a consequence, there are three types of frames used in video encodings: i) An intra-coded frame contains the full frame
{7}------------------------------------------------
information, ii) a predictive frame only contains changes to the previous frame, and iii) a bidirectional frame contains the changes to the previous and the next frame. Predictive and bidirectional frames are smaller and require less bandwidth.
In contrast to most communication protocols, which primarily are concerned with buffers getting too full and data being dropped, video streaming is also concerned with a buffer being close to empty as an empty buffer leads to stalling. Reliability can be achieved by using TCP or applying error correction on the application layer. Alternatively, in the absence of retransmissions or correction, interleaved media can mitigate the impact of errors.
Live streaming comes at additional challenges to streaming stored media as not all the media is already present at the server. It uses relatively large buffers as it cannot get ahead by downloading faster than the live rate.
Interactive video streaming/calls are even more challenging as large buffers are not an option due to the delays being too large for interactive communication. They usually compromise on the video quality, possibly adjusting it based on the available bandwidths.
Content Delivery Networks In a content delivery network, resources are stored on multiple machines and parties should access machines such that the load is well balanced. Furthermore, they should access resources (geographically) close to them as that reduces latency.
We discuss three ways to manage this: i) static allocation, ii) mirroring, and iii) DNS redirection.
P2P Networks Up to now, we focused on clients communicating with servers. However, servers represent a single point-of-failure, i.e., if they decide/are forced to quit providing a service, the service can no longer be accessed. Furthermore, the server might require a lot of resources and cannot easily increase the resources if the number of users increases. In a Peer-to-Peer network, parties act as both clients and service providers. They have the responsibility to provide a part of the service, e.g., they may be responsible for storing a subset of content and providing it when requested. Ideally, if more peers join, that means a higher load on the network but also more resources, meaning the service scales automatically.
We discuss Napster and Bittorrent and find that in their original form, they still rely on a central server to discover which parties provide a certain service. We show that this server can be replaced by a distributed lookup service called a distributed hash table (DHT), which is actually what modern Bittorrent uses. We introduce one specific DHT, namely Chord. Chord assigns positions in a ring to both files and parties. A party is responsible for the files with ring positions that correspond to the party's position or are right before that position on the ring. Parties then establish connections such that they can find files efficiently by contacting parties they know that are close to the desired files on the ring. They keep track of their connections in a routing table also called the finger table.
Blockchains Blockchains are built on top of peer-to-peer networks and manage a distributed ledger of transactions. Transactions are grouped in blocks. A leader is elected to decide upon the next block. There are various leader election protocols, which we do not detail.
We differentiate three types of blockchains: i) permissionless blockchains, which everyone can actively participate in, ii) public permissioned blockchains, which everyone can read but only a selected set of parties can add transactions to, and iii) private permissioned blockchains, which can only be accessed by a selected set of parties. We introduce criteria to decide whether a blockchain is useful for an application and if so, which blockchain type to choose.
{8}------------------------------------------------
June 12, 2025
In this chapter, cryptography and its applications in the design of network protocols are treated. Security consists of three goals: confidentiality, integrity, and availability. Our focus is on confidentiality and integrity.
Cryptography In the reading assignment, we discuss introductory concepts in cryptography. Ethical issues and disclosure processes are explained, most notable full, responsible, and coordinated disclosure.
The technical part starts with symmetric encryption, also called private-key encryption: Two (or more) communicating parties share a secret key. The two classes of symmetric encryption protocols are stream and block ciphers. Stream ciphers encryot bit-by-bit whereas block ciphers encrypt blockby-block. Block ciphers are a combination of P-boxes and S-boxes. For block ciphers, the mode of operation determines how a sequence of blocks is encrypted to avoid patterns in the ciphertext. We discuss three modes of operation: Electronic Codebook, Cipherblock Chaining, and Counter Mode. Note that nonces/initial vectors are important for both stream and block ciphers to prevent patterns that can be exploited to break the encryption even if the underlying encryption protocol is secure.
In contrast to symmetric encryption, asymmetric encryption, or public-key encryption, relies on two keys: a public key used for encryption and a secret key used for decryption. RSA is an example of asymmetric encryption. We introduce textbook RSA but note that without randomization, it is insecure. Asymmetric encryption is slower than symmetric encryption; thus frequently a combination of the two called hybrid encryption is used. An alternative to hybrid encryption is an interactive key exchange, which requires communication partners to both be online and provide secrets for the key exchange. We discuss Diffie-Hellman key exchange as an example.
Up to now, we focused on confidentiality. For integrity, we introduce two types of algorithms: message authentication codes (MACs) and digital signatures. They both prove to the receiver that a message has indeed been sent by the supposed sender and that the message has not been changed by a third party. MACs use symmetric-key cryptography and hence offer repudiation: each party can deny having sent the message as everyone having the key could have sent it. They are often built from cryptographic hash functions, i.e., hash functions that offer preimage resistance, second-preimage resistance, and collision resistance. Digital signatures, in contrast, use asymmetric cryptography and offer nonrepudiation, i.e., it can be proven who has sent a message. As digital signatures take a long time to compute on longer texts, they are frequently computed on the cryptographic hash of a text, a method called hash-then-sign.
Last, we discuss public-key infrastructures (PKIs), which manage public keys to ensure that people obtain indeed the public key of the party they want to communicate with. We differentiate hierarchical PKIs and the Web-of-Trust.
Wireless Security The goals of a wireless security protocol are i) confidentiality of a message between a client and a router, ii) integrity of a message between a client and a router, and iii) access
{9}------------------------------------------------
control, i.e., only parties knowing the password should be able to access the network.
We introduce how WEP, the first protocol for wireless security, failed at achieving all three of the above goals. Then, we present the high-level idea of WPA (WPA2, WPA3) and sketch how it overcomes the issues of WEP.
Firewalls Firewalls are combined with gateways and protect (company) networks by classifying traffic into allowed and forbidden. Before discussing firewalls specifically, we classify threat detection based on blacklist versus whitelist and signature-based versus anomaly-based detection.
We then explain four types of firewalls: i) packet filter firewalls, ii) stateful firewalls, iii) firewalls with deep packet inspection, and iv) personal firewalls.
Virtual Private Networks (VPNs) A VPN provides confidential and authenticated communication over an untrusted network. Depending on the mode, it can also provide some degree of anonymity. There are two modes: transport and tunnel mode. For company/institutional VPNs, transport mode is used when a employee/member outside of the institutional network communicates with a party within the network or uses services within the network. Tunnel mode is used to communicate between two institutional networks in different locations. Tunnel mode is also used by commercial VPNs to protect the privacy of their clients. Tunnel mode provides anonymity in that anyone using the VPN server/qateway could be the source of the traffic.
There are many VPN implementations. We describe IPSec, which relies on encapsulating IP packets by encrypting and authenticating them. In transport mode, only the payload of the IP packet is encrypted and authenticated. In tunnel mode, both header and payload are encrypted and authenticated and then put into another IP packet using the IP address of the VPN gateway/server in the header instead of the original IP.
Tor VPNs only use one party to proxy traffic, which provides low anonymity as it might be easy to compromise this party. Tor uses multiple intermediaries, called relays or onion routers, to forward traffic. Note that despite the term routers, Tor acts on the transport layer, not the network layer, and onion routers are end hosts. In order for the forwarded content to look different at different parts of the network, Tor uses layered encryption. A variant of Diffie-Hellman key exchange is used to establish shared keys between the source and each relay on the path. The source then encrypts the message with all keys and each relay removes one layer of encryption, a process referred to as onion routing. The protocol discussed above only provides sender anonymity. Hidden or onion services hide the identity of the receiver. For this purpose, both sides — sender and receiver — determine relays that forward their communication. Introduction points facilitate the communication, i.e., they relay information about the sender to the receiver so that the receiver can decide to accept the communication.
Transport Layer Security (TLS) TLS encrypts and authenticates communication between clients and web servers. A hierarchical PKI is used and web servers can pay to obtain certificates. When a client communicates with a website, they first execute a -way handshake: In the first two messages, they decide on the TLS version and the ciphersuite and the web server presents their certificate. They furthermore exchanges nonces that are then used to derive keys. The second two messages are for the key exchange and to verify that both parties now have shared key material.
They then use this key material for a symmetric encryption algorithm combined with a MAC.
DNSSEC We first explain DNS spoofing and DNS poisoning, two common attacks on DNS that lead to incorrect information at the client side, i.e., incorrect IPs for requested domains.
DNSSEC works similar to TLS but does not provide encryption, it merely authenticates the name server. As a consequence, no handshake is required and the protocol can be executed with UDP as the transport layer protocol.
{10}------------------------------------------------
Client Authentication Clients typically do not have TLS certificates as these cost money and clients may not see the reason to spend money. Instead websites uses different factors to authenticate clients divided into three categories: i) something the client knows, ii) something the client possesses, and iii) something the client is (biometrics).
For higher levels of security, multi-factor authentication should be used, i.e., the client has to provide information for more than one of these categories.
Pretty Good Privacy (PGP) PGP is for email encryption. It uses hybrid encryption for confidentiality and hash-then-sign for integrity. Messages are first signed and then the message and the signature are both encrypted. It is possible to only encrypt or sign. Web-of-Trust is used as a PKI.
Off-the-Record Messaging (OTR) Off-the-Record Messaging provides confidentiality and integrity for instant messaging. In contrast to PGP, it provides repudiation.
With every new message, parties also exchange a new key to use in the next message using Diffie-Hellman key exchange. The exchanged keys are for symmetric encryption, a hash of the key is used for a MAC. This hash and hence the MAC key is published after the other party has authenticated the message. In this manner, anyone could have written the (encrypted) message.
{11}------------------------------------------------
January 16, 2023
This document contains the lecture notes for the course CSE14B on error detection and correction. They roughly correspond to Chapter 3.2 of the 5th/6th edition of the book Computer Networks [1]. You can alternatively read the book and Section 3.1 of these notes, which describes the only algorithm not covered in the book.
In contrast to the book, the nodes do not treat convolutional codes, Reed-Solomon codes, and low-density parity checks as they require mathematical tools that are out of scope for this course. Even the book only treats them on a high level without including the details to actually execute the computations. Instead, we introduce a simple error correction algorithm called parity blocks or two-dimensional parity checks.
In terms of structure, the notes start with error detection whereas the book starts with error correction. The change is due to the introduction of parity blocks, which are an error correction algorithm but extend upon concepts used by parity bits and parity words, which are error detection algorithms. Hence, error detection has to be treated first. Furthermore, error detection is slightly simpler, which makes it a more suitable starting point. In the notes, we first discuss the algorithm in general and then give an example. The book interleaves the example with the explanation, so if you prefer that style, starting with the book might be the better option for you. The notes are more concise and have more subheadings, which makes it easier to find something during studying. The book provides more details and historical background, is less dense, and has the benefit of professional editing. The last difference is that the notes have links to videos when a step-by-step discussion in a video seems more appropriate than a written example, giving you the opportunity to make use of different media when studying.
If, after reading this, you are still unsure whether you prefer the lecture notes or the book, I suggest you first try the lecture notes as they condense the content to what is needed for this course. If you find the lecture notes are too condensed and you require more background, you can switch to the book. Even if you switch to the book, the notes may still be useful in studying for the exam due to their condensed form.
Error detection and correction deal with one or multiple bits flipped during transmission from a sender to a receiver. Saying that 'an error occurred' does include the case of multiple bit flips. Such errors are very common on the physical layer if a bit is flipped when being transmitted, especially if the transmission is wireless. Error detection or correction are then applied by the data link layer to provide reliable transmission to the network layer. Furthermore, routers on the network layer may introduce bit flips while relaying data. The transport layer is responsible for detecting and correcting these errors if a reliable data stream is desired.
The difference between error detection and correction is illustrated in Figure 1. Error detection means that the receiver can identify that there has been an error but they are typically not able to
{12}------------------------------------------------
Image /page/12/Figure/0 description: The image shows two diagrams of a phone and a router communicating. In the first diagram, the phone sends the binary code "10101100" to the router, but the router sends back an "ERROR" message. The phone then sends the binary code "10101110" to the router. In the second diagram, the phone sends the binary code "10101100" to the router, and the router sends back the binary code "10101110" to the phone.
(a) Error Detection
(b) Error Correction
Figure 1: Error Detection vs. Error Correction in the example of wireless communication between a phone and a router: The red bit is flipped from during transmission. Error detection recognizes the error and signals the sender to retransmit. Error correction allows the receiver to recover the original message without retransmission.
tell which error occurred. As a consequence, the sender has to be given a signal that they have to retransmit the message. Signals can be explicit requests for retransmission.
Alternatively, receivers may acknowledge correctly received data. If such an acknowledgement is not received within a certain time, the sender retransmits. We discuss multiple options to realize such acknowledgments in the lecture but they are not the topic of this document. In contrast, error correction allows the receiver to identify the exact bit or bits that have been flipped. The receiver can hence correct the error without retransmission.
Choosing an error detection/correction algorithm Note that no algorithm can detect or correct all errors; error detection and correction only considerably reduce the probability of errors to be forwarded to the next higher layer. For this purpose, these algorithms add additional bits, creating redundancy that allows the receiver to detect or correct errors. The number of additional bits added is referred to as the amount of redundancy. Usually this amount of redundancy is given as additional bits per data amount or as a percentage of extra data. For example, consider an algorithm that adds 9 bits to every message of 100 bits. The amount of redundancy is 9 bits per 100 bits or 9%. Instead of amount of redundancy, the term overhead can be used. Note that overhead is not a synonym of amount of redundancy but a more general term that can refer to any additional bits added to the actual message, e.g., information about the protocol version used or flag bytes that indicate the beginning of a frame on the data link layer.
The choice of a suitable error detection or error correction algorithm depends on multiple factors. The higher the amount of redundancy is, the more errors can be detected. However, a higher amount of redundancy means that more data needs to be transmitted, which can cause longer delays or overload the network. If one can tell based on measurements that errors are rare, an algorithm with a low redundancy is hence preferable. Error correction has a lower latency as it does not require retransmission. Yet, for the same amount of redundancy, error correction has a higher chance to accidentally forward an incorrect message than error detection, as we will illustrate on the example of Hamming codes in Section 4.
Content and structure of this document This document considers parity bits, parity words, checksums, cyclic redundancy checks (CRCs), and Hamming codes, as discussed in the book by Tanenbaum and Wetherall [1]. We also include parity blocks for error correction. We first discuss error detection in Section 2 and then error correction in Section 3. So the choice depends on trading off the requirements for error probability, bandwidth, and latency.
For each algorithm, we first discuss the general idea. Afterwards, we detail which parameters the sender and retriever have to agree on to run the algorithm. Note that in practice, the parameter choices are given by the implementation, so interaction for an explicit agreement is usually not needed. The sender and receiver merely have to use implementations with the same parameters. For common protocols such as Ethernet, there is a standard that all implementations have to follow, which includes
{13}------------------------------------------------
the parameters chosen for error detection/correction.
After stating which parameters need to be agreed upon, we discuss the concrete algorithm. We start by describing the action of the sender, followed by the actions of the receiver. Once the algorithm is explained in general, we provide examples and an analysis of the algorithm in terms of amount of redundancy and the amount of errors it can detect and correct. Errors sometimes occur in bursts, i.e., they occur on bits that are subsequent or close to each other in the message rather than on single isolated bits . These errors are caused by effects that last longer than the transmission of a single bit, e.g., bad connectivity due to being too far from a wireless router. Thus, we also discuss how the algorithms introduced here deal with burst errors.
Notes: i) In this document, we assume that bits may be flipped but not lost. Solutions for lost data are treated in other parts of the course. ii) 'They' is used as a gender-neutral singular pronoun (mostly to refer to sender and receiver) as well as a plural pronoun.
Part 1 of 4 — loading the next…