Real-World Networks in Spring 2020

14-760: ADV.REAL-WORLD NETWORKS SPRING 2020 (KESDEN)

Application Establish an idiom for communicating with a particular application Transport Establish endpoints useful to a programmer NETWORK REFERENCE MODEL Network Given multiple inter-connected LANs, achieve cross-connectivity, Link Manage the channel to enable actual communication, i.e. establish a LAN Physical Establish a channel with connectivity and signaling

PHYSICAL LAYER: ESTABLISHES THE CHANNEL Medium? Light? Radio frequency? Electrical signals? What color(s) of light? How bright? What RF frequencies? How powerful? What signals represent what values? What shape are the connectors? How far can cables run? Etc. We have a functioning physical layer once we have the ability to send and receive signals

PHYSICAL LAYER: BANDWIDTH VS LATENCY Bandwidth = bits/second. Improved with parallelism or faster clock rate Latency = Function of signal propagation speed Limited by speed of light Major paradigm shift would be needed to make traffic to India or China less latent Latency tends to be limiting at a global scale Speed of light over long distances Bandwidth tends to be limited at local scale, e.g data center How to divide up and recombine messages to utilize parallelism? How to clock faster without losing signal to noise.

LINK LAYER: MANAGES THE CHANNEL When do we start transmitting? When do we stop? When do we start receiving? When do we stop? Who is sending? Who is receiving? How do we know if it is correct? What happens if there is contention for, or collision in, a shared channel? Key contributions: Framing, among others We have a functioning link layer once we can build a functioning LAN of at least two stations.

NETWORK LAYER: SCALING UP Passing messages among multiple networks For scale Of different types (wired, wireless, fiber, infrared, etc) Managed by different domains, etc. Globally meaningful addressing Ability to choose paths among multiple options We have a functioning network layer once we can connect multiple networks, identify hosts among them, and messages can find their way across networks from source to destination.

TRANSPORT LAYER: MEANINGFUL ENDPOINTS Hosts don t communication various aspects of software systems do Consider how many different sessions your Web browser has with servers. Now add for your IM sessions, upgrades-in-progress, music streaming, etc. Endpoints enable the establishment of sessions Classic model is <<IP:port>:<IP:port>> Client: Ephemeral port Host: Well-known port

TRANSPORT LAYER: MEANINGFUL ENDPOINTS, CONT. Character of communication Reliable/session-oriented, e.g. TCP Unreliable/datagram, e.g. UDP Etc. The transport layer exists once we have the ability to establish communication from end- point to end-point with well-understood properties

APPLICATION LAYER: PURPOSEFUL COMMUNICATION Defined by the messaging we, as programs, bake into our applications, shaped by our applications, e.g. client-server interactions, peer-to-peer interactions, etc. E.g. HTTP: PUT, GET, POST, etc E.g DNS: queries, responses, updates, etc. MIME, VOIP protocols, etc. Application protocols exist when applications can communicate

QUICK EVOLUTION OF LANS: SIMPLE LANS Two or more hosts share a common physical medium, e.g. ethernet Physical protocols define hardware Link-layer protocols manage it Point-to-point, e.g. fiberoptic Broadcast, e.g. ethernet

QUICK EVOLUTION OF LANS: WIRED LIMITS Consider ethernet: Multiple stations share a common wire What happens if more than one transmits at the same time? Collision, e.g. corruption Link layer manages collision, e.g. exponential back-off, jamming signals, etc. Wire can only get so long Attenuation, power to drive it, noise, etc. Mess of actually getting the wire through the building, etc. Can only have a certain number of stations Too little network time per each, otherwise Aside: Wireless has similar limits, too.

QUICK EVOLUTION OF LANS: BUS TOPOLOGY Imagine having to snake one wire around the building! https://upload.wikimedia.org/wikipedia/commons/9/9e/Bustopologie.png

QUICK EVOLUTION OF LANS: HUB TOPOLOGY The bus remains an equivalent collision/contention domain, but the wiring gets easier, physically. home runs to wiring closet, etc. Adapted from: https://upload.wikimedia.org/wikipedia/commons/9/9e/Bustopologie.png

QUICK EVOLUTION OF LANS: HUB HIERARCHY Hierarchies can be built, e.g. one hub per Hallway connected to one hub for the floor. But, all buses form a single collision/contention domain.

