NSDI 2011 Day 2 LiveBlog

Hey all,

Today's LiveBlog is even liver: Join us on IRC at chat.freenode.net, channel #nsdi11 (go here for web IRC access).

Bootstrapping Accountability in the Internet We Have

(9:01:51 AM) smowton: Ang Li, Xin Liu and Xiaowei Yang
(9:02:04 AM) malte: "the internet was designed in the old time"
(9:02:47 AM) smowton: They're worried about "traffic hijacking," defined as advertising prefixes you don't own
(9:02:48 AM) malte: example: Pakistan YouTube incident
(9:02:59 AM) smowton: and also plain old DDOS
(9:03:48 AM) smowton: morning Theo
(9:03:52 AM) twh25: afternoon!
(9:04:04 AM) smowton: motivating example: Wikileaks supression
(9:04:12 AM) malte: Attacks are bad: disruptive, politically motivated, costly
(9:05:26 AM) malte: Largest DDoS attack observed in practice has exceeded 100 Gbps
(9:06:17 AM) malte: Question: Can we make the intertubes secure?
(9:06:20 AM) smowton: Challenge: secure the internet in a way that's incrementally deployable *and* helps early adopters
(9:07:13 AM) smowton: previous work: secure BGP (BGP + signing)
(9:07:27 AM) malte: There are various existing approaches: Secure BGP, packet source authentication
(9:07:41 AM) malte: reference for the latter: "Packet passport" in NSDI 2008
(9:07:49 AM) smowton: Other previous work: source-signing, in which packets contain unforgable source information to prevent spoofing
(9:08:11 AM) smowton: Natural application to preventing DoS as you know who's actually doing it
(9:08:24 AM) malte: What's missing? Why is the internet so vulnerable?
(9:09:24 AM) malte: two types of "natural identifiers" in the internet: (1) IP addresses, (2) IP prefixes
(9:09:51 AM) malte: but they cannot be used for accountability ("identify bad guys") because they can be spoofed, like all network-layer identifiers
(9:10:05 AM) smowton1: they introduce "IPA", IP-made-accountable, which tries to produce non-spoofable network identifiers
(9:11:24 AM) smowton1: Criticism of existing approaches:
(9:11:32 AM) smowton1: PKIs require heavyweight deployment
(9:11:36 AM) smowton1: web-of-trust isn't reliable
(9:11:44 AM) smowton1: and self-signing has obvious problems
(9:13:05 AM) smowton1: proposal: use DNSSEC and BGP to serve the role of a PKI
(9:14:16 AM) smowton: In the case of DNSSEC, this means using a reverse-resolution record as proof of ownership of some IP range
(9:14:55 AM) smowton: or rather, attesting to your owning a keypair that you will use to sign source addresses
(9:15:23 AM) mas90: that's pretty cool. I bet the IETF would love that
(9:16:18 AM) smowton: Apparently there's a break in the chain of trust between in-addr.arpa and root allocators like ARIN; just an administrative thing though
(9:16:55 AM) smowton: the top-level guys would just assert ownership of some key, but presumably SSH-style has-the-key-changed will suffice for something so commonly encountered
(9:16:59 AM) malte: (and supposedly to be resolved shortly: "by end of March")
(9:16:59 AM) mas90: ha
(9:16:59 AM) mas90: better be quick :)
(9:17:56 AM) malte: certificate distribution is supposed to be "in-band", by piggy-backing on BGP announcements
(9:18:07 AM) smowton: BGP messages enclose certificates in the obvious way, a la HTTPS supplying the complete cert chain
(9:18:19 AM) malte: the data would go into "optional" and "transitive" path attributes
(9:18:34 AM) smowton: the chain should mirror netblock delegation
(9:19:20 AM) malte: Each certificate is ~650 bytes
(9:19:31 AM) smowton: They're concerned about overhead, and solve it by sending only unsent certificates
(9:19:45 AM) smowton: but really, how significant is the complete throughput of BGP relative to actual dataplane traffic?
(9:19:47 AM) malte: in order to avoid sending those big-ish certs all over the place all the time, the certs relating to neighbours are cached
(9:20:07 AM) malte: smowton: agreed
(9:20:41 AM) smowton: cert revocation is done in the ordinary existing fashion: revocation lists (eagerly flooded to your delegatees) and expiry dates
(9:22:41 AM) malte: eval in terms of three dimensions: performance, security and adoptability
(9:23:52 AM) malte: for time's sake, they only present the overhead on normal BGP and some adoptability analysis in the talk
(9:24:35 AM) malte: their BGP trace contains a total of 118M updates, with ~44 occuring per second
(9:25:08 AM) smowton: they measure in terms of bytes/second for a BGP speaker taking part in their protocol but otherwise exchanging the same updates as a real-world speaker
(9:25:36 AM) smowton: they find some examples of updates that would take 60 seconds to process
(9:25:43 AM) smowton: but 99.4% would be <= 30s
(9:26:06 AM) smowton: presumably this would get better as routers are already expensive; could include some specialist crypto h/w
(9:26:42 AM) smowton: adpotability problem: there's a Cisco router that explodes when they set their cert attribugte
(9:26:53 AM) smowton: mundane bug
(9:27:25 AM) smowton: this is their incremental adpoptability: BGP speakers will preserve their new attributes even if they don't understand them themselves
(9:28:33 AM) smowton: and that's that

 

