Midterm ReviewOutlineNetwork Basics – Extremely importantNetworking Basics – ExampleNetworking and ProtocolsLayered Architecture in NetworkingPhilosophy of the InternetInternet Design: TodayPhysical LayerPhysical Layer: Signal to BitsThe Nyquist LimitCapacity of a Noisy ChannelMultiplexing the ChannelEncodings4B/5B EncodingDatalink LayerEthernetThe Early Days of EthernetEthernet: early MAC layerEthernet: Collision DetectionBuilding Larger LANs: BridgingSpanning Tree AlgorithmSlide 23Slide 24Slide 25Internet Protocol (IP)IP AddressingClassful-Internet ArchitectureClassless-Internet ArchitectureNetwork Address TranslationTunnelingDistance-Vector Routing ProtocolLink State Protocol ConceptDijkstra’s AlgorithmA Logical View of the InternetTransit vs PeeringBGP: Path Vector ProtocolDomain Name System (DNS)The Good / Bad NewsSuggestionsMidterm Review15-441: Recitation 7By: TAs determined to make sure you ace the midterm1Outline•Networking basics•Network architecture▫Layered model▫Internet design•Switching, bridging, and routing2Network Basics – Extremely important•Bandwidth: link transmission rate (bits/s)▫increase/decrease in delay no affect•Throughput: successful information xferred over time (bits/s)▫affected by latency and loss rate▫1MB transferred in 200ms?▫1MB/(200ms/1s) = 1MB/.2s = 5MB/s•Round Trip Time (RTT)3Networking Basics – Example •Calculate throughput on 1.5Mbps link:▫Transfer of 1000KB file▫RTT of 100ms▫a packet size of 1KByte▫initial 2RTT of handshaking•Fix units first!▫RTT=0.1s, FILE = 1000*1024*8 = 8192000 bits•T = Thandshake + Tpropagation + Ttransmission•T = (2*RTT) + (0.5*RTT) + (data/bandwidth)•T = (2*0.1s) + (0.5*0.1s) + (8192000/(1.5*10^6/s))•T = 5.711s4Networking and Protocols•What is a protocol? (think IRC!)▫A convention consisting of a set of rules and syntax for synchronization of communication ▫e.g., client: NICK+USER, server: MOTD•Why we need protocols: heterogeniety▫Many applications and implementations▫OS: Linux, Windows, MacOS▫Applications: IE, Firefox, Opera, Safari5Layered Architecture in Networking•Why do we have a layered architecture?▫break down complexity of the system▫allows development at each layer without knowing details of the nextBITSBITSFlow FramingSwitching RoutingEnd-to-end ReliabilityManaging logical connectionsData transformationsWeb, E-Mail, IRC, Telnet6Philosophy of the Internet•“End-to-end argument”: greatest impact on the design of the Internet•Fundamental goal: effective interconnection•Functionality: does everyone need it? E2EA:▫Everyone needs it: put it in the core▫Optional functionality: implement at the hosts•What would E2EA say about:▫packet forwarding, security, reliability7Internet Design: Today•Reliability: end to end (e.g., TCP)•Management: completely decentralized•Cost: inexpensive… Internet infrastructure cost less than typical enterprise networks•Attachment: host connection automatic•Accountability: what accountability? ;)▫Leads to major security issues▫More of a push towards security in core8Physical Layer•Why do we care? It affects us!9Physical Layer: Signal to Bits•Fundamental of communications: sine wave▫S(t) = A * sin(2π f t + Θ)•Modulation: varying a periodic waveform (e.g., sine wave) in order to convey a message (e.g., bit)▫Amplitude, frequency, and phaseMODEM: modulator + demodulator10The Nyquist Limit•First, bandwidth: width of a frequency range▫e.g.,: 300MHz to 400MHz = 100MHz bandwidth•A noiseless channel of width H can at most transmit a binary signal at 2H▫e.g., 3000Hz channel, at most 6000bps▫Assumes binary amplitude encoding11Capacity of a Noisy Channel•Shannon’s Theorem: C = B * log2(1+S/N)▫C = maximum channel capacity(bps)▫B = channel bandwidth (Hz)▫S/N = signal-to-noise ratio: 10*log(S/N) •For example, homework 1:▫B = 1000Hz, S = 500, N = 10▫C = 1000Hz * log2(1+500/10)▫C = 5672bps (NOT Hz)12Multiplexing the Channel•Want to support multiple users, but the medium is shared▫Time division: me, you, me, you, me, etc…▫Frequency division: me(100-200Hz), you(200-300Hz)13TimeFrequencyEncodings•NRZ: 1->high, 0->low▫Problem: long seq.•NRZI: 1->transition▫Problem: long 0’s•Manchester: ▫0: positive transition▫1: negative transition144B/5B Encoding•Data coded as symbols, 4 bits uses 5 bits▫uses NRI to encode 5 bits▫pre-determined in dictionary•Key properties:▫each valid symbol: at least two 1s▫dense transitionsbetter for clock synchronization▫downside: requires overhead▫100Mbps requires ___MHz15Datalink Layer•Datalink layer responsibilities:▫framing (e.g., bits into a datagram)▫media access (e.g., who transmits when)▫error control (detection and correction)▫flow control (e.g., sender doesn’t overflow receiver)•Framing: where are the useful bits?▫detect using special bit sequences (preamble)▫E.g., 101110110111010… here comes a packet!16Ethernet•Goal: connect computers to form LAN▫Defines PHY, data link, MAC, and addressing17The Early Days of EthernetMultiple machines sharing non-duplex medium… … implications? Think: MAC layer18Ethernet: early MAC layer•Key Fact: only 1 node can transmit at a time▫otherwise: collision, both packets lost19Random…… why?Ethernet: Collision Detection20LatencyBandwidthMinimum_pkt_size = latency*bandwidth2*Propagation delay * wire lengthBuilding Larger LANs: Bridging•Extend reach of single shared medium▫Copy data frames between the segments▫Reduced collision domain•Problem of loops▫Solution: spanning tree21Spanning Tree Algorithm22•What port to forward?▫Select lowest ID: root▫(ID, ROOT, ROOT-HOPS)•First round:▫B5: (B5, B5, 0)▫B7: (B7, B7, 0)▫B3: (B3, B3, 0)▫B2: (B2, B2, 0)Spanning Tree Algorithm23•What port to forward?▫Select lowest ID: root▫(ID, ROOT, ROOT-HOPS)•Second round:▫B5: (B5, B1, 1)▫B7: (B7, B1, 1)▫B3: (B3, B2, 1)▫B2: (B2, B1, 1)Spanning Tree Algorithm24•What port to forward?▫Select lowest ID: root▫(ID, ROOT, ROOT-HOPS)•Third round:▫B5: (B5, B1, 1)▫B7: (B7, B1, 1)▫B3: (B3, B1, 2)▫B2: (B2, B1, 1)Spanning Tree Algorithm25Disabled since throughB5 is shorter to B1Disabled since throughthrough B2 is shorter thanthrough B3Although same hop countthrough B5 and B7, B5 has lower numberInternet Protocol (IP)26 email WWW phone...SMTP HTTP RTP...TCP UDP…IP ethernet PPP…CSMA
View Full Document