QUICK EVOLUTION OF LANS: NETWORK SWITCHES Enable connection of input and output port pairs without sharing a single common channel Crossbar switch: Mess of switched connections Input and output buffering with shared memory and control Etc Learning Pay attention when host sends to learn which port it is on, then direct messages to that host only to that port Flood all ports only when destination unknown. Enables larger networks Terminology note: A bridge is a simple switch with only two ports.

QUICK EVOLUTION OF LANS: LIMITS Even with switching, there is a limit to the size of a LAN In the worst case, a host which is not known, the entire LAN is still a single contention/collision domain If a host hasn t yet sent, or hasn t sent recently enough to be cached, flooding will be needed The flooding can, in the worst case, flood every port on every switch There obviously is no way to know the location of every host on the Internet And, of course, networks use different technologies, are managed by different domains, etc.

ERROR DETECTION AND CORRECTION Transmission process may introduce errors into a message. Single bit errors versus burst errors Detection: Requires a convention that some messages are invalid Hence requires extra bits An (n,k) code has codewords of n bits with k data bits and r = (n-k) redundant check bits Correction Forward error correction: many related code words map to the same data word Detect errors and retry transmission 17

THINKING ABOUT ERROR DETECTION AND CORRECTION T T T If the targets are close enough, a miss might hit the wrong one. If they are far enough apart, a miss is more likely to land in between . If they are really far apart, it is most likely that the a miss will land closer to the intended target than any other.

CLOSE ENOUGH? Consider the following code: 0 = jump 1 = run If 1 bit is in error, the message will be incorrect and misleading Now, consider the following code: 00 = jump 11 = run Now, if only 1 bit is in error, the message won t make sense, but we know that there is an error. Okay, one more code: 000 = jump 111 = run Now, if only 1 bit is in error, we can figure out which one it should be. If 2 bits are in error, we know that the codeword is defective, but don t know which bits are wrong.

HAMMING DISTANCE 1 0 1 1 0 1 1 0 1 0HD=2 Hamming distance of two bit strings = number of bit positions in which they differ. If the valid words of a code have minimum Hamming distance D, then D-1 bit errors can be detected. If the valid words of a code have minimum Hamming distance D, then [(D-1)/2] bit errors can be corrected. HD=3

HAMMING DISTANCE AND EC/ED Like the example on the previous slide, Hamming distance measures how far two things (codewords) are apart. Remember that Hamming Distance measures the distance between two codewords by the number of bits that would need to change to convert one into another. This is a useful measure, because as long as the number of bits in error is less than the Hamming Distance, the error will be detected -- the codeword will be invalid. Similarly, if the Hamming distance between the codewords is more than double the number of bits in the error, the defective codeword will be closer to the correct one than to any other.

HOW MANY CHECK BITS? If we have a dense code with m message bits, we will need to add some r check bits to the message to put distance between the code words The total number of bits in the codeword n = m + r If we do this, each codeword will have n illegal codewords within 1 bit. (Flip each bit). To be able to correct an error, we need 1 more bit than this, (n + 1) bits to make sure that 1-bit errors will fall closer to one codeword than any other.

ERROR DETECTION EDC= Error Detection Code (redundancy) Error detection not 100% reliable! Protocol may miss some errors, but rarely Larger EDC field yields better detection and correction D = Data protected by error checking, may include header fields EDC = Error detection code 23

EXAMPLE: PARITY CHECKING Add an extra bit Force sum of bits to be odd or even Set extra bit accordingly. If, upon receiving the message, the odd/even invariant isn t correct: Either parity bit or data is corrupt Can t tell which Throw away messages Even-bits in error escape detection, e.g. 2-bit errors, 4-bit errors, etc. 24

ERROR CORRECTION EXAMPLE: HAMMINGS CODE Label the bits of the codeword from left-to-right, from 1 through n. Check bits are stored in power of two bit positions. Data bits are stored in other positions Each parity bit is used to force the sum of itself and the bits that it checks to an even number (or odd) Each bit is checked by one or more parity bits. Specifically, let s consider a bit index i. If we rewrite in terms of powers of 2, it is checked by those powers of two that contribute to the addition For example, 7 = 4 + 2 + 1 so bit 7 contributes to parity bits 4, 2, and 1.