Privad: Practical Privacy in Online Advertising

09:35 < malte> Next talk: Serving ads from localhost for Performance, Privacy and Profit
09:35 < malte> Saikat Guha, Microsoft Research India; Bin Cheng and Paul Francis, MPI-SWS
09:35 < avsm> woah cool, usenix is serving ipv6 dhcp!
09:36 < malte> experimental talk: he's going to keep the talk short and leave lots of time for questions
09:36 < malte> Today's web ads suck: quality sucks, so flood users with lots of them
09:36 < malte> loading ads from third-party servers slows down page rending
09:37 < malte> the way it works today is that a "broker" of some sort (e.g. Google) marries advertisers' ads to publisher websites
09:38 < malte> money flows from advertisers to brokers to publisers
09:38 < malte> users don't get a cent
09:38 < mas90> users are the saleable product :-)
09:39 < smowton> users get content :)
09:39 < malte> cookies leak information to ad broker -- Google knows every page we visit
09:39 < smowton> problem: persistent cookies as the broker domain is the same even if the site is different
09:40 < smowton> they're worried that an evil employee will sell the Google Ads database
09:40 < smowton> Goal: work in the current world
09:40 < malte> including "the current click-fraud model" :-)
09:41 < malte> they define privacy as "unlinkability"
09:41 < smowton> "private enough"
09:41 < smowton> keep the tracking-for-targeted-ads thing without letting anyone know who you are
09:42 < smowton> basically because otherwise only the altruistic advertisers will adopt
09:42 < malte> at the same time, they don't want to trade off privacy for poorer advert quality
09:42 < smowton> and there are obvious problems with that sentence :)
09:42 < smowton> "Scalable: yada yada yada"
09:43 < malte> fundamental decision: the most trusted entity in the advertising ecosystem is the client's own computer
09:44 < malte> they are wondering what data *needs* to leave the local system
09:44 < malte> they could achieve privacy by either having an anonymization network in between the user and the broker (e.g. Tor)
09:45 < malte> but the problem with that is that it doesn't allow detection of click fraud
09:45 < smowton> problem: most anonymisation protocols would make the ad-broker vulnerable to click fraud
09:45 < malte> so they introduce another party called the "dealer"
09:45 < malte> they assume that the dealer and the broker don't ever collude
09:46 < smowton> the dealer anonymises and filters for fraud
09:46 < smowton> the broker plays his old role but with anonymised input
09:46 < malte> the local agent monitors user behaviour and builds a local user profile
09:46 < smowton> why would anyone be a dealer?
09:47 < malte> broker sends a bunch of ads to the dealer, who then sub-selects the ones to present to the user
09:47 < malte> the agent has got a local cache of ads that is populated by the dealer
09:47 < malte> (question: how does the broker know that the ads have actually been viewed?)
09:48 < malte> (their solution is that the client reports ad event to the dealer, who reports to the broker... but that assumes that both agent and dealer are honest)
09:48 < smowton> the dealer seems like a vague creature; this basically moves the risk from the broker to the dealer
09:49 < smowton> ah, the ad reports are encrypted; the dealer can't peek
09:49 < malte> actually, they use PKI to sign the reports so that the dealer can't modify them
09:49 < smowton> assuming again he doesn't collaborate with the broker
09:49 < malte> it only strips the private information
09:49 < malte> *he
09:49 < smowton> which here == IP
09:50 < malte> now he's asking people what they want to know more about
09:52 < malte> Q: is the user profile information actually safe on the user's own machine?
09:52 < malte> A: probably more so than anywhere else...
09:53 < malte> Q: is this really compatible with the current ad model? Does it support CPI and CPC models?
09:54 < malte> A: Yes, all of view/click/other events can be reported through their ad event reporting system
09:55 < smowton> A: yup
09:55 < smowton> Q: why would a broker trust dealers to stay functional?
09:56 -!- googie [80e80ef5@gateway/web/freenode/ip.128.232.14.245] has joined #nsdi11
09:57 < smowton> A: They can use the privacy benefits as a selling point
09:58 < smowton> but ad-vendors don't really sell to users
09:58 < smowton> I could see tinfoil-hat websites that desperately need ad revenue selling it to their user
09:58 < smowton> but pretty much only them
09:58 < smowton> Aside: they don't care about AdBlock: it works either way, and only 12% of people use them
09:59 < smowton> I'm actually surprised how high that figure is
09:59 < malte> indeed
09:59 < malte> looks like people in Saudi Arabi haven't been educated about spyware toolbars yet ;-) (40% install third-party tool bars)
10:00 < smowton> Q: why-t-f would you be a dealer? how will you make money?
10:00 < smowton> A: they won't; they'll be run as a public service by the EFF or someone like that
10:00 < smowton> Alternatively, MS could be both -- with appropriate legal oversight
10:01 < smowton> seems to me like the same deal as laws requiring them not to be evil in using their ad data
10:01 < smowton> I suppose so long as no one angry employee has the keys to the dealer's logs and the broker's logs also...
10:02 < malte> Q: How do you prove to me that the local agent tool (supplied by YOU) is not going to act as spyware and leak my data?
10:02 < smowton> ooooh, answered a question by "removing the weasel words"
10:02 < smowton> take that, wikipedia
10:03 < smowton> it's 10:03; the Usenix heavies are descending
10:05 < malte> opinion: nice talk as it was controversial and incited discussion, and the presenter is actually keen on this stuff
10:05 < malte> but I don't really buy the architecture
10:05 < smowton> yup same
10:05 < smowton> like most things, no incentive to improve without direct pressure from the users
10:06 < smowton> and most people don't know or care about the problem
10:06 < smowton> alright
10:06 < smowton> next talk

