CS640 Midterm Notes.pdf

History of Communication 1. A. Graham Bell (Telephone) - 1876 2. Claude Shannon telecom research - 1940 3. Satellite communication - 1958 4. Fiber Optics - 1958 5. Packet Switching (P. Barren, L. Kleinrock, D. Davies) 6. RAND develops Arpanet plan - 1967 7. Arpanet, Network Cont...

History of Communication 1. A. Graham Bell (Telephone) - 1876 2. Claude Shannon telecom research - 1940 3. Satellite communication - 1958 4. Fiber Optics - 1958 5. Packet Switching (P. Barren, L. Kleinrock, D. Davies) 6. RAND develops Arpanet plan - 1967 7. Arpanet, Network Control Protocol - 1972 8. R. Metcalf invented Ethernet - 1973 9. Tim Bernes Lee invented HTTP - 1991 3 Definitions of the Internet: 1. Infrastructure to support applications 2. Network of networks 3. Collection of protocols Groups that specify requirements for the internet: 1. Application programmers: list services that the application needs 2. Network operator: lists characteristics of a system easy to administer and manage 3. Network designer: list the properties of cost-effective design Abstract Perspective of Networks/Internet - Nodes and Links - Link with 2 endpoints -> point-to-point - Link with multiple endpoints -> multiple-access - 2 indirect ways to connect nodes - Switched Network: - Packet Switch: store and forward - Circuit Switch: establish a dedicated circuit across links and allow source node to send bits across this circuit to the destination node - Internetwork: - Network of networks - Router: connects two or more networks - Runs in Internet Protocol (IP) - Unicast: single source node to single destination node - Multicast: single source node to multiple destination node - Broadcast: single source node to all other nodes Internet Perspective of Networks/Internet General flow: 1. Person send http request 2. Send packet to router (home switch) 3. Router multiplex traffic to network - Synchronous time-division: divide time into equal-sized quanta and give each flow a change to send its data over the physical link using round robin - Frequency-division: transmit flow over physical link at different frequency - Statistical: send whenever you want, store packets in a buffer and use an algorithm to divide which one goes first 4. Send it to modem to translate packet that internet can read 5. Switches forward the packet within a network 6. Routers forward the packet between networks - Routing: establish forwarding tables. 7. Find the desired server Architectural Perspective of Networks/Internet 5 Layer Internet Model Layer 1: Physical Hardware specifications, representation of bits on physical media Layer 2: Link How host access the physical media (Ethernet, DSL, Cable, Fiber) Layer 3: Network Uses only 1 protocol: Internet Protocol to define addresses, routing protocols Layer 4: Transport TCP, UDP, logical (end-to-end) channels Layer 5: Applications Data and header is pushed to transport layer through socket - Each layer has its own header - Encapsulation: wrap them all in the packet - Decapsulation: unwrap them - Hosts: L1 - L5 - Switches: L1 - L2 - Modem: L1 - Router: L1 - L3 - There will be a lot of encapsulation and decapsulation throughout the transmission process Narrow Waist Protocols define 2 interfaces: 1. Service Interface: moving between different layers on the same machine 2. Peer Interface: moving between different machines on the same layer IP Service Model 1. Connectionless: Not sure about connectivity of the network before sending/receiving 2. Packet-Based 3. Best Effort: No guarantee 4. Destination-Based Performance Performance Formulas Throughput = TransferSize/TransferTime (bits/sec) TransferTime = RTT + 1/Bandwidth x TransferSize Propagation delay for one-way trip -> RTT/2 Transfer time (one way) = RTT/2 + size/bandwidth + (handshake, waiting time if needed) Number of Packets = Transfer Size / Bandwidth Delay x Bandwidth product represents the number of data sender can send before it would be possible to hear a response Queuing - Little’s Law a simple queuing theory - Mean number of jobs in a system = Arrival Rate x Mean Response Time - If average forwarding time for a router is 100 microsecond and the I/O rate is 100 kpps (kilo packets per second), what is the mean number of packets buffered? - 100,000 (packets per second, arrival rate) x 0.0001 (second, mean response time) = 100000 * 0.0001 = 10 The Noisy Channel Problem - Claude Shannon - Problem: Can we recover the signal that was sent by the source at the receives - A mathematical theory for communication 1948 - Source coding -> compression - Channel coding -> error detection and correction Dealing with Errors - Error detection -> when errors are rare - Error correction -> when errors are common - Handling Errors: - Start with packet D - Apply algorithm A to D to generate code C - Transmit D and C over a link - Receiver receives D’ and C’ - Receiver applies A to D’ to get C’’ - Check if C’ = C’’ - Methods for detection: - Parity (Odd/Even Parity) - Checksum (used in IPv4) - CRC (Cyclic Redundancy Check) Layer 1: Physical Layer Key Components of Physical Layer: 1. Network cables and connections 2. Representations of 0’s and 1’s 3. Framing: start and end of packets Characteristics of links: 1. Medium - Copper wire in some form (DSL, Coaxial Cable) - Optical Fiber (backbone) - Air/free space (last mile)  -Media define: - Distance over which a signal can be effectively transmitted - How resilient they are to noise - How resilient they are to strains - How many bit/sec they can handle - Cost 2. Frequency - Wavelength = speed of light / frequency - Unit: hertz 3. How they are used - Various economic and deployment issues influence where different link types are found 3 primary types of physical media 1. Air - Signals are sent/received by antennas - Faster than copper and fiber - Susceptable to noise 2. Copper - Twisted pair is a standard for noise reduction (Ethernet uses twisted pair) - Using a different voltage where the receiver detects the difference to distinguish 0’s and 1’s - Ethernet cable categories specify details that determine how cables are resilient to noise and can support different bandwidths - Transceivers send and receive signals 3. Fiber (1966) - Lasers send, optical diodes receive - Further signal propagation and the ability to transmit at higher bandwidth than copper -  Multimode Optical Fiber Single Mode Optical Fiber - Larger core size: usually 50 - Smaller core size: usually 8 micrometers micrometer - Allow multiple light modes to travel - Only allow single light mode to travel simultaneously simultaneously - Designed for short-distance runs - Suitable for long-distance applications - Generally less expensive - Only support one type of data - Support multiple data transmission transmission mode modes - Higher bandwidth - Most commonly used now Bit Encoding on Copper 1. NRZ - Map 1 onto higher signal, 0 to a low signal - Uses average of the signal to distinguish high and low signals - Too many consecutive 1’s and 0’s will affect average -> baseline wander - Frequent transitions from high to low and vice versa are necessary to enable clock recovery - Sender and receiver’s clock has to be in synch - The receiver describes the clock from the received signal - Whenever the signal changes, the receiver knows it’s at a clock cycle boundary, so that it can resynchronize - Long period without transitions will cause clock drift 2. NRZI - Sender make a transition from the current signal to encode a 1, stay at current signal to encode a 0 - Thus solves the problem caused by consecutive 1’s, because there will be signal transition no matter what if encounter a 1 3. Manchester encoding - Low to high signal -> 0 - High to low signal -> 1 4. 4B/5B - Every 4 bits of data are encoded in a 5 bit code (using the table) - No more than one leading 0. No more than two trailing 0s - Solves problems caused by consecutive 0s Framing - Byte oriented protocols (BISYNC, PPP, DDCMP) - Sentinel based approaches (character stuffing) - BISYNC: - - PPP: - - Flag: 01111110 - Byte-counting approach - Include number of bytes contained in a frame as a fiend in frame header - DDCMP - - Bit-Oriented Protocols (HDLC) - - Beginning and ending sequence: 01111110 - To avoid 01111110 from appearing in data body, use bit stuffing - Whenever there are 5 consecutive 1’s, stuff a 0 after that Error Detection - CRC: N = highest degree of the CRC polynomial 1. Pad N 0’s to the end of data bits 2. Divide padded data bits with polynomial (use XOR) 3. The remainder are the CRC bits - To do error detection: 1. Divide (message + CRC bits) by CRC polynomial 2. If remainder = 0, then no transmission error - 2-D Parity: add one extra bit to 7 bit code (odd parity), add extra parity byte for each column - Internet Checksum Algorithm Layer 2: Link Ways of Link Coordination (Medium Access Control) 1. Channel partitioning (multiplexing methods: frequency, time division, statistical) 2. Taking turns (token-based systems, polling based) 3. Random access -> Aloha protocol Aloha Protocol 1. Any station can send anytime 2. Receiver transmits acknowledgement packet 3. If the sender does not receive an ACK after a period of time, sender will enter random exponential backoff - Exponential backoff: on the nth round, choose from the set k = {0, 1, 2, …, 2^(n01)}. Then delay for 51.2*k microseconds 4. Retransmit after backoff is complete 5. Does not have interframe gap 6. Does not enforce carrier sense 802.3 Ethernet Standard - Based on Aloha - Specifies Layer 1 and Layer 2 details Physical properties (Layer 1) - - Repeaters: forward digital signals - Understands bits, not frames - No more than 4 repeaters can be positions between any pair of hosts - Classical ethernet had a total reach of only 2500m - Hub: Multi-way repeater - Repeats whatever it hears on one port out all its other ports - No forwarding table - Any signal places on the Ethernet by a host is broadcast over the entire network - Terminator attached to the end of segment absorb the signal and keep it from bouncing back and interfering with trailing signals  - Bridge: Connect different collision domains (Layer 1 + Layer 2) - Use forwarding tables - Switches: complicated and can cause loops (spanning tree algorithm) - Forwarding tables - Hosts competing to the same link are in the same collision domain Access Protocol (Layer 2) - CSMA/CD - Carrier Sense: all nodes can distinguish between an idle and a busy link - If line is idle for 9.6 microseconds, then send - If line is busy, wait until idle, then wait 9.6 microseconds, then send - Multiple Access: set of nodes send and receive frames over a shared link - Collision Detect: a node listens as it transmits and can therefore detect when a frame it is transmitting has interfered with a frame transmitted by another node - If there is a collision: - Send jam signal - Exponential backoff (remember to include IFG) - Frame format: - Preamble: clock synchronization - Interframe gap (IFG) = 9.6 microseconds = 96 bit time - 0.1 microsecond = 1 bit time - Frames less than minimum frame length = runt frame - Minimum frame length must be long enough for collision detection - Bit oriented - Addresses - Every ethernet host has a unique ethernet address which belongs to the adaptor, not the host -> unicast address - Each frame transmitted on an ethernet is received by every adaptor connected to that ethernet - Each adaptor recognizes those frame addresses to its address and passes only those frames onto the host - Broadcast address: all 1’s, send to all hosts - Multicast address: start with 1, send to subset of hosts 802.11 (Wifi) Standard - Wireless links all share the same medium - Antenna’s can’t effectively send/receive at the same time Two Kinds of Endpoints 1. Base station - No mobility but has a wired connection to the internet or other networks - 2. Mesh/ad hoc - No special base station node - Message may be forwarded via a change of peer nodes as long as each node is within range of the preceding node - Access Control (Focus on Layer 2 for 802.11) - Can’t send and receive at the same time - - A and C are hidden nodes - Both A and C can be sending nodes to B, but neither of them are unaware because they are not in each other’s range - - If B transmits to A, C will be forbidden to send since it’s in range of B. However, C should be able to send to D -> exposed node - Multiple Access with Collision Avoidance (MACA): - Sender sends RTS that includes duration - Receiver sends CTS - In hidden node problem: - A will send RTS to B - B will Send CTS to A and C - C will receive CTS but not corresponding RTS, so now it knows it’s a hidden node - In exposed node problem: - B will send RTS to A and C - A will send CTS to B, C will not receive it since it’s not in A’s range - Since C didn’t receive a CTS corresponding to RTS received earlier, it knows it’s not close enough to interfere Distribution System (Wifi) - Base station oriented - In distribution system, some nodes are allowed to roam - Some nodes are connected to a wired network -> access points - Access points that are connected together -> distribution system - - Association Protocol - Node sends a probe frame - All APs within reach reply with a probe response frame - The node selects one of the APs and sends that AP an association request frame - The AP replies with an association response frame - APs periodically send a beacon frame that advertises the capabilities of the access point - Layer 3: Network - Concerned with internetworking (moving packets between networks) - Infrastructure operated by an Internet Service Provider (ISP) - IP addresses facilitate global connectivity - IPv4 is most widely used - 32 bits separated by dots (per byte) - Nodes that interconnect the networks are called routers/gateways 3 Things you need to be an ISP 1. Infrastructure 2. Address space 3. Autonomous system number 4. Managed by Internet Assigned Numbers Authority (IANA) Classful Allocation  - - Number of Class A networks = 2^7 - 2 = 128-2 = 126 - 2 reserved networks - Number of Class A hosts = 2^24 - 2 - Challenges: - Allocation boundaries are restrictive - Doesn’t move packets inside a network (not Layer 3’s responsibility) - General flow: - Send a packet - Move between networks using routers - Translate IP (Layer 3) to MAC (Layer 2) to get to specific host Subnets - Enable a network to be divided into smaller networks - Reduce total number of networks numbers assigned to physical networks - Map a single network number to multiple physical networks - Groups of physical networks that have the same network number are subnets - Each subnet has one subnet number, which can be extracted from the IP address using subnet mask (this will be added to the forwarding table) Supernets (Classless) - Classless interdomain routing (CIDR) - Allocate address space on power of 2 (slash notation) - Class A: /8, Class B: /16, Class C: /24 - Assign contiguous block of classes addresses - /X : X is the prefix length - Longest prefix match Address Resolution Protocol (ARP) - Layer 3 doesn’t allow for moving packets to hosts. We need a mechanism to map IP to MAC -> ARP - Runs on hosts and switches (routers also) - Each host dynamically learn the contents of the ARP table - Entries are timed out after 15 mins and removed - If a host wants to send an IP datagram to a host that it knows to be on the same network:  - Check for a mapping in the cache - If not found, invoke ARP over the network - Broadcast an ARP query onto the network - Each host receives the query and checks if it matches its IP - If match, add to ARP - Each host that received the broadcast can update their ARP table - Only hosts with host on their table will update their tables (and refresh the timer) - Target host will add information for sure, since might need to send ACK - DHCP (Dynamic Host Control Protocol) - Assign IP addresses to each host - Send request for an IP address to 255.255.255.255 - The DHCP server will respond with an IP address - Doesn’t interact with DNS Fragmentation and Reassembly - Every network type has a maximum transmission unit (MTU) - Use fragmentation to send parts of dat ato destination if packet too big (fragmented by the router that receives them) - Fragmentation will only be necessary if the path to the destination includes a network with a smaller MTU - ID/Flags/Offset fields in the header are used for fragmentation - Use ID field for reassemble fragments at the receiving host (fragments belong to the same packet will carry the same ID) Error Reporting (ICMP)  - Defines a collection of error messages that are sent back to the source host whenever a router or ghost is unable to process an IP datagram successfully - Defines some control messages that a router can send back to source host - Example: ICMP-Redirect (tells the source that there is a better route) - Two common debugging tool: ping, traceroute Practice Problems Calculate the total time required to transfer a 1.5-MB file in the following cases, assuming an RTT of 80 ms, a packet size of 1 KB data, and an initial 2 × RTT of “handshaking” before data is sent: (a) The bandwidth is 10Mbps, and data packets can be sent continuously. Transmission Delay = packet size / bandwidth = 1.5MB/10Mbps = 1200ms Propagation Delay = RTT/2 = 80ms/2 = 40ms Latency = handshake + Transmission Delay + Propagation Delay = 1.4s (b) The bandwidth is 10Mbps, but after we finish sending each data packet we must wait one RTT before sending the next. Number of packets = file size / packet size = 1.5MB / 1KB = 1500 Latency = handshake + Transmission Delay + Propagation Delay + extra RTT = 2*RTT + 1200ms + 40ms + (1500-1) RTT = 121.32s (c) The link allows infinitely fast transmitting, but limits bandwidth such that only 20 packets can be sent per RTT. Number of trips = Number of packets / bandwidth = 1500/20 = 75 Latency = 2*RTT + (74.5)80 = 6.12s Consider a point-to-point link 2 km in length. At what bandwidth would propagation delay (2 x 10^8) equal transmit delay for 100 byte packets? Transmit Delay = 100/x Propagation Delay = 2km/(2 x 10^8) x = 10^7 Suppose the round-trip propagation delay for Ethernet is 46.4μs. This yields a minimum packet size of 512 bits (464 bits corresponding to propagation delay + 48 bits of jam signal). (a) What happens to the minimum packet size if the delay time is held constant, and the signaling rate rises to 100 Mbps? 46.4 x 10^-6 * 10^8 = 46.4*10^2 = 4640 Minimum packet size = 4640+48 = 4688 Path MTU is the smallest MTU of any link on the current path (route) between two hosts. Assume we could discover the path MTU of the path used in the previous exercise, and that we use this value as the MTU for all the path segments. Give the sizes and offsets of the sequence of fragments delivered to the network layer at the destination host. Suppose hosts A and B have been assigned the same IP address on the same Ethernet, on which ARP is used. B starts up after A. What will happen to A’s existing connections? Explain how “self-ARP” (querying the network on start-up for one’s own IP address) might help with this problem. After B broadcasts any ARP query, all stations that had been sending to A's physical address will switch to sending to B's. A will see a sudden halt to all arriving traffic. (To guard against this, A might monitor for ARP broadcasts purportedly coming from itself; A might even immediately follow such broadcasts with its own ARP broadcast in order to return its traffic to itself. It is not clear, however, how often this is done.) If B uses self-ARP on startup, it will receive a reply indicating that its IP address is already in use, which is a clear indication that B should not continue on the network until the issue is resolved.