A Brief History of Communication,David Tse,Communication Systems,What goes into the engineering of these systems?,Key Ingredients,Software Hardware Communication architecture, with coding and signal processing algorithms,Communication channels can be very nasty!,Channel distortion, noise, interference,How do we communicate reliably over such channels?,Communication has a long history,Smoke signals, telegraph, telephone 1895: invention of the radio by Marconi 1901: trans-atlantic communication,State of affairs: Early 20th century,Most communication systems are analog. Engineering designs are ad-hoc, tailored for each specific application.,Big Questions,Is there a general methodology for designing communication systems? Is there a limit to how fast one can communicate?,Harry Nyquist (1928),Analog signals of bandwidth W can be represented by 2W samples/s Channels of bandwidth W support transmission of 2W symbols/s,From CT to DT,Nyquist converted the continuous-time problem to a discrete-time problem.But has he really solved the communication problem?No. You can communicate infinite number of bits in one continuous-valued symbol!,Claude Shannon (1948),His information theory addressed all the big questions in a single stroke.,Randomness,Shannon thought of both information sources and channels as random and used probability models for them.,encoder,source,channel,decoder,Everything is bits,Shannon showed the universality of a digital interface between the source and the channel.,source,Source Encoder,Channel encoder,channel,Bit stream,Information is like fluid,Every source has an entropy rate H bits per second. Every channel has a capacity C bits per second Reliable communication is possible if and only if H rendez-vous point for source and dest (Giordano & Hamdi, EPFL tech. report, 1999) Grid Location Service: quad-tree hierarchy, proximity in hashed id space (Li et al., Mobicom 2000) DREAM: Distance Routing Effect Algorithm (Basagni & Chlamtac & Syrotiuk, Mobicom 1998),Last Encounter History,Question: Do we really need a location service? Answer: No (well, at least not always) Observation: Only information on network topology available for free at a node is local connectivity to neighboring nodes But there is more: history of this local connectivity! Claim: Collection of last encounter histories at network nodes contain enough information about current topology to efficiently route packets,Last Encounter Routing,Can we efficiently route a packet from a source to a destination based only on LE information, in a large network with n nodes? Assumptions: Dense encounters: O(n2) pairs of nodes have encountered each other at least once Time-scale separation: packet transmission (ms) topology change (minutes, hours, days) Memory is cheap (O(n) per node) Basic idea: Packet carries with it: location and age of best (most recent) encounter it has seen so far Routing: packet consults entries for its destination along the way, “zeroes in” on destination,Definition: Last Encounter Table,A,B,encounter at X between A and B at t=10,B: loc=X, time=10 C: .,A: loc=X, time=10 C: . D: .,X,Fixed Destination,A,Moving Destination,A,