Bazaar: Strengthening User Reputations in Online Marketplaces

(10:06:47 AM) smowton: Ansley Post, MPI-SWS and Rice University; Vijit Shah and Alan Mislove, Northeastern University
(10:07:21 AM) smowton: Marketplaces are what you might suppose: eBay et al
(10:07:32 AM) smowton: point being, untrusted people trading with others
(10:08:54 AM) smowton: economists observe that your eBay reputation does matter
(10:09:00 AM) smowton: you'll get more money for the same item
(10:09:06 AM) smowton: but: accounts can be created for free
(10:09:30 AM) smowton: so can start anew
(10:09:33 AM) smowton: or, can collude
(10:10:38 AM) smowton: apparently there are often very cheap listings that have "positive feedback guaranteed"
(10:11:13 AM) smowton: Potential solutions:
(10:11:24 AM) smowton: 1. Make it hard to join to begin with, e.g. must present some ID
(10:11:34 AM) smowton: sucks because it's a barrier to honest people too
(10:11:44 AM) smowton: 2. Use escrow, but only appropriate for expensive things
(10:12:24 AM) smowton: 3. Transactions happen in person; the website just pairs you up. Problem: transfers online fraud to plain old mundane mugging
(10:12:36 AM) smowton: 4. Insurance: spreads the cost
(10:14:09 AM) smowton: Their solution keeps existing feedback systems but tries to bound fraud
(10:15:37 AM) smowton: They build a "risk graph": accounts that have traded are joined by an edge weighted by dollar amount
(10:16:09 AM) smowton: Turst = max-flow between buyer and seller
(10:16:29 AM) smowton: presmably the hope is that fraudulent people will be walled off from honest ones by negative-feedback edges
(10:16:59 AM) malte: I don't quite see how this solves the sybil attack problem
(10:17:09 AM) smowton: trading with your own sockpuppets doesn't help as they're a clique
(10:17:15 AM) smowton: they might as well be the same person
(10:17:19 AM) malte: ah, I see
(10:17:23 AM) malte: yeah
(10:17:37 AM) avsm: cunning
(10:18:05 AM) mrry: nice aspect of this is that, at least on eBay, you have to pay a %age fee, so there is cost to building up these edges (if you're only pretending to sell things)
(10:18:05 AM) malte: unless of course you make your sockpuppets do a bunch of genuine transactions in order to link them into the honest network
(10:18:35 AM) smowton: sure, so you're required to be at least X% honest
(10:18:41 AM) smowton: I think this is the strong bound on fraud
(10:18:42 AM) mrry: @malte, you'd still have to make large transactions with your sockpuppets, which would be expensive
(10:19:17 AM) malte: mrry: yeah, point taken - you can't trade a bunch of 50c items and then defraud someone for $5000 as you don't have enough flow
(10:19:34 AM) smowton: your best bet would be to genuinely be an honest trader for a few months
(10:19:47 AM) smowton: then quickly make off with everyone's wallet whilst they're still in the dark
(10:21:42 AM) smowton: aha, this is challenge #1
(10:21:58 AM) smowton: the ability to steal a lot of cash before the users realise
(10:22:12 AM) smowton: solution: your edge is suspended whilst there's an outstanding transaction
(10:22:22 AM) smowton: limits the volume of trade you can perform if your reputation is low
(10:22:29 AM) smowton: seems reasonable with or without bazaar
(10:23:46 AM) malte: same principle as the London tube Oyster charging system :-)
(10:24:04 AM) twh25: ?
(10:24:30 AM) smowton: challenge #2: how to induct new users? Friends can vouch, lending their credability, or can do link-escrow (buy your initial credability, I think)
(10:24:41 AM) malte: (Oyster deducts the maximum fare while you're en-route, then credits you when you touch out)
(10:25:32 AM) smowton: problem: max-flow over a large graph is expensive.
(10:26:06 AM) smowton: They assert real-world graphs are usually of a shape that makes this okay
(10:26:30 AM) smowton: and also note we only need a vague is-it-greater-than-X answer, not the true result
(10:27:38 AM) smowton: cunning technique for cheap maxflow: construct log(n) [where n is the highest weight link] graphs where graph i is restricted to edges with weight >= 2^i
(10:28:04 AM) smowton: for big sellers you'll find that the sparse top-level graph says yes right away
(10:28:27 AM) malte: in fact, if you assume that the majority of your sellers is honest, your performance is okay
(10:28:29 AM) smowton: only need to check the lowest-level full graph if your maxflow would be very small
(10:28:49 AM) smowton: Eval:
(10:29:18 AM) smowton: crawled a 90-day trace of ebay (8m auctions)
(10:29:46 AM) smowton: used 80% to form a risk network using observed feedback
(10:30:12 AM) smowton: remaining 20% used to test
(10:30:36 AM) smowton: found that total amount users could steal is always <= their previous successful transactions
(10:30:44 AM) smowton: sounds like something that could be proved rather than experimented :)
(10:30:57 AM) malte: yeah, surely that's a fundamental property of their system?
(10:31:20 AM) smowton: <5% false positive rate
(10:31:36 AM) smowton: where that means it flags an auction that actually led to positive feedback
(10:31:48 AM) smowton: they blame their lack of knowledge before 90 days ago

