Archive

Archive for the ‘What i’ve been reading’ Category

Vector clocks to drive delay tolerant networking

March 1st, 2011 1 comment

Vector Clocks can be used to build a knowledge of the network surrounding each node, from the local perspective of that node. This means that it would be possible to calculate some metrics about the global network, at each individual node. However, we already know [1] that in human networks, the 6 hour degree approximates the betweeness centrality of the node, which can be used as a useful metric for routing [2], so why should we complicate things further?

Benefits of vector clocks

Maintaining a vector clock [3] for each node encountered can give us extra information about the network. Assuming in our vector clock updates, we also transmit information about the network as seen by each node, we can tell both the structure of the network, and a number of extra things about the network that simply counting degree cannot.

Each node can know how out of date other nodes are, simply by checking it’s records, and seeing when an update was last received about that node, this gives some notion of distance from itself to other nodes (a.k.a. ball of radius, latency).

Indirect paths and essential links can be deduced at a global level by looking at the routes that are used to update vector clocks; where an update is received about an unknown node during an encounter, we can mark the encountered node as a possible carrier for the unknown node. And where one node is always used as a conduit for information updates about certain nodes, we know that it connects some other portion of the network.

The rate that other nodes update us with information (update rate) gives us a notion of how often contact is made with that node, the update amount, tells us how much knowledge about the network that node delivers . A node that has a high update rate is one that is encountered often, and one that has a high update amount may be well connected to other portions of the network.

Derived knowledge

Using these metrics, we can start to make other observations about the network. We now have sufficient information to attempt to predict future events [4][5]; Using the knowledge of update rate and out-of-dateness We may anticipate future encounters, based on the notion of periodicity [1], or perhaps even by simple Markov chains [6].

We can also try to calculate a notion of distance from one node to another using the update amount, out-of-dateness and out knowledge of the network structure. A nodes knowledge of the network also allows it to calculate things like it’s own centrality, degree and community membership, as well as giving it hints as to the same metrics for other nodes.

Vector clocks for location

Extending the idea further, it would be possible to share information about node movements along with network structure. Assuming nodes could detect their locations using some globally known scheme (e.g. simply using a grid-based approach to specifying location based on Latitude/Longitude), the vector clock updates can pass along updates about the last time a node visited a location, and perhaps the duration of the visit. This, combined with updates from other other nodes about their movements can give each node a picture of movements of other nodes. This in turn would allow us to make predictions[4][5] about where nodes will be in the future.

Usage

The combination of these metrics, gives us rich information to provide to a routing scheme, for example, it may be possible to adapt CAR [7] to use these metrics in it’s calculations, or a hybrid approach to BubbleRAP [2], where the global and/or local rank are based on these metrics. We may also want to devise our own scheme for routing based on this specific knowledge, however there are a large number of schemes already proposed, and it would seem  sensible to improve an existing scheme, rather than create yet another one.

Refs

1. Williamson G, Cellai D, Dobson S, Nixon P. Self-management of Routing on Human Proximity Networks Spyropoulos T, Hummel KA, eds. 2009;5918:1-12. Available at: http://www.springerlink.com/index/10.1007/978-3-642-10865-5 [Accessed July 7, 2010].

2. Hui P, Crowcroft J, Yoneki E. BUBBLE Rap: Social-based Forwarding in Delay Tolerant Networks. Networks. 2008:241-250. Available at: http://portal.acm.org/citation.cfm?doid=1374618.1374652.

3. Kossinets G, Kleinberg J, Watts D. The structure of information pathways in a social communication network. In: Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining – KDD ’08. New York, New York, USA: ACM Press; 2008:435. Available at: http://portal.acm.org/citation.cfm?doid=1401890.1401945.

4. Song C, Qu Z, Blumm N, Barabási A-L. Limits of predictability in human mobility. Science (New York, N.Y.). 2010;327(5968):1018-21. Available at: http://www.ncbi.nlm.nih.gov/pubmed/20167789.

5. Ashbrook D, Starner T. Using GPS to learn significant locations and predict movement across multiple users. Personal and Ubiquitous Computing. 2003;7(5):275-286. Available at: http://www.springerlink.com/openurl.asp?genre=article&id=doi:10.1007/s00779-003-0240-0 [Accessed July 31, 2010].