HAMMINGS CODE (EXAMPLE) a = _ _ 1 _ 1 0 0 _ 0 0 1 1 2 3 4 5 6 7 8 9 10 11 1 checks 3, 5, 7, 9, 11 1 + 1 + 0 + 0 + 1= 3; set parity bit on to force even parity 2 checks 6, 7, 10, 11 0 + 0 + 0 + 1= 1; set parity bit on to force even parity 4 checks 5, 6, 7 1 + 0 + 0 = 1; set parity bit on to force even parity 8 checks 9, 10, 11 0 + 0 + 1= 1; set parity bit on to force even parity a = 1 1 1 1 1 0 0 1 0 0 1 1 2 3 4 5 6 7 8 9 10 1

HAMMINGS CODE (EX.), CONT. a = 1 1 1 1 1 0 1 1 0 0 1 1 2 3 4 5 6 7 8 9 10 11 1 checks 3, 5, 7, 9, 11 1 + 1 + 1 + 0 +1 = 4; parity should be 0, but it is 1. Count = 1 2 checks 6, 7, 10, 11 0 + 1 + 0 + 1 = 2; parity bit should be 0, but isn t. Count +=2, so count is 3 4 checks 5, 6, 7 1 + 0 + 1 = 2; parity bit should be 0, but isn t. Count += 4, so count=7 8 checks 9, 10, 11 0 + 0 + 1= 1; parity bit should be 1 and is. Don t change count. Count is still 7 So, if only 1 bit is in error, it is bit 7.

HAMMINGS CODE (EX.), CONT. a = 1 1 1 1 1 0 1 0 0 0 1 1 2 3 4 5 6 7 8 9 10 11 1 checks 3, 5, 7, 9, 11 1 + 1 + 1 + 0 + 1= 4; parity should be 0, but it is 1. Count = 1 2 checks 6, 7, 10, 11 0 + 1 + 0 + 1= 2; parity bit should be 0, but isn t. Count +=2, so count is 3 4 checks 5, 6, 7 1 + 0 + 1 = 2; parity bit should be 0, but isn t. Count += 4, so count=7 8 checks 9, 10, 11 0 + 0 + 1= 0; parity bit should be 1 but is 0. Count +=8, so count=15. This makes no sense! More than 1 bit is in error. We can t fix it.

EXAMPLE: INTERNET CHECKSUM (CRC) Goal: detect errors (e.g., flipped bits) in transmitted segment Receiver Sender Compute checksum of received segment Check if computed checksum equals checksum field value: NO - error detected YES - no error detected. But maybe errors none-the-less? Treat segment contents as sequence of 16-bit integers Checksum: addition (1 s complement sum) of segment contents Sender puts checksum value into checksum field in header 29

