15-744: Computer NetworkingReview9Sensor Nets Metric: Communication• Lifetime from one pair of AA batteries • 2-3 days at full power• 6 months at 2% duty cycle• Communication dominates cost• < few mS to compute• 30mS to send message-0.3505.23810.82516.41322.0000.00800000000000000 2.00400000000000154 4.00000000000000307Time v. Current Draw During Query ProcessingCurrent (mA)Time (s)Directed Diffusion• Data centric – nodes are unimportant• Request driven:• Sinks place requests as interests• Sources are eventually found and satisfy interests• Intermediate nodes route data toward sinks• Localized repair and reinforcement• Multi-path delivery for multiple sources, sinks, and queries2Diffusion (High Level)• Sinks broadcast interest to neighbors• Interests are cached by neighbors• Gradients are set up pointing back to where interests came from at low data rate• Once a sensor receives an interest, it routes measurements along gradients34Illustrating Directed DiffusionSinkSourceSetting up gradientsSinkSourceSending dataSinkSourceRecoveringfrom node failureSinkSourceReinforcingstable pathTAG Introduction• Programming sensor nets is hard!• Declarative queries are easy• Tiny Aggregation (TAG): In-network processing via declarative queries• In-network processing of aggregates• Common data analysis operation• Communication reducing• Operator dependent benefit• Across nodes during same epoch• Exploit semantics improve efficiency!• Example: • Vehicle tracking application: 2 weeks for 2 students• Vehicle tracking query: took 2 minutes to write, worked just as well!7SELECT MAX(mag) FROM sensors WHERE mag > threshEPOCH DURATION 64msBasic Aggregation• In each epoch:• Each node samples local sensors once• Generates partial state record (PSR)• local readings • readings from children • Outputs PSR during its comm. slot.• At end of epoch, PSR for whole network output at root• (In paper: pipelining, grouping)812 3459Illustration: Aggregation12345112341123451Sensor #Slot #Slot 1SELECT COUNT(*) FROM sensors10Illustration: Aggregation123451122341123452Sensor #Slot #Slot 2SELECT COUNT(*) FROM sensors11Illustration: Aggregation123451122313411234531Sensor #Slot #Slot 3SELECT COUNT(*) FROM sensors12Illustration: Aggregation123451122313451123455Sensor #Slot #Slot 4SELECT COUNT(*) FROM sensors13Illustration: Aggregation1234511223134511123451Sensor #Slot #Slot 1SELECT COUNT(*) FROM sensors14Synopsis Diffusion (SenSys’04)• Goal: count the live sensors in the network0 1 0 0 0 0 0 0 0 0 1 00 0 1 0 0 0 0 0 0 0 0 1idBit vector0 1 0 0 0 0BooleanOR0 1 0 0 1 00 1 1 0 0 00 1 0 0 0 0 0 1 0 0 1 00 1 1 0 1 00 1 0 0 1 00 1 0 0 1 10 1 1 0 1 1Count 1 bits4Synopsis should be smallApproximate COUNT algorithm: logarithmic size bit vectorChallenge15Synopsis Diffusion over Rings• Each node transmits once = optimal energy cost (same as Tree)Ring 2•A node is in ring i if it is i hops away from the base-station•Broadcasts by nodes in ring i are received by neighbors in ring i-116EvaluationApproximate COUNT with Synopsis DiffusionSchemeEnergyTree41.8 mJSyn. Diff.42.1 mJ0.000300.251390.502490.753581.004680 0.225 0.450 0.675 0.900RMS ErrorLoss RateTree Syn. Diff.More robust than TreeAlmost as energy efficient as TreePer node energy Typicalloss rates15-744: Computer NetworkingL-14 Network TopologyTrends in Topology ModelingObservation• Long-range links are expensive• Real networks are not random, but have obvious hierarchy• Internet topologies exhibit power law degree distributions (Faloutsos et al., 1999)• Physical networks have hard technological (and economic) constraints.Modeling Approach• Random graph (Waxman88)• Structural models (GT-ITM Calvert/Zegura, 1996)• Degree-based models replicate power-law degree sequences• Optimization-driven models topologies consistent with design tradeoffs of network engineers18A few nodes have lots of connectionsRank R(d)Degree dSource: Faloutsos et al. (1999)Power Laws and Internet Topology• Router-level graph & Autonomous System (AS) graph• Led to active research in degree-based network modelsMost nodes have few connectionsR(d) = P (D>d) x #nodesLmaxl(g) = 1P(g) = 1.08 x 1010 P(g) Perfomance (bps)PAPLRG/GRGHOTAbilene-inspired Sub-optimal0 0.2 0.4 0.6 0.8 1 101010111012 l(g) = Relative Likelihood 20PA PLRG/GRGHOTStructure Determines PerformanceP(g) = 1.19 x 1010P(g) = 1.64 x 1010 P(g) = 1.13 x 1012 2118Routing: Chord• Associate to each node and item a unique id in an uni-dimensional space• Properties • Routing table size O(log(N)) , where N is the total number of nodes• Guarantees that a file is found in O(log(N)) steps23Routing: Chord Basic LookupN32N90N105N60N10N120K80“Where is key 80?”“N90 has K80”24Routing: Finger table - Faster LookupsN80½¼1/81/161/321/641/12819Aside: Hashing• Advantages• Let nodes be numbered 1..m• Client uses a good hash function to map a URL to 1..m • Say hash (url) = x, so, client fetches content from node x• No duplication – not being fault tolerant.• One hop access• Any problems?• What happens if a node goes down?• What happens if a node comes back up? • What if different nodes have different views?21Consistent Hash• “view” = subset of all hash buckets that are visible• Desired features• Balanced – in any one view, load is equal across buckets• Smoothness – little impact on hash bucket contents when buckets are added/removed• Spread – small set of hash buckets that may hold an object regardless of views • Load – across all views # of objects assigned to hash bucket is small22Consistent Hash – Example•Smoothness addition of bucket does not cause much movement between existing buckets•Spread & Load small set of buckets that lie near object•Balance no bucket is responsible for large number of objects• Construction• Assign each of C hash buckets to random points on mod 2n circle, where, hash key size = n.• Map object to random position on circle• Hash of object = closest clockwise bucket08412Bucket1441Geometry’s Impact on Routing• Routing • Neighbor selection: how a node picks its routing entries• Route selection: how a node picks the next hop • Proposed metric: flexibility • amount of freedom to choose neighbors and next-hop paths• FNS: flexibility in neighbor selection• FRS: flexibility in route selection• intuition: captures ability to “tune” DHT
View Full Document
Unlocking...