6. Musolesi M, Piraccini M, Fodor K, Corradi A, A. Supporting Energy-Efficient Uploading Strategies for Continuous Sensing Applications on Mobile Phones. Pervasive. 2010. Available at: http://www.springerlink.com/index/WH71427029706513.pdf [Accessed September 3, 2010].

7. Musolesi M, Mascolo C. CAR: Context-Aware Adaptive Routing for Delay-Tolerant Mobile Networks. IEEE Transactions on Mobile Computing. 2009;8(2):246-260. Available at: http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=4585387.

Graham’s Thesis

October 27th, 2010 No comments

I was lucky enough to get to read Graham Williamson’s thesis draft, and it reads very well, and justifies my line of research, i.e. enhancing existing routing protocols with location information.

Graham’s Persistance Based Routing (PBR) is efficient, at the same time as being reasonably reliable. I believe it is possible to further enhance his routing protocol with location knowledge. By using his hybrid scheme (Binary Spray and Focus + PBR)  as a basis, I believe that it can be made more efficient, and increase the reliability.

pbr

His hypothesis is:

Link persistence is an effective measurement as the basis for building a practical and flexible routing protocol in human contact networks in order to maximise delivery ratio.

He lists his main contributions as follows:

  • An analysis of the metrics which form the basis for routing in delay- tolerant networks (Chapter 4).
  • A procedure for generating synthetic contact traces which include periodicity and well-defined community structure (Chapter 5).
  • A study of structural metrics for routing and the effect of community- awareness on routing performance (Chapter 6: Section 6.2).
  • A self-managing mechanism for adapting window sizes inferred from periodicities observed in the contact pattern of nodes (Chapter 6: Section 6.3).
  • A metric, and protocol based on this, for routing in human contact net- works which is based on the persistence of links (Chapter 7).
  • A hybrid degree-persistence protocol able to maintain performance with limited routing information (Chapter 7: Section 7.4).

He identifies identifies four areas for future research

  1. Augmenting his PBR scheme with a message replication phase and identifying situations that respond well to this
  2. Using composite metrics to balance competing routing demands
  3. Investigating the combination of link persistence with link prediction
  4. Considering other dissemination goals such as publish-subscribe and anycast

ContactSim

ContactSim is Graham’s powerful discrete contact event simulator, which he used to process data, run his experiments and generate results. I had a preview of this a few months ago, but have not looked at it since. However, as he has now documented some of the main aspects of it, it may be possible to adopt this simulator for our own research, by augmenting it to include a notion of location. I will contact Graham for advice on how he thinks this could be achieved. The source code may be available in the group repository, so I will start investigating this.

Weekly Update 30 Apr 2010

April 30th, 2010 No comments

Last week I set out the following plan for the week:

For the next week I plan to nail down how I can implement vector clocks for location and proximity, also think about what metrics we can derive from this. At the same time I plan to read through Knox’s thesis, and read Simons paper, and try to formalise my ideas about location.

Since then, I have read Simon’s paper, which provided a nice discussion about what needs to be thought about when we deal with location. I have made progress with the simulator software. I also wrote code to process all of the data I collected from N95s, so that each reading in the database has a location associated with it. The simulator will now be able to use this to drive the location aspects of nodes.

I had some thoughts about planning a chapter about deriving location from sensor readings (e.g. WiFi position, GPS Readings, Cell Tower Positioning and Triangulation) – e.g. how can we measure the accuracy of our posistion calculations, how accurate does a the position need to be, and how should we represent location.

I also started to read up on Graph Theory, but starting with Barabasi’s book ‘Linked’ , which gives a really interesting overview of Graph Theory and how to measure aspects of complex networks. This made me realise that I will also need a chapter about this subject, and so I plan to write a review of Graph Theory based roughly based on this book.

I have also been giving more thought regarding Vector Clocks and how to use them, but I have not implemented anything yet.

My plan for next week is:

  • to get a better understanding of Graph Theory by finishing the book.
  • Implement vector clock code in the simulator, based on proximity, and work towards a location based one.
  • Read Knox’s thesis.
  • Formalise my thoughts on how to use Vector Clocks of proximity and location, and what metrics can be derived from them
  • Generate a rough outline of chapters for my thesis, and identify the main areas for the background section

Supervisor PhD Meeting 14 Apr 2010

April 15th, 2010 No comments

Had a meeting with Paddy for me to pitch my ideas.

This was the basis of my Pitch_to_Paddy

