How to build a big wireless network? (ack: rtm) cellular (3G, WiMax) [[A picture of cellular network]] complete coverage with a set of base stations base stations are connected with wires spectrum reuse to avoid inter-cell interference mobile nodes talk directly with a base station mobile nodes are handed-off from one base station to another more capacity needed (because of too many mobile nodes)? use smaller cells! add more base station lower transmission power Alternative architecture: multi-hop [[A picture of multi-hop network]] cellular requires infrastructure (wire base stations) expensive sometimes awkward (sensor nets) sometimes impossible (military and emergency deployements) Multi-hop challenges: 1. how efficient? Why multihop? 2. how much capacity? 3. how to find a route to nodes? 4. (next class) how to find a high performance route? Efficiency: [[re-use the pic of multi-hope sensor net, one collection point]] Q: send packets directly or use multi-hop? Digression: free-space propagation, power density decreases as 1/d^2 Power radiated through the sphere (radius=d) around the antenna is constant thus, density is inversely proportional to d^2 direct: total tx power d^2 3-hop route: 3 * (d/3)^2 = d^2/3 n-hop: n * (d/n)^2 = d^2/n (Typical tx power cellphone:1-2Watt 802.11:10-100mW bluetooth:2.5mW) Few systems exist with variable tx power For now, view multi-hop as extending ranges of fixed-power radios e.g. increase coverage of a collection point Capacity of a single multi-hop route [[picture of a 6-node chain]] Q: end-to-end throughput from 1 to 6? 1Mbps radio, if all nodes were able to send concurrently, we get 1Mbps However, not true because of interference 1 and 2 cannot send at the same time (2 cannot send&receive) 1 and 3 cannot send (1 and 3's transmission interfere with 2's reception) 1 and 4? (depending on if 4's transmission interferes with 2's reception, 1 and 4 may or may not be able to send at the same time). If 4's transmission interferes with 2's reception, then we have to only allow every 4th node to transmit concurrently, resulting in 1/4 E2E throughput i.e. 1/4 Mbps System capacity of an entire network All users want to communicate n senders, n random destinations Total # of concurrent transmissions O(n) GREAT, scales with # of nodes Unforutnately, each connection has sqrt(n) hops total hops: n * sqrt(n) total e2e throughput O(1/sqrt(n)) BAD, e2e performances goes down as net becomes bigger Alternative explanation: cross section b/w sqrt(n) n connections cross, each gets O(1/sqrt(n)) Is our argument unique to wireless? Asymptotic scaling is bad, but okay if most communication is local Routing in multi-hop network How is it different from wired network? # of nodes is small frequency of link/node failure is high -Running LinkState is expensive links do not consistently deliver packets (next class) Discuss DSDV, DSR, AODV How does a node discover a route to destination? - DSDV: each node keeps n entries for all periodic broadcast route table (exchange info w/ neighbors) like DV Each (15s) broadcast interval: O(n) messages w/ O(n * n) bytes - DSR: src floods ROUTE REQ messages over network forwarding nodes append to source routes in REQ destination returns ROUTE REPLY using reversed route Each ROUTE REQ results in O(n) messages w/ O(n*n) bytes - AODV: similar to DSR, except forwarding nodes set up local state forwarding nodes create reverse routes to the source through the previous-hop they heard DISCOVERY from forwarding nodes create forward routes to the dest through previous-hop they heard REPLY from How do nodes forward packets? Guarantee loop-freedom? - DSDV: According to forwarding nodes' routing tables Each node advertises an even sequence number for itself Nodes use routes with newest seq #, if tie, lowest metric If a node detects a next hop to dst is down, advertise with an infinite metric w/ an incremented (and odd) seq # - DSR: According to the source route in each packet's header - AODV: According to forwarding nodes' local state (hop-by-hop) Similar to DSDV How do nodes detect route failure? repair? - DSDV: Detects unreachable neighbors via missing broadcasts or inability to forward packets Set infinite metrics for all routes using broken neighbor Rely on DV to re-converge - DSR: Detect broken routes when intermediate nodes fail to forward Notify source via ROUTE ERR - AODV: Missing HELLO or inability to forward packets Notify all upstream nodes None of these protocols are "scalable" DSDV, DSR, AODV BGP Per-node state N # of ASes Internet has address aggregation Address aggregation is not possible in wireless - Topology is not static - Network setup is ad-hoc (no IANA to assign AS #) Where to get the aggregation needed for scalable routing? - geographical aggregation - if destination is north of me, just forward in the direction of north Geographical forwarding Intuition: - wireless connectivity (loosely) corresponds to geographical distance - Popular "disc model". Nodes can directly communicate if within d distance Strawman: all nodes know its geographical position (lat, longtitude) forward packets to neighbors closest to destination - scalable, efficient: each node only needs to know its neighbors (Based on geographical positions, a node can easily distinguish neighbors that make forwarding progress from those that don't) - robust: if one nbr fails, route through another neighbor (In contrast, traditional routing tables contain only one single next hop choice per destination.) Biggest problem with Strawman: - cannot guarantee to find a route in all cases [[picture of a example void]] GPSR's solution: - traversing the perimeter of the "void" to get out of local minima - use right-hand rule for perimeter traversal Why cross edges are bad? [[picture of cross edges causing problem]] Solution: remove crossing edges using planarization GPSR properties: Does GPSR always find a route if one exists? - GPSR's assumption: wireless connectivity follows "disc model", all nodes have same tx range This assumption is unlikely to hold in practice. When it does not hold, one cannot plananize the graph without risking disconnection the graph - Does GPSR always find shortest paths? No. Greedy geographic forward is likely to find short paths, but it's not guaranteed to be shortest. Furthermore, "perimeter traversal" just wants to get out of a local minima and is unlikely to find shortest paths. In general, a protocol with less than O(n) state per node does not guanrantee finding shortest all-pairs path - Does GPSR always find the best route? We'll see in the next class that not all links have the same ``quality''. Geographic forwarding as stated in this paper is closer towards finding short paths than better quality paths. It's still an open research question on how to incorporate link quality in geographic forwarding.