CYCLIC REDUNDANCY CODES (CRC Commonly used codes that have good error detection properties. Can catch many error combinations with a small number of redundant bits Based on division of polynomials. Errors can be viewed as adding terms to the polynomial Should be unlikely that the division will still work Can be implemented very efficiently in hardware. Examples: CRC-32: Ethernet CRC-8, CRC-10, CRC-32: ATM 30

CRC: BASIC IDEA Treat bit strings as polynomials (Notice X3 is missing): Sender and Receiver agree on a divisor polynomial of degree k Message of M bits send M+k bits No errors if M+k is divisible by divisor polynomial If you pick the right divisor you can: Detect all 1 & 2-bit errors Any odd number of errors All Burst errors of less than k bits Some burst errors >= k bits 1 0 1 1 1 X4+ X2+X1+X0 31

CHECKSUMS Checksums are based on dividing binary polynomials, modulus 2. Both addition and subtraction are equal to XOR in modulus 2 arithmetic + 01010001 01011111 10011011 11001010 + 11110000 10101111 This can be used to perform long division.

CHECKSUMS, CONT. Given a message, we will add checksum bits These bits will be computed by dividing the message by a generator polynomial modulus 2. The remainder is the checksum The checksum is one bit smaller than the generator polynomial. Good polynomials won t divide the types of errors common in a particular channel

CHECKSUM, CONT. CRC-12: x12 + x11 + x3 + x2 + x1 + 1 CRC-16: x16 + x15 + x2 + 1 CRC-CCITT: x16 + x12 + x5 + 1 These can be represented as polynomials. For example, consider CRC-12: 1 1 0 0 0 0 0 0 0 1 1 1 1

CHECKSUM, CONT. 1 1 0 0 0 0 1 0 1 0 1 0 0 1 1 1 1 0 1 0 1 1 0 1 1 0 0 0 0 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0 1 1 0 1 0 0 1 1 1 0 1 0 0 1 0 0 1 1 1 1 1 0 This remainder is the checksum.

THE NETWORK LAYER Hierarchical addressing Traditional IPv4 addresses: 32-bits: Network# + Host Number IPv6 addresses: 128-bits and more structured Host number translated to LAN station ID, e.g by ARP between IPv4 and 802.11 Routing selects path to take from one network to another, often on a hop-by-hop basis Does this packet belong on one of my LANs? If so ARP and deliver If not, send upstream (or to a peer, or ) This provides for an order of magnitude more hosts

THE NETWORK LAYER: IP ADDRESS ASSIGNMENT Old school: Go to system administrator and trade MAC address for IP address Today: DHCP server automates this. Broadcast of request with MAC is answered with assigned IP Assigned IP is leased and needs to be renewed Assigned IP can be from dynamic pool Assigned IP can also be according to a pre-configured rule, such as to give a server a well- known address DHCP can also communicate other configuration information

DOMAIN NAME SYSTEM Old school Let The Keeper of All Things know about a hostname:IP assignment in your organization The Keeper updates a hosts text file with the information Periodically download this file to keep your system up to date Obvious scalability problems, but /etc/hosts still exists vestigially and for special cases Today Domain Name System (DNS) is a distributed data base that delegates assignments for information to the responsible domains and can direct queries to the servers associated with those domains. Uses caching for efficiency. We ll talk about it later in detail

TRANSPORT LAYER: USER DATAGRAM PROTOCOL (UDP) Reminder: Port numbers in addition to IP addresses Best effort = Unreliable Messages can be lost or reordered Message corruption is assumed to be detected at the link layer Message oriented. Max message size Simple Used for timely updates, e.g. send audio or video for teleconferencing

TRANSPORT LAYER: RELIABLE PROTOCOLS Keeps trying to send data until it succeeds or times out Used acknowledgements to determine that it does not need to resent Buffers to ensure in-order delivery, which allows head-of-line blocking Messages are assumed to be correct or undelivered via checksums at link layer Byzantine Failures are possible, occur commonly at Internet scale, but infrequent enough to be (mostly) ignored. Maybe. Can t guarantee delivery. At best can trade timeliness for delivery

TRANSPORT LAYER: STOP-AND-WAIT PROTOCOLS Send a message. Wait one fully network latency for it to get to the recipient. Wait for the recipient to process it. Wait another full network latency to send back the acknowledgement In one round-trip time (RTT), only one message is sent. RTT sec * bits/sec = total bits we can send in that time. Size of message is what we actually sent. Rest of time is wasted waiting.

TRANSPORT LAYER: SLIDING WINDOW Buffer enough data on sender to keep sending for the entire RTT. Treat sending buffer as circular: As ACKs come back, slide window to buffer new data, releasing old data and keep sending. If ACK doesn t come back in time, resend data. Head-of-line blocking is possible Keep buffer an receiver in sync with sender to buffer, releasing segments up the stack in order. Requires segments, segment numbers

TRANSPORT LAYER: SLIDING WINDOW Acknowledged packets Packets not acknowledged yet LFS seq. numbers LAR LAR (last ACK received) LFS (last frame sent)

TRANSPORT LAYER: SLIDING WINDOW, CONT. Sender Receiver Next expected Max acceptable Max ACK received Next seqnum Sender window Receiver window Credit: Hui Zhang Sent & Acked Sent Not Acked Received & Acked Acceptable Packet OK to Send Not Usable Not Usable

TRANSPORT LAYER: TRANSMISSION CONTROL PROTOCOL (TCP) Reminder: Port numbers in addition to IP addresses Used for transmissions that need to be correct, but not timely Streaming audio or video, e.g. recorded movies Bulk data transfer, e.g. uploads or downloads Requires overhead of establishing a session to maintain shared state between sender and receiver to coordinate. Different schemes for ACKs Delayed ACKs, Cumulative ACKs, Selective ACKs

TRANSPORT LAYER: TRANSMISSION CONTROL PROTOCOL (TCP) Congestion Control Packet loss can be due to many types of failure, including congestion If congestion, desire is to slow down. Slowing down can be achieved by shrinking window, which leaves network time unused TCP has different strategies it can use to determine when to slow down and how to speed back up. 3-Way Handshake: SYN, SYN-ACK, ACK-SYN Establishes session, negotiates window sizes and other options, e.g. SACK, window sizes, etc.