Mobility is NOT location…. see Simons paper

Discussed my ‘Hypothesis’

  • Human mobility patterns are predictable
  • Human proximity patterns are predictable
  • Knowledge of proximity and location makes opportunistic routing more efficient than proximity alone.
  • Proximity and Mobility can be used independantly to achieve the same efficiency in oppotunistic networking.
  • Mobility or Proximity can be discounted when planning opportunistic networking algorithms.
  • There are low complexity algorithms based on vector clocks that can be used for routing
  • Any given node will only need to communicate with with other nodes that they know (friends), or want to know (friends of friends).
    • Paddy suggested this might be a bit like a DNS tree, which hands off knowledge
    • Also experiments need to establish that a friend or a friends of a friends knowledge is enough to route
    • Might establish that 3 degrees is more than enouhg
    • tradeoff = you can get better efficiency if you give more coverage of the network

Local Metrics

Using vector clocks –

Range – how many hops away – build a knowledge about the network using information in the vector clocks – how do you do that? This is a PhD part.

How do we determine the important nodes? – the Aaron Quigley effect.

Nodes in your ball of radius = sphere of interest = friends, +1 hop = friends of friends, +1 = everyone else.

Dig out reviews on DTN’s – especially patterns  – but paddy thinks that the notion of location and proximity have never been used, but the patterning structures e.g. highly important update nodes.  So i need to look at ways of discovering special nodes. How do they determine that . Location thing seems to be different- find a review.

Mobility as opposed to location – gives your prediction element.

Limit the range of forward projection.

Datasets

Email GW to see if he can get a public dataset. – sign over under NDA?

Email Barry Smith to see if he knows of any datasets we can use. – Vodaphone dataset?

Email Aaron Quigley – he will know if there is any publicly available – his masters student has access to a corporate travel dataset.

Also – see Simons Paper about location.

Look up Intel Placelab dataset

Email knox to see what datasets he might have.

Progression

Paddy not sure where the Vector clocks fit in

Is it a novel implemenation mech. – i.e. am I going to use vector clocks in this thing.

I want to make a prototype. – paddy likes the idea – there are some hard questions – some novelty in there. This parts Understanding how to frame solid hypothesis. reading reviews. building exp structure, breaking out a few bits – vector clocks, heuristics about making decisions, how it all fits together.

Ideas about locations

Not fully formed so need to think a bit more about it

Future

We can turn the VC thing on its head, and make it useful for proximity and location.

I want to build prototype

Need to be careful not to spend too much time comparing to existing things if they are not really related.

Important thing is does it matter where you are when I pass you a message  – as proximity and mobility are the same – do I pass it to you because i know you see that person, or because I know you will be in the same location as that person.

Nodes can predict their own positions – share this information with other nodes – paddy suggested sharing based on the types of people – e.g. friends get detailed info, FOAF get  obfuscated location, others get much broader information.

Requests?

Does a node do calculations about other nodes, or does it ask the other node – can you get this to this person?

A little but like Agent systems?

You might have different approaches depending on who you are dealing with – e.g. message to a friends goes through friends, message to FOAF goes otherwise, everyone else – can you get it to somewhere nearer than me – or somehting…

Then we can say we of course can encrypt this information.

Plan

Paddy felt that vector clocks etc. that are used to encode e.g. double vecotr cocoks location mobility, is a solid piece of work, and if it gets into a good conference, then it is my PhD.

It will need a Order of computaion section with a complexity analysis i.e. is it N^N, Nlog(N), N^2, N^3 – dont go much beyond that  – need to analyse the algorithms at the end. well travelled ground about what the complexity of vector clocks is.

I want to Nail down what these metrics in the system are, then implement CAR using these metrics as well as coming up with my own algorithm.

Need to convince Paddy what algorithms/datasets to compare with, there needs to be a good rationale be behind it.

Need to refine the contributions bit – but this will come with time

Hypotheis section is  good – but must refine and remove negative ones – it should keep the positive ones, and prove one thing true or false – pick the one we think is most likely.

Add another hypothesis that low complexity algorithms based on vecotr clocks (30:24)  can be used.

Dont go down rabbit holes!!! Give Paddy weekly updates – every Friday – nag paddy – if he has not  responded by 10am monday – Paddy will comment back

Tighten up – look at knox Hyp section. – and write a halfpage hypothesis introduction and a one/two line hypothesis at the end.