Dewdrop: An Energy-Aware Runtime for Computational RFID

(11:03:11 AM) smowton: defn: "computational RFID" = computer that works solely using RF energy
(11:04:00 AM) smowton: scenario: pervasive monitoring for the elderly
(11:04:30 AM) malte: (or, alternatively, government surveillance and spying :-P)
(11:04:32 AM) smowton: they don't like cameras for this purpose, due to privacy concerns
(11:04:47 AM) smowton: motes are neat but battery powered
(11:06:19 AM) smowton: so, let's use computational RFIDs, in which the reader powers the thing but it can do some on-board computation (and storage?)
(11:08:20 AM) smowton: they use the Intel WISP: a CRFID prototype that can be read from 4m and has an accelerometer and temperature probe
(11:09:16 AM) malte: challenges:
(11:09:22 AM) malte: 1) CRFIDs have tiny energy stores
(11:09:30 AM) malte: 2) programs have different energy needs
(11:10:28 AM) smowton: their runtime coordinates program runs by accumulating enough energy to run it to completion before allowing it to complete
(11:10:58 AM) smowton: runtime executes in a standby mode that allows us to monitor energy levels whilst still charging
(11:11:13 AM) smowton: we want to avoid failure in which we run out of useful energy during a run
(11:12:24 AM) malte: this is difficult because programs have different energy needs and we cannot always predict how much a particular program is going to need (e.g. because it is non-deterministic(
(11:13:05 AM) malte: 3) CRFIDs have inefficiencies
(11:13:25 AM) malte: e.g. overcharging might cause issues as the chip requires a fixed input voltage
(11:13:44 AM) smowton: because voltage regulators throw away energy in that situatioin
(11:13:54 AM) malte: 4) Energy is harvested even while executing
(11:15:01 AM) malte: energy is largely harvested from EM waves in the environment, but due to frequency hopping and friends, it's often hard to predict where/how we can harvest energy even in the near future
(11:15:23 AM) smowton: gives a couple of examples of programs' performance vs. initial charge
(11:15:35 AM) smowton: shows that the optimal charge differs from program to program
(11:15:43 AM) malte: to make things worse, the amount of energy required to run a program may also depend on environmental features such as the distance to the reader device!
(11:15:45 AM) smowton: to the point that some programs fail entirely at the optimal V for another
(11:16:08 AM) smowton: extra problem: some of their examples are nondeterministic
(11:17:19 AM) malte: Dewdrop is a 'clever' runtime environment that takes energy needs into account
(11:17:47 AM) malte: the overall goal is to maximize execution rate (defined as the rate of successful task executions=
(11:17:55 AM) smowton: just adaptively find the initial charge V per program
(11:18:09 AM) smowton: continuously adapts, so if you move the reader it'll gradually converge on the new correct answer
(11:18:48 AM) smowton: it looks like they assume we want to run the same program in a loop
(11:19:05 AM) smowton: so waste due to failed runs is considered equivalent to wasted time due to excess charging
(11:20:06 AM) smowton: implementation: exponential backoff to avoid polling sucking up all the available energy
(11:21:32 AM) smowton: eval: compare task execution rate to some unspecified hardware mechanism
(11:22:00 AM) smowton: manage to get higher success rate at short range and some success rate from far away when the builtin mechanism fails entirely
(11:24:06 AM) smowton: Eval 2: big bag of tags, how many of them do something useful vs. output power
(11:24:12 AM) smowton: again they beat the builtin mechanism

SSDAlloc: Hybrid SSD/RAM Memory Management Made Easy

(11:31:19 AM) malte: starts off by talking about the use of memory in networked systems
(11:31:39 AM) malte: (1) as cache, (2) index to reduce disk pressure
(11:32:52 AM) malte: they identify a problem in the fact that cost of DRAM in a commodity server scales linearly up to 64 GB, but super-linearly beyond
(11:33:05 AM) malte: second problem: disk speed is not increasing (seek etc.)
(11:33:27 AM) malte: usually tackled by using high speed disk arrays, but they are expensive
(11:33:56 AM) malte: their proposal to address the problems: use flash as memory
(11:34:55 AM) malte: first problem is addressed by scaling beyond the 64 GB limit by adding flash memory
(11:34:55 AM) malte: doing this would reduce the TCO and lead to more efficient server utilization
(11:35:42 AM) malte: with flash, random reads are very fast, but writes are slow
(11:36:32 AM) malte: so this solves problem number 2
(11:36:50 AM) malte: now the question is how to integrate flash into the well-known memory hierarchy
(11:37:08 AM) malte: initially, SSDs were put into the same category as disks because they are non-volatile
(11:37:26 AM) malte: they don't believe this and argue that SSDs should be used and addressed like memory
(11:37:49 AM) malte: existing approaches: use SSD as swap or via mmap
(11:37:59 AM) malte: + applications don't need to be modified
(11:38:09 AM) malte: - native pager only delivers 10% of SSF performance
(11:38:21 AM) malte: - even a flash-aware pager only gets up to 30%
(11:38:37 AM) malte: they assert that this is because OS pagers weren't designed for flash memory
(11:40:20 AM) malte: the concrete issue appears to be in the fact that a page on the SSD is first brought into memory, so we have to read $pagesize worth of data, instead of just the object we're interested in
(11:40:38 AM) smowton: I wonder how similar this is to XIP stuff
(11:40:55 AM) smowton: which afaik allows you to execute stuff off disk without pulling pages into ram
(11:41:00 AM) smowton: not sure how they implemented that
(11:41:26 AM) malte: they suggest non-transparent tiering, which requires applications to be modified so they are flash-aware
(11:41:26 AM) smowton: prsumably it would require an interface for fine-grained disk use whilst mimicing memory however
(11:42:50 AM) malte: but this is tedious because it requires a lot of knowledge about flash memory and more verbose code due to bookkeeping code for the flash object store
(11:43:03 AM) malte: instead, their goal is to run 'mostly' unmodified apps
(11:43:40 AM) malte: they want to use DRAM more efficiently and not cache at page granularity but below that
(11:43:57 AM) malte: plus they want to use the SSD well and limit the number of writes
(11:44:05 AM) malte: (which is fairly standard stuff)
(11:44:26 AM) smowton: they want to use it as a a log-structured object store
(11:44:35 AM) smowton: which is interesting as afaik some drives do that in firmware already
(11:44:41 AM) smowton: and/or you should use JFFS2 :)
(11:45:52 AM) malte: they establish a 1 page = 1 object correspondence
(11:46:04 AM) malte: now this obviously may waste huge amounts of memory
(11:46:22 AM) malte: so they have a compacted cache in RAM
(11:46:56 AM) malte: (as well as a page buffer, where the pages are expanded from the compact representation)
(11:49:43 AM) malte: they implemented the on-demand paging (generation of sparse pages from compact representation) using mprotect
(11:50:29 AM) malte: on the lowest level, there is a log-structured object store on the SSD
(11:50:47 AM) malte: to which things from the in-RAM compact cache are written out
(11:52:09 AM) malte: on the SSD, they use a copy-and-compact garbage collector to write live and dirty objects and remove everything no longer required ('freed' objects and objects written elsewhere)
(11:53:22 AM) malte: in addition to the OPP model (one object per page), they also support a MP model, which is more like traditional paging
(11:53:40 AM) malte: their entire implementation is ~11k lines of C++
(11:54:11 AM) malte: they give some numbers for the overhead of SSDAlloc's runtime intervention
(11:54:28 AM) malte: they are all sub-microsecond
(11:54:37 AM) malte: the combined overhead is 0.83 µsec
(11:56:17 AM) malte: for a bunch of benchmarks, they get performance improvements between ~5x and ~17x over using SSD as swap
(11:56:23 AM) malte: (for SSDAlloc-OPP)
(11:56:35 AM) malte: the advantage for SSDAlloc-MP is less pronounced (1.5x to 3x)
(11:59:08 AM) malte: for a macrobenchmark (memcached), they see a large benefit in using SSDAlloc-OPP for small requests
(12:00:12 PM) malte: as the request size increases, the advantage diminishes and ultimately all approaches are the same
(12:01:15 PM) malte: they claim their approach delivers 90% of raw SSD performance, compared to max. 30% for other approaches

