14175274
Description
Flashcards by Julian Rottenberg, updated more than 1 year ago
|
Created by Julian Rottenberg
about 6 years ago
|
|
| Question | Answer |
| The Link Layer's Service | |
| Options for Link Layer Service (Reliable) | - Reliabel (dependable) service - yes/no -> Reliablity has many facets --> A delivered packet should have the same content as the transmitted packet --> All packets have to be delivered eventually --> Packets have to be delivered in order |
| Options for Link Layer Service (Error control) | - Error control may be required -> forward errror correction, or backward error corrections with acknowledgements or retransmissions |
| Distringuish: Service Versus Implementation | - One example: -> Connection-less & reliable service required by the network layer -> Link layer decides to use connections internally as a means to help with error control |
| Basic Link Layer Functions - Framing | |
| Basic Link Layer Functions - Error Control | |
| Basic Link Layer Functions - Connection Setup | - Connections useful for many purposes -> application context -> Error control - several error control schemes rely on a common context between sender and receiver |
| Basic Link Layer Functions - Flow Control | - What happens with a fast sender and a slow receiver? -> Sender will overrun buffers faster than the receiver can process the packets in that buffer -> Lots of transmission effort is wasted in this caase - Necessary to control the amount of frames a link layer send per unit time, adapt to receiver's capabilities |
| Framing | |
| Framing by Character Counting | |
| Basic Technique: Put Control Data into a Header | |
| Framing by Flag Bytes/Byte stuffing | |
| Framing by Flag Bit Patterns / Bit Stuffing | |
| Framing by Coding Violations | |
| Error Control (basic aspects) | - Detect the presence of errors (incorrectly received bits) in a frame - Correct error frames |
| Error Control (Detect, but do not correct) | - detect, but do not correct -> simply drop a frame; pretend that it never has arrived at the receiver --> Higher layers can take corrective measures, if they so desire |
| Error Control (Correct, but do not detect) | - try to correct as many errors as possible but do not care if there are some remaining errors present -> only feasible if application is not (too much) borthered by errors -> Example: voice applications can tolerate some degree of bits errors without loosing too much voice quality -> justifiable, since even with detection the residual error probability is always > 0 |
| Error Detection | EDC = Error Detection and Correction bits (redundancy) D = Data protected by error checking, may include header fields - Error detection is not 100% reliable: -> Protocol might miss some errors, but rarely -> Larger EDC field yields better detection and correction |
| Error Detection (Bild) | |
| Error Control - Redundancy (1) | |
| Error Control - Redundancy (2) | |
| How Do Illegal Messages Help With Detecting Bit Errors? | - Transmitter only sends legal frame - Physical medium/receiver might corrupt some bits |
| How Do Illegal Messages Help With Detecting Bit Errors? (Hope) | - Hope: A legal frame is only corrupted into an illegal message -> But one legal frame is never turned into another legal frame |
| How Do Illegal Messages Help With Detecting Bit Errors? (realizing hope) | - necessary to realize hope: -> Physical medium only alters up to a certain number of bits (by assumption) - say, k bits per frame --> This is only an assumption! -> Legal messages are sufficiently different so that it is not possible to change one legal frame into another by altering at most k bits |
| Altering Frames by Changing Bits | |
| Simple Redundancy Examples: Parity (1) (Odd parity) | - Parity is used as a simple rule to construct 1 redundant bit (i.e. n=m+1) - Odd parity: Add one bit, choose its value such that the number of 1's in the entire message is odd |
| Simple Redundancy Examples: Parity (1) (even parity) | - Parrity is used as a simple rule to construct 1 redundant bit (i.e. n=m+1) - Add one bit, choose its value such that the number of 1's in the entire message is even |
| Simple Redundancy Examples: Parity (1) (Example) - Original message without redundancy: 01101011001 - Odd parity: ?? - Even parity: ?? | - Odd parity: 01101011001*1* - Even parity: 01101011001*0* (die Zahll zwischen * ist der Teil, der sich ändert |
| Simple Redundancy Examples: Parity (2) - Send 1 0 1 1 0 0 0 in even parity | - There are three 1's in this - To make this even parity a 1 is added to the end (=> total four 1's) - 1 0 1 1 0 0 0 1 is transmitted by the sending computer |
| Simple Redundancy Examples: Parity (2) - Send 1 0 1 1 0 1 0 in even parity | - There are four 1's in this - to keep this even parity a 0 is added to the end - 1 0 1 1 0 1 0 0 is transmitted by the sending computer |
| Simple Redundancy Examples: Parity (2) (even parity expectations) | - The destination computer always expects an even number of 1's: --> If there is not an even number of 1's arriving, then the frame has been corrupted |
| Simple Redundancy Examples: Parity (3) (Parity bit problems + how to solve them) | - Even and odd parity works well to detect single bit errors - but it can't detect all possible errors - to detect more errors (i.e. even number of bit errors), a checksum or a cyclic redundancy check is needed |
| Simple Redundancy Examples: Parity (3) (Parity bit probolems - Example) | - for example: consider when transmission errors cause two bits to be changed: --> if 1 0 0 1 1 0 1 0 is sent but two bits get changed during transmission --> The destination computer receives 0 1 0 1 1 0 1 0 and does not realise that there were errors during transmission |
| Simple Redundancy Examples: Checksum (1) (Checksums) | - To compute a checksum, the sending computer treats the data as a sequence of binary integer and computes their sum. - Not that the Data Link Layer treats the data as a sequence of integers for the purposes of computing a checksum |
| Simple Redundancy Examples: Checksum (1) (Checksum example) | |
| Simple Redundancy Examples: Checksum (2) | |
| Distance Between Frames | |
| Hamming Distance of a Set of Frames | |
| Hamming Distance and Error Detection/Correction | |
| Hamming Distance and Detection/Correction | |
| Hamming Distance and Detection/Correction | |
| Generalization - Required Hamming Distances (detect) | - To detect d bit errors, a Hamming distance of d+1 in the set of legal frames is required --> So that it is not possible to re-write a legal frame into another one using at most d bits |
| Generalization - Required Hamming Distances (correct) | - To correct d bit errors, a Hamming distance of 2d+1 in the set of legal frames is required --> So that all frames that are at most d bits away from a legal frame are illegal and are more than d bits away from any other legal frame |
| Frame Sets - Code Booke, Codes (terminology aspect - code book / code) | |
| Frame Sets - Code Books, Codes (teminology aspect - R) | |
| Frame Sets - Code Books, Codes (terminology aspect - | |
| Frame Sets - Code Books, Code | - A good code should have large distance and large rate - but arbitrary combinations are not possilbe --> For details: Information theory, Claude Shannon |
| How to Construct Error Correcting Codes | - Constructing good codes (e.g. highest reate at given error correction needs) is difficult |
| How to Construct Error Correcting Codes (simple example) | - Use several parity bits --> Distribute the parity bits over the entire codeword to protect against burst errors |
| How to Construct Error Detecting Codes - CRC | - Efficient error detection: Cyclic Redundancy Check (CRC) |
| How to Construct Error Detecting Codes - CRC (CRC) | - Gives rules how to compute redundancy bits and how to decide whether a received bit pattern is correct --> Very high detection probablility with few redundancy bits --> Can be efficiently implemented in hardware |
| How to Construct Error Detecting Codes - CRC (basic operation bassed on polynomial arithmetic) | - Basic operation based on polynomil arithmentic --> Bit string is interpreted as representing a polynomial --> Coefficients 0 and 1 are possible, interpreted modulo 2 |
| Modulo 2 Arithmetic | |
| Modulo 2 Division | - Division of two numbers is done just like normal division: --> Subtracdt the denominator (the bottom number) from the leading parts of the enumerator (the top number) --> Proceed along the enumerator until its end is reached --> Remember that we are using modulo 2 substraction - After division, a remainder may result |
| Modulo 2 Division (Number example) ** | |
| Modulo 2 Division With Remainder (Number example) ** | |
| Polynomials Over Modulo 2 Arithmetic | |
| Bit Strings and Polynomial Modulo 2 (Idea) | - Idea: Conceive of a string of bits as a representation of the coefficients of a polynomial |
| Bit Strings and Polynomial Modulo 2 | |
| Use Polynomials to Compute Redundancy Bits - CRC (1) | - Define a generator polynomial G(x) of degree g --> Known to both sender and receiver --> We will use g redundancy bits in the end |
| Use Polynomials to Compute Redundancy Bis - CRC (2) | |
| CRC Transmission and Reception (What happens in the channel after transmitting T(x)? - No errors) | - No errors: T(x) arrives correctly at the receiver |
| CRC Transmission and Reception (What happens in the channel after transmitting T(x)? - Bit errors) | - Bit errors occur: T(x) is modified by flipping some bits --> Equivalent to modifying some coefficients of the polynomial --> Equivalent to adding an error polynomial E(x) --> At the receiver, T(x) + E(x) arrives |
| CRC Transmission and Reception (At the receiver) | |
| CRC - Overview | |
| Choice of G(x) Determines CRC Properties (When is remainder of E(x) / G(x) != 0?) | - If G(x) divides E(x) without remainder, an error slips through! |
| - G(x) needs two or more terms to ensure that E(x) is not a multiple of it | |
| Choice of G(x) Determines CRC Properties (Odd number of errors) | - E(x) has an odd number of terms -> E(x) will NOT have (x+1) as a factor -> Make (x+1) a factor of G(x) so that it cannot divide E(x) Using r check bits, all burst errors of length < r can be detected (as well as "most" burst errors of length >= r) |
| Commonly Used CRC Generator Polynomials | |
| How to Handle Detected Errors? | - Suppose the receiver detects an error - Clearly, the received frame cannot be delivered to higher layers/application -> Have to repair the error somehow |
| How to Handle Detected Errors? (Forward) | - Sender sends redundant information so that receiver can correct "a couple of" errors (requires advanced coding techniques) |
| How to Handle Detected Errors? (Backward) | - Sender sends redundant information so that receiver can detect errors with high probability and upon detection of an error, packets are retransmitted |
| How to Handle Detected Errors (ARQ) | - Backward correction protocols are generally known under the name "Automatic Repeat Request" (ARQ), denoting three main variants -> Send and wait -> Go-Back-N -> Selective reject (selective retransmission) |
| A Simple, Simplex, Acknowledgement-Based Protocol | |
| Acknowledgment-Based Protocol, Second Trial (Cure one Problem) | - Cure one problem: Concentrate on one packet, only accept the next packet from higher layer when previous one has been fully processed |
| Acknowledgment-Based Protocol, Second Trial (first solution attempt) | |
| Acknowledgement-Based Protocol, Second Trial - Does Second Version Work Correctly? | - It holds back the transmitter until packets are processed -> It implements flow control! => Simple cases seem ok |
| Acknowledgement-Based Protocol, Second Trial - Does Second Version Work Correctly? (Does it ensure that all packets arrive, in correct order?) | |
| Acknowledgement-Based Protocol, Second Trial - Does Second Version Work Correctly? (What if an acknowledgment is lost?) | |
| Acknowledgement-Based Protocol, Second Trial - Does Second Version Work Correctly? (Summary of Second Version: Send and Wait) (1) | - Sender transmits one single packet -> Sender sets timeout -> Sender waits for acknowledgement (ACK) -> If no ACK is received within timeout, the sender retransmits the packet |
| Acknowledgement-Based Protocol, Second Trial - Does Second Version Work Correctly? (Summary of Second Version: Send and Wait) (2) | - If a received packet is damaged, the receiver simply discards it - Often, this scheme is also referred to as "Stop-and-Wait" as the sender stops transmitting after each packet |
| Acknowledgement-Based Protocol, Second Trial - Does Second Version Work Correctly? (Summary of Second Version: Send and Wait) (3) | - If the ACK packet is damaged, the sender will not recognize it: -> Sender will also retransmit the packet -> Receiver gets two copies of packet |
| Overcoming the Problem of Send and Wait (Problem - Sender) | - Sender can't distinguish between a lost packet and a lost acknowledgement -> Has to re-send the packet |
| Overcoming the Problem of Send and Wait (Problem - Receiver) | - Receiver cannot distinguish between a new packet and a redundant copy of an old packet -> Additional information is needed |
| Overcoming the Problem of Send and Wait (Solution) | - Put a sequence number in each packet, telling the receiver which packet it is -> Sequence numbers as header information in each packet -> Simplest sequence number: a 0 or 1 ! - Needed in packet & acknowledgement -> In Ack, convention: send the sequence number of the last correctly received packet back --> Also possible: send sequence number of next expected packet |
| Acknowledgements & Sequence Numbers - 3rd Version | |
| Assessment of 3rd Version - Altering Bit Protocol (1) | - correct implementation of a reliable protocol over a noisy channel -> Name: Altering bit protocol -> Class: Automatic Repeat reQuest (ARQ) protocols (sender waits for a positive confirmation) -> It also implements a simple form of flow control |
| Assessment of 3rd Version - Altering Bit Protocol (2) | - Note the dual task of the acknowledgement packet --> It confirms to the sender that the receiver has obtained a certain packet --> It is also the permit to send the next packet, stating that the receiver has the capacity to handle it --> These two functions can be and are separate in other protocols |
| Alternating Bit Protocol - Efficiency | |
| Improving Efficiency - Have More "Outstanding" Packets (1) | - Inefficiency of alternating bit in large bandwidth-delay situations is owing to not exploiting "space" between packet and acknowledgement |
| Improving Efficiency - Have More "Outstanding" Packets (2) | - Always sending packets results in high efficiency --> More packets are "outstanding" = sent, but not yet acknowledged --> "pipelining" of packets |
| Improving Efficiency - Have More "Outstanding" Packets (3) | - But not feasible with a single bit as sequence number => Need larger sequence number space! --> It also needs - ideally - some full-duplex support |
| Improving Efficiency - Have More "Outstanding" Packets (Bild) | |
| Sliding Windows to Handle Multiple Outstanding Packets | - use sliding windows at both sender and receiver to handle these numbers - for a larger sequence number space (n bits or 2^n sequence numbers -> not all of them may be allowed to be used simultaneously (=> like alternating bit case) |
| Sliding Windows to Handle Multiple Outstanding Packets (Sender) | - Sender: sending window - set of sequence numbers it is allowed to send at given time -> may be fixed in size or adapt dynamically over time -> Window size corresponds to flow control |
| Sliding Windows to Handle Multiple Outstanding Packets (Receiver) | - Receiver: receiving window - set of sequence numbers it is allowed to accept at given time -> may be fixed in size or adapt dynamically over time -> Window size corresponds to flow control |
| Sliding Window - Simple Example | |
| Transmission Errors and Receiver Window Size (Assumption) | - Link layer should deliver all frames correctly and in sequence - Sender is pipelining packets to increase efficiency |
| Transmission Errors and Receiver Window Size (Bild) | |
| Go-Back-N (receiver window size 1) | - With receiver window size 1, all frames following a lost frame cannot be handled by receiver -> They are out of sequence -> they cannot be acknowledged, only ACKs for the last correctly received packet can be sent |
| Go-Back-N (timeout) | - Sender will timeout eventually -> Since all frames sent in the meantime, they have to be repeaed -> Go-Back N (frames)! |
| Go-Back-N (Assessment) | - Assessment -> Quite wasteful of transmission resources -> But saves overhead at the receiver |
| Selective Reject (Selective Repeat) | |
| Duplex Operation and Piggybacking (so far) | - So far, simplex operation at the (upper) service interface was assumed -> The receiver only sent back acknowledgements, possibly using duplex operation of the lower layer service |
| Duplex Operation and Piggybacking - What happens when the upper service interface should support full-duplex operation? (One option) | - Use two separate channels for each direction -> wasteful |
| Duplex Operation and Piggybacking - What happens when the upper service interface should support full-duplex operation? (better option) | - Interleave acknowledgement and data frames in a given direction |
| Duplex Operation and Piggybacking - What happens when the upper service interface should support full-duplex operation? (best (and usual) option) | - Put the acknowledgement information for direction A -> B into the data frames for B -> A => As part of B's header - piggyback it |
| Performance: Error-Free Send and Wait (1) | |
| Send and Wait Link Utilization | |
| Performance: Error-Free Send and Wait (2) | |
| Performance: Send-and-Wait ARQ with Errors | |
| The Parameter a | |
| Stop-and-Wait Timing (transmission time = 1; propagation time = a) | |
| Performance of Send and Wait | |
| Performance: Error-Free Sliding Windows ARQ (1) (what is W) | - Let W be the number of frames that the sender can send, before he has to wait for an acknowleadgement |
| Performance: Error-Free Sliding Windows ARQ (1) (Case 1 & 2) | |
| Timing of Sliding-Window Protocol | |
| Performance: Sliding Windows Utilization as Function of a (y-Achse = Utilization x-Achse = a) | |
| Performance: Normalized Throughput in Case of Errors | |
| Performance: ARQ Utilization as Function of a | |
| Performance: ARQ Utilization as Function of W | |
| Conclusions - Data Link Layer (Errors) | - Most problems in the link layer are due to errors -> Errors in synchronization require non-trivial framing functions -> Errors in transmission require mechanisms to correct them so as to hide from higher layers -> Or to detect them and repair them afterwards |
| Conclusions - Data Link Layer (Flow Control) | - Flow control is often tightly integrated with error control (and sometimes also congestion control) in practical protocols -> But it is a separate function and can be realized separately as well |
| Conclusions - Data Link Layers (error control scheme) | - Choice of error control scheme (and its parameters) has implications on achievable performance |
| Conclusions - Data Link Layers (Connections) | - Connection setup/teardown still has to be treated -> Necessary to initialize a joint context for sender and receiver (e.g. initial sequence numbers, window size) |
| Chapter 10 | Chapter 10 |
| Security Objectives of IPSec (IPSec aims to ensure the following security objectives) (Data origin authentication/connectionless data integrity) (Replay protection) | - It is not possible to later replay a recorded IP packet without the receiver being able to detect this |
| Security Objectives of IPSec (IPSec aims to ensure the following security objectives) (Confidentiality) | - It is not possible to eavesdrop on the content of IP datagrams - Limited traffic flow confidentiality |
| Security Objectives of IPSec (Security policy) | - Sender, receiver and intermediate nodes can determine the required protection for an IP packet according to a local security policy - Intermediate nodes and the receiver will drop IP packets that do not meet these requirements |
| IPSec: Security Association | |
| IPSec: Security Association (An SA can be set up between the following peers) | - Host <-> Host - Host <-> Gateway (or vice versa) - Gateway <-> Gateway |
| IPSec: Security Association (There are two conceptual databases associated with SAs) | - The security policy database (SPD) specifies, what security services are to be provided to which IP packets an in what fashion - The security association database (SADB) |
| IPSec: Protocol Modes (An AS is always of one of the following types) (Transport mode) | - Transport mode can only be used between end-points of a communication -> host <-> host or - host <-> gateway, if the gateway is a communication end-point |
| IPSec: Protocol Modes (An AS is always of one of the following types) (Tunnel Mode) | - Tunnel mode can be used with arbitrary peers |
| IPSec: Protocol Modes (Transport mode) | |
| IPSec: Protocol Modes (Tunnel Mode) | |
| IPSec: Nesting of Security Associations | |
| IPSec: Authentication Head (AH) | |
| IPSec: Encapsulating Security Payload (ESP) | |
| IPSec: Establishment of Security Associations | - Prior to any packet being protected by IPSec, an SA has to be established between the two "cryptographic endpoints" providing the protection |
| IPSec: Establishment of Security Associations (SA establishment can be realized:) | - Manually, by proprietary methods of systems management - Dynamically, by a standardized authentication & key management protocol - Manual establishment is supposed to be used only in very restricted configurations (e.g. between two encrypting firewalls of a VPN) and during a transition phase |
| IPSec: Establishment of Security Associations (IPSec defines a standardized method for SA establishment:) (ISAKMP) | - Internet Security Association and Key Management Protocols (ISAKMP) -> Defines protocol formats and procedures for security negotiation |
| IPSec: Establishment of Security Associations (IKE) | - Internet Key Exchange (IKE) -> Defines IPSec's standard authentication and key exchange protocol |
| Internet Firewalls | |
| Firewalls: Terminology (Firewall) | - A component or a set of components that restricts access between a protected network and the Internet or between other sets of networks |
| Firewalls: Terminology (Packet Filtering) | - The action a device takes to selectively control the flow of data to and from a network - Packet filtering is an important technique to implement access control on the subnetwork-level for packet-oriented networks, e.g. the Internet - A synonym for packet filtering is screening |
| Firewalls: Terminology (Bastion Host) | - A computer that must be highly secured because it is more vulnerable to attacks than other hosts on a subnetwork - A bastion host in a firewall is usually the main point of contact for user processes of hosts of internal networks with processes of external hosts |
| Firewalls: Terminology (Dual homed host) | - A general purpose computer with at least two network interfaces |
| Firewalls: Terminology (Proxy) | - A program that deals with external servers on behalf of internal clients - Proxies relay approved client requests to real servers and also relay the servers answers back to the clients - If a proxy interprets and understands the commands of an application protocol it is called an application level proxy, if it just passes the PDUs between the client and the server it is called a circuit level proxy |
| Firewalls: Terminology (Network Address Translation (NAT)) | - A procedure by which a router changes data in packets to modify the network addresses - This allows to conceal the internal network addresses (even though NAT is not actually a security technique) |
| Firewalls: Terminology (Perimeter Network) | - A subnetwork added between an external and an internal network, in order to provide an additional layer of security - A synonym for perimeter network is de-militarized zone (DMZ) |
| Firewalls: Architectures (1) | |
| Firewalls: Architectures (2) | |
| Firewalls: Architectures (3) | |
| Firewalls: Packet Filtering (What can be done with packet filtering) | |
| Firewalls: Packet Filtering (Basic packet filtering enables to control data transfer on) | |
| Firewalls: An Example Packet Filtering Request |
Want to create your own Flashcards for free with GoConqr? Learn more.