Aside:

Can we use Barabasi way to generate new dataset – almost reverse engineer their preditions, and try to get a dataset based on it?

e.g. Random graph of streets for dublin, randomly place nodes – simulator and start to make locations as the predictions.

Dig out reviews on DTN’

Paper reading with Davide 26 Feb 2010

February 26th, 2010 No comments

Spent a few hours going over the following paper with Davide:

Kossinets, G., Kleinberg, J., & Watts, D. (2008). The structure of information pathways in a social communication network. In Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining – KDD ’08 (p. 435). New York, New York, USA: ACM Press. doi: 10.1145/1401890.1401945.

This was a very useful session, as it meant that we were forced to really understand the paper.

The authors present analysis of email datasets usin using vector clocks as a framework. They argue that the issues of out-of-date information and indirect paths are central to the understanding of the patterns of systemic communicatoion.

They explore Granovetter’s theory of weak ties, which basically says that long range connections can give better information than close connections.

This paper lead me to think that vector clocks would be a great way to discover the state of an unknown network from the point of view of each node. E.g. if a node exchanges vector clocks with other nodes it meets (perhaps with some probability, and time restriction) it could quicky build up in internal state of the following:

  • the number of nodes in its connected network
  • hops to other nodes (?? maybe ?? – )
  • the range of other nodes (i.e. the amount information update a node gives about other nodes) – which can be used as a routing metric
  • membership clustering using the ball of radius (i.e. the nodes it is up to date with to some value Τ days, which could be based on periodicity)
  • periodic degree of a node can also be used (using T as the period)  as a routing metric

Each node must have a unique identity (perhaps based on BT Mac address), even Open World nodes that are not members of the closed world can be counted when it comes to degree calculations, but only as a ramp up, as only closed world nodes (i.e. others using this algorithm) will be of interest when sending messages.

My RSS Talk next week (18 Nov 2008)

November 12th, 2008 No comments

My RSS talk is on Tuesday – as i’m struggling to get my head around a thesis topic – I have decided to do my talk on Delay Tolerant Networks (DTN) and intend to use the first paper I can find on it (which has been cited as the seminal paper on it – Li and Rus – Sending Messages to mobile users in disconnected ad-hoc networks – MobiCom ’00: Proceedings of the 6th annual international conference on Mobile computing and networking), the first paper on Epidemic routing (Amin Vahdat and David Becker, Epidemic routing for partially-connected ad hoc networks – Tech Report – 2000), and the most recent paper by Cecilia Mascolo -(CAR: Context-aware Adaptive Routing for Delay Tolerant Mobile Networks – IEEE Transactions on Mobile Computing 2008)

I think this fits in with the idea we had a while ago – but we still need to talk about the whole thing – from my recent reading there is a lot of interesting stuff on DTN and it seems to be a relatively new field.

A survey paper of the area I read recently suggested a few areas of research, one of which I am particularly interested in – how to create context profiles for users in a system to improve routing accuracy – specifically – profile a users movement habits – routes, places and regular encounters.

Ideas about context

July 29th, 2008 No comments

I’ve been reading lots of things recently about wearable computing, but previously I was reading around context and situation awareness, had a number of thoughts based on the ideas I read. Alot of my more recent reading has also referenced some of this material, so it seems  it may be useful, and I have written a short document about how I understand it at the moment.

Ideas About Context

Supervisor Meeting 17 July 2008

July 17th, 2008 No comments

Met with paddy this morning to talk about where to go from here.

I’ve been reading around Context, Privacy, Infrastructure, Management etc. in relation to wearable computing. There are a number of texts that mention it, but nothing (so far) that has dealt with it directly.

Paddy suggested reading and using the idea from http://infoblog.stanford.edu/ that you take the main assumptions about an area, list them out, then change one or two of them, and see what happens. (yet to read artical)

Also, paddy suggested to have a think about stream processing.

I should also look at the locations/conferences/groups that are doing these thing – i.e. find papers that are newer, and may not be highly cited.

Suggested conferences to look into:

MobHoc, MobiCom, Middleware, etc

Paddy also mentioned that reading can expand to fill all available time, so don’t let!

What i’ve read

October 5th, 2007 No comments

Read so far is the content of my current BibTex database can be found in the uploaded file 🙂

ToRead

is what I have on the list to read 🙂