About the Final Exam!! Saturday June 4 3:00-6:00PM!! Open book, open notes; no computers!! Material to be covered!" Chapter 2: focusing on 2.2 & 2.5!" Chapter 3: focusing on TCP (3.5 & 3.7)!" Chapter 4: 4.4 ~ 4.7!" Chapter 5: 5.3 ~ 5.6!" Chapter 6: 6.3 and 6.5!! The objective: testing the overall understanding of the material!CS118!1!The big picture!CS118!2!HTTP TCP IP Ethernet interface HTTP TCP IP wireless interface IP IP Ethernet interface Ethernet interface SONET interface SONET interface host host router router HTTP message TCP segment IP packet IP packet IP packet Ethernet frame Access point (AP) A Bottom-up Roadmap!! Physical layer: know how to calculate the delay of sending packets from one node to another!" Transmission rate (bandwidth)!" Transmission delay!" Propagation delay!! Link layer: move data between two directly connected nodes!" Error checking schemes: parity, checksum, CRC!" Framing, byte stuffing!" Multi-access protocols: Aloha, Ethernet (CSMA/CD), 802.11 (CSMA/CA)!" MAC address, Address Resolution Protocol!" Switch/bridge self-learning scheme!CS118!3!Bandwidth, transmission delay, propagation delay!CS118!4!bandwidth!time!10Mbps 20Mbps Total bits to send!T=0!T=1!T=2!Above link layer!! Network layer!" IP header, IP address structure (subnet, CIDR)!" Routing: distance vector, link state; BGP; broadcast, multicast, IGMP!! Transport layer!" UDP, TCP: header format!" TCP!# connection set-up & tear-down!# congestion control!# retransmission timer setting!" Mechanisms for reliable data delivery; relations among sequence number, window size, RTT!! Application layer protocols!CS118!5!Packet switching!! Why packet switching?!! Packet: data chopped into chunks!! Forwarded in a "store-and-forward" way!" Statistical multiplexing ! queueing delay, potential losses!! Delays in the network!" Transmission delay: packet-size/bandwidth!" Propagation delay: link-length/prop. Delay!" Store-and-forward delay!" Queueing delay!CS118!6!Data link layer!! You need to know the concepts of (1)framing; (2)byte stuffing; (3)bit error detection!! Link layer address: MAC addresses (Medium Access Control)!" not IP address!!" flat address space!" Need ARP to map IP to MAC address!! Channel access protocols for multiaccess channels (e.g. Ethernet, wireless LAN)!CS118!7!Random multi-access protocol!! Multi-access: single communication channel shared by multiple nodes, only one node can send successfully at a time!! Aloha/Slotted Aloha!Q: for a network with 3 nodes, what is the probability that a given node sends a data frame successfully without collision?!! Ethernet!" 1-persistent CSMA/CD!Q: Why need collision detection?!" Collision resolution: Q: how the exponential backup works!! 802.11 wireless LAN!" CSMA/CA!Q: why doing collision avoidance instead of collision detection?!" RTS-CTS!CS118!8!Aloha example!! P(success by a given node)= p . (1-p) (N-1) ! N=3, if P = 0.2, p . (1-p) (N-1) = 0.2(0.8)2 Ү 0.08 ! P(success by any node)= N p . (1-p) (N-1) ! As N $ large, Pmax(success by any node)=1/2e ! Maximum throughput? 1Mbps * 0.18 = 180Kbps CS118!9!Ethernet: CSMA/CD!! Carrier Sense Multiple Access with Collision detection !Listen before transmit!" If channel sensed idle: transmit right away!" If channel sensed busy, wait!But collisions still possible!! To cut the loss early: Collision Detection: compare transmitted with received signals!" Abort collided transmissions!CS118!10!Ethernet: colision detection and recovery!A: sense channel, wait if necessary until it is idle !transmit and monitor the channel; !If detect another transmission !then { ! abort and send jam signal; !update # collisions (n++); !delay for K x 512bits transmission time!goto A!}!else {done with the frame; set #collisions to zero (n = 0)}!!Jam Signal: make sure all other transmitters aware of the collision!!Exponential Backoff algorithm: !! first collision (n=1): choose K from {0, 1} (i.e. {0, 2^n – 1})!! after second collision (n =2): choose K from {0, 1, 2, 3}…!! after 10 collisions (n=10), choose K from {0,1,2,3,4,…,1023}!CS118!11!Why Ethernet has a lower bound on frame size?!! Ethernet transceiver can send & listen at same time !" If the received data stream differs from the one transmitted ! collision!! to detect a collision: the sender must still be transmitting when garbled signal propagates back !CS118!12!B A time!2*Propagation-delay!! Etheret’s lower bound on frame size: for reliable collision detection:!" cable max length: 2500m "!" minimum frame size = 64bytes = 512bits, take 51 to transmit at 10Mbps data rate!(so that A will still be transmitting when B’s collided signal propagates to A)!CS118!13!sec2.512µ=delayPsecµEthernet efficiency: example!! 10Mbps coaxial-cable Ethernet LAN has a span of 2250 meters, data frame size = 125 bytes, signal propagation speed 2.25 " 108 m/sec!! What is the effective throughput?!CS118!14!! efficiency =11+ 5tprop/ttransEffective throughput = data rate x efficiency!1000!100 = !! 107"11+5 " 10100=1071.5# 667KbpsARP: Address Resolution Protocol!! A knows B's IP address, needs to find B's MAC address!! A broadcasts ARP query pkt, containing B's IP address !" Contains A's IP address as well!" Dest MAC address = FF-FF-FF-FF-FF-FF!! B receives ARP packet, replies to A with its (B's) MAC address!" reply sent to A’s MAC address (unicast)!" Caches A's IP-to-MAC address mapping!! A caches (saves) IP-to-MAC address mapping until it times out!! ARP Table: IP/MAC address mappings for local LAN nodes! < IP address; MAC address; TTL>!CS118!15!How to connect multiple Ethernets!! Compare hubs, switches, and routers!! Switch self-learning algorithm!CS118!16!B1 B3 B2 B4 A D C Q: Assuming all the switches' forwarding tables are empty, show the forwarding tables for switches B1-B4 after the following transmissions: 1. A sends to C 2. C sends to A 3. D sends to C Solution: • When A sends to C, all the switches see the packet and learn where A is. • When C sends to A, packet is routed directly to A, so B4 does not learn where C is. • When D sends to C, packet is routed by B2 towards B3, and B1 does not learn where D is.Another exercise problem!! Will Host-D and Host-C have the same subnet mask?!!
View Full Document
Unlocking...