SliceTime: A Platform for Scalable and Accurate Network Emulation

(2:25:51 PM) smowton: SliceTime: A Platform for Scalable and Accurate Network Emulation
(2:27:39 PM) smowton: Testbeds are expensive, and simulations lack fidelity
(2:27:46 PM) smowton: so, let's hybridise the two
(2:28:53 PM) smowton: Connect real nodes using a realtime simulation that can also insert virtual nodes
(2:30:31 PM) smowton: Simulations are often not capable of operation in real-time
(2:31:00 PM) smowton: and thus we can easily break this hybrid world because their perception of time drifts apart
(2:32:03 PM) smowton: They fix this by slowing down the real nodes
(2:33:02 PM) smowton: Want to operate on real nodes
(2:35:31 PM) smowton: They run the "real" nodes inside VMs
(2:35:43 PM) smowton: and barrier if they run ahead of simulation time (or vice versa
(2:37:28 PM) smowton: Implement using Xen
(2:38:39 PM) smowton: Xen has means to tell the difference between virtual and "wall" time; presumably these are appropriately mangled
(2:40:20 PM) smowton: yup indeed they are
(2:41:37 PM) smowton: Wrote an 802.11 equivalent of tun to allow them to inject virtual wireless packets into real nodes
(2:44:30 PM) smowton: eval shows it's fairly accurate at making machines think links are the way the simulator says they are
(2:44:55 PM) smowton: found that barrier density and so accuracy functions as you'd expect too
(2:46:16 PM) smowton: Overhead is pretty severe at 1ms accuracy, but much better if you'll settle for coarse grains
(2:47:04 PM) smowton: eval 2: is it useful? Duplicated an experiment called AODV, which had some people conduct real-life random walks with laptops and observe when they were able to communicate
(2:47:34 PM) smowton: took the GPS traces from that experiment and made a model of the world they were occupying
(2:47:58 PM) smowton: found that the simulated world gave a very similar result to the real one

Accurate, Low-Energy Trajectory Mapping for Mobile Devices

(3:32:49 PM) smowton: Better version of MapMyRide etc
(3:34:29 PM) smowton: GPS is troublesome because it's rather energy intensive
(3:36:20 PM) smowton: idea: use GPS infrequently to pin your location down, then use less precise methods like WiFi or 3G localisation more frequently
(3:37:33 PM) smowton: 3G is especially nice because you have to idly watch the signal anyway to decide when to roam and listen for push notifications
(3:38:50 PM) smowton: They also use a compass and accelerometer at low power to decide when to use their different localisation techniques
(3:43:04 PM) smowton: 3G is also super tricky in urban areas because your perceived location will often veer wildly around the place in response to radio propagation
(3:45:03 PM) smowton: They find that smoothing over time actually helps a lot
(3:45:08 PM) smowton: as does snapping to roads
(3:45:15 PM) smowton: but only *after* the smoothing
(3:47:27 PM) smowton: They use an HMM to make the naive point sequence sane, using knowledge both of what one is likely to see in a given grid, and the probability of moving from one grid to another
(3:49:33 PM) smowton: They're actually pretty tolerant of wild leaps about the grid, as they need it to deal with black spots in coverage
(3:51:52 PM) smowton: The later snap-to-roads stage doesn't tolerate leaps because they want a conceivable track at the end of the day
(3:54:30 PM) smowton: Eval: compared against GSM radio analysis + snap-to-roads and to GPS every 4 mins + snap-to-roads
(3:55:09 PM) smowton: They characterise sub-sections of the trace as "right" or "wrong" and find that they're right 2.4x as often as the best of their rivals
(3:55:34 PM) smowton: Find that the grid-mapping stage is very important
(3:56:01 PM) smowton: hints from sensors only give them an extra 5%, but apparently help a lot in certain restricted situations

Improving Wireless Network Performance Using Sensor Hints

(4:05:06 PM) smowton: Observation: people's mobility is often characterised by static periods and mobile periods
(4:05:20 PM) smowton: WLAN et al are basically set up for static operation and do badly when moving
(4:06:36 PM) smowton: The right way to work differs (ignore short-term variations or not?)
(4:06:44 PM) smowton: So it'd be nice to figure out when we're moving and when we're not
(4:10:03 PM) smowton: They can also use other physical hints, e.g. direction, speed
(4:12:29 PM) smowton: Application 1: rate adaptation in WLAN.
(4:12:48 PM) smowton: Took some physical connectivity traces and simulated TCP operating over the simulated links
(4:13:02 PM) smowton: found only got 35-60% of best possible using standard ways to rate adapt
(4:13:55 PM) smowton: In mobile situations there are lots of burst drops
(4:14:15 PM) smowton: In static situations they're mostly random losses
(4:15:36 PM) smowton: Invented a new way to rate-adapt if you're moving: reduce rate on loss; keep a 10ms history and don't try any bitrate that failed in that history
(4:16:40 PM) smowton: Simulated again: found 10-25% better TCP throughput using their method
(4:16:59 PM) smowton: compared to some existing protocols: SampleRate, RRAA, RBAR, CHARM
(4:17:13 PM) smowton: Worse when static by up to 28% due to pessimism
(4:17:27 PM) smowton: so: as we said at the start, it'd be good to figure out when we're moving and switch modes
(4:18:39 PM) smowton: real-world eval:
(4:18:52 PM) smowton: 2 environments, 10 movement patterns
(4:20:30 PM) smowton: did 17-28% better than existing schemes when hint-aware
(4:20:41 PM) smowton: i.e. switching their scheme on and off as appropriate to movement
(4:21:24 PM) smowton: They concede that PHY layer techniques are better, e.g. SoftRate
(4:21:35 PM) smowton: but they require h/w modifications
(4:21:43 PM) smowton: they got 90% of softrate however
(4:22:26 PM) smowton: they claim that a two-mode setup is better than a continuous sliding scale between static and mobile operations
(4:22:47 PM) smowton: evidence using moving traces at various speeds: *any* movement yields highly correlated losses; none yields no correlation
(4:23:15 PM) smowton: Example 2: picking an AP
(4:24:56 PM) smowton: Scan more often when moving
(4:25:55 PM) smowton: also wrote a fairly cunning thing that learns where the APs are and uses a heading hint to figure out when it can minimise handoffs by ignoring a tempting AP in favour of one it thinks will shortly come into range
(4:26:52 PM) smowton: Example 3: using speed to optimise vehicle mesh nets
(4:27:11 PM) smowton: estimate connection time proportional to 1/speecd
(4:27:30 PM) smowton: found it helps when planning how much to send to a vehicle you see