Mathematical Analysis of Peer-to-Peer Communication Networks

[00:00:05]by um Bruce Hayek um I guess it gives me a chance to say a few things first of which is thanks to the organizers of this program and this Workshop just done a fantastic job it's great to see so many people uh here um second thing is as usual you know it's being recorded please switch off your mobile phones because if you don't switch off your mobile phones it will be picked up even if they're in silent mode so do please um switch them off um a few words only about um Bruce he'll be very well known to all of you I'm sure he's the H professor at the University of Illinois at Urbana champagne and um and we're just delighted that you're going to give this lecture um as Bruce has seen these on the web a couple of times so he knows exactly what I'm going to say now this is a very special time piece it is absolutely accurate and it is the world standard definition of mutant hour because when I turn it over that's the period for the lecture Bruce welcome and thank you thank you thank you David it's a very happy to be here thank you to the organizers uh for inviting me to give this lecture and uh so I'll be speaking about mathematical analysis of peer-to-peer communication and networks I'd like to thank um my collaborators laurant mulier suj svi former student of mine who's now at University of Texas at Austin and xiu who's out there somewhere X where are you right there uh okay and uh the overview of the presentation is to give an overview of peer-to-peer communication and networks first and I'll talk about file exchange with a fixed peer population and then uh which is work with suj and laurant and then I'll be moving on to work where there's continuous arrival of peers coming into the system uh there's a fluid analysis of mul and banovic their paper I'll review that and then talk about the work that G and I did related to that and then some close up with some discussion okay so so the first overview is pretty general just about what peer-to-peer communication is so a traditional file service we have a single server and then if a peer wants to download a file the uh the server just sends the file out and a bottleneck would be the server because of the sending out the packets one at a time so in peer-to-peer file communication a server could send out the the file and then peers can exchange the file among themselves so the capacity scales uh with the number of peers so it's a robust scalable mechanism the U it's it takes a lot of traffic on the internet this is a rough composition of internet traffic today it's taken from this study um most it's Africa and Europe large part of the world covered so peer-to-peer file transfer uh which is about half of that is movies uh software is around 20 to 30% uh games and the mixture varies over time is about 50 to 60% of the traffic on the Internet it's estimated at and um of course some service providers view this as something to get rid of and there's a lot of controversy surrounding it because of all the a lot of its copyrighted material sent illegally but there's a lot of legal uses of it and U so it's a it's something to pay attention to because it has such a large uh fraction of the uh capacity of the internet that's being used uh web pages including social networking like Facebook have 20 to 30% of the traffic in the internet web streaming for example seminar like this being streamed from the website would be uh 8% voice over IP it's it's an important application but it only uses about 1% of the capacity of the internet and then 5% for other things like news groups emails gaming and other things these things are fluctuating over time and we know we can't always just design the internet just for one mixture of traffic because things uh change over time and we could see peer-to-peer file transfer in increase or decrease it's been decreasing a bit lately because this uh Facebook um sort of been taking market share from it okay um so uh a first generation peer-to-peer system uh uh would take the seed or Source would take the file and send the complete file to neighbors and then they would send the complete file on and so forth okay it would it be kind of slow because have to download the whole file before that Pier could be useful so so the second generation system uh you take the file and break it into pieces or chunks and those pieces are sent to other peers and then those peers can start immediately sending those pieces onto other peers before they get the whole file okay so the peers can start serving pieces without waiting for the entire file it's more effective for serving large files and bit torrent which is the most popular uh peer-to-peer system uses that e donkey um use that I just have a I just put one picture up here I like this model from this paper of Xiao Louie and Chu a model of peer-to-peer live streaming uh next few slide just talk about a lot of variations there's not one peer-to-peer situation but there's a lot of different scenarios with different models and so our approach is to to look look at the different systems that are out there and then try to study two or three models that that capture a lot of the Dynamics you know and a lot of things that go on without looking at all the details that's the idea and uh this one reminds me of a jet engine with the uh fuel coming in it sort of goes in and there's a the peer-to-peer turbine mixes the you know the the packets together and what comes out the other end is a a pure stream okay so in in a live streaming there's a source looks like a spray can coming out here so this the seed uh this is piece 44 coming out this is the play time so you've got a bunch of peers here the seed just sprays out these pieces to the peers and then the peers exchange pieces as time goes on okay so the next slot this uh the seed sprays out piece 45 and then there's you know each each row here is a pier so you know this this pier is missing piece number 39 here piece 36 is being played out they're looking at their viewers seeing piece 36 they want to get piece 37 next 38 because that's what's going to be coming up on the other hand they like to collect pieces early on because those will be useful to give the other peers okay so it's good to get pieces right before the deadline it's also good to get pieces early because then you can give those to other peers so anyway I just think of this as like uh some lighter fluid or something and this going here and uh so it's an interesting model and and you there's interesting astics they they look at the density dependent Markov process model uh there so there is a limit theorem there and then you try to to uh look at optimal policies for uh if if if one peer contacts another peer which piece should they exchange to go for the last fill in the last pieces or get the early pieces um another phenomenon uh related a little bit what I said about controversy in peer-to-peer systems is the a notion of an ISP friendly peer-to-peer protocol so um I know I talked to a service provider yesterday Tim Roser I don't know if he's watching me now but uh the uh he as he was saying uh they they they can throttle a lot of the traffic because they have um deep packet inspection as being uh implemented on a lot of routers so they can look into the packet and see what kind of a packet it is and if it's a peer-to-peer packet they could drop it and so the people that write peer-to-peer software use it um well first of all they tried to disguise the packets that's one encrypting yes s uh okay ISP is internet service provider internet service provider uh there are companies that would charge you to hook up to the Internet and then if you're a peer then the traffic if you're a peer and you choose other peers at random by choosing a r a random other Pier that's got the file much of the traffic would be Crossing from one ISP over the boundary to another ISP and isps have lot of capacity inside their network but there's limited capacity from one ISP to a neighboring ISP and they have to pay to use that okay so it cost them a lot more uh in terms of you know the connectivity they have to have to the rest of the internet to have one peer coming settling in their ISP uh downloading and then uploading to to the whole rest of the world okay so the ISP would rather have you uh have a SE download a few piles uh files into their ISP and then have all the exchange going on within the ISP as much as possible and then if if the peer-to-peer protocols work that way there would be less of a nuisance to the isps and they wouldn't be throttled so much and the isps may even have some incentive to help with this uh because there is apparently some value to this uh tra TR going on and the isps want to have happy customers so so this and and and by and doing this you also end up with smaller populations so it's uh sort of raises the interest in in understanding how the the period appearer system works with smaller populations because of this ISP friendly thing okay another um Phenomenon with bed torrent and a lot of the file sharing is the idea of a flash crowd where there's some file and word passes around that there's this file available gets advertised and and peers start downloading it so you got graph something like this uh you might have several thousand peers downloading the file simultaneously for a few hours this is like the first 24 hours and then after few hours it kind of starts going down again this could vary by factors of 10 or 100 and how how high it can go and and how long it can last so there's all kinds of variation um but when you're looking at the performance you might be thinking about the startup phase or sort of the the steady state phase in the startup phase that's where there's very few copies out and you'd like to have the have the file uh be propagated um very quickly so that's just some uh to W that's the overview so to wrap up this overview I wrote an incomplete list of some performance issues peer-to-peer uh one is the peer-to peer peer selection strategies how do the peers discover other peers if they have a list of other peers how do they decide which peers to contact for pieces uh once you contact a pier what pieces do you exchange you could exchange piece lists so one Pier knows what the other has and could could give pieces there's push versus pull one Pier can kind of push pieces to another Pier or can contact peers and ask for pieces there could be heterogeneous link speeds and peers with high access to the internet tend like a bit torent they end up tending to peer with other uh peers with a similar link speeds um but there's effects of network topolog ology and the spread of the sort of the geographic spread and that gets influenced more with ISP friendly operation without the ISP friendly operation the whole thing would kind of uh build up all over the world s equal rate but because of the uh ISP friendly uh nature it sort of does tend to spread so you could see a file sort of spreading over to Europe me starting Asia and that starts in the northeast of the us it kind of spreads sort of like some infection or something like that so um the applications include file transfer uh uh a lot of it like software for example um live streaming like the uh the jet engine model I mentioned there uh video on demand uh in video on demand there could be a lot of files out there that you'd like to maybe view but be able to change channels so um you would like to have the early parts of these files widely distributed or cached and then uh so that you could sort of start seeing anything quickly and then if you stayed on something longer then it could be could fill in you know later parts and uh this is a lot of the uh the motivation for laurant I believe at um Thompson research Labs um online interactive gaming or instruction just some way to increase the uh the bandwidth to lots of users any questions at this point this is sort of ending the overview I think one one of the question is missing the behavior of selfish peer I mean peers we do don't want to do anything just want to catch okay yeah so incentives for cooperation um yeah that's one of course in bit torrent you can't upload unless you download because you you each Pier has three has four neighbors and they might give them a few files but if they don't don't get pieces back they'll drop them that's a so-called tip forap uh incentive mechanism and uh before that I mean you there's idea of currency where you get some kind of points or something for uploading and then you can spend those to download and uh yeah so incentives is a many other issues I said this in complete list of performance issues okay um okay so I'll talk a bit about file exchange for a fixed peer population and this pertains uh to the early portion of the flash crowd situation I talked about before that's here maybe it's not that good of a model but I'm thinking that there's uh by some time there's a lot of peers that are interested in a file and this model assumes there's a fixed number of peers and one seed and you want to get that file to this fixed number of peers as quickly as possible okay so there one file so there's a n peers out there and the file consists of K pieces and want measure the time and multiples of the time it takes to download one piece okay so so if the file is not split the best completion time is K log 2 of n okay this comes because it takes K time units for the seed to to give the uh the file to one other Pier so then two peers have the the file and then after K time units four peers have the file then after K time units eight peers and so forth so would take log 2 of n of those periods of length k for the whole file to get disseminated so that would be K * log 2 the file is split then the best completion time is what what log n plus it's K plus yeah K plus log 2 of n or vice versa um because it takes would take K time units to for the source just to get out the pieces and then if each of those pieces was replicated and in this doubling fashion then the last piece would take log two the N More Time to get disseminated to everywhere else so that would be K plus log 2 of N and that's optimal and there's a nice paper of Richard Weber I see him sitting over there which gives a centralized algorithm for um dist you know how would you schedule these pieces to do that okay um but if you don't have a centralized algorithm and you sort of randomly contacting neighbors uh question is can you do a similar uh completion time so this it's kind of related to the coupon collection problem so if the contacts result in random pieces it's kind of like a line collection you just go around and collect pieces without exchanging any piece information and just collect the pieces until you get a complete collection then it's a coupon collector problem you've got K pieces you want to collect till you get the whole file and uh we all know here that uh to get probably you get a complete collection after you received K log K plus K * C coupons and the coupon collector problem is approximately the probability of getting a complete collection given your receipt re a plusone number of coupons with the same mean and then if that's true then the number of coupons you receive of each type is also Pon by the splitting independent splitting property of pone random variables so the prob so the problem you don't get a uh particular coupon is uh see what's this silic should be one minus here this might be a one minus um yeah to the K uh no maybe this is a probably you don't get a coupon of a given type so this probably do get a coupon of a given type you raise that to the K power it's probably get all the coupons that you need anyway it's like that so pardon c c is an arbitrary constant so the idea is it's K log K which is bigger than K so you pick C and so it's like a sharp bound so K log K is how many coupons you need and if you go up by C * K you just adjust it up and down a little bit that sort of goes through the dynamic range of your success probability so it's kind of a concentration type result um but it's uh it's very nice it's K log K but if you knew what you were going for you just need k p pieces the extra log K is because well it's really the mean time mean number of pieces is is one it's a harmonic series you know the first piece is useful probability one the second piece is useful the probability K minus one over K third piece is useful probably K minus 2 over K and one the sum of one over those is K log K roughly so um now if you use coding at the source source coding like digital Fountain codes um then you take the K pieces and you transform those into coated pieces where each coated piece is perhaps linear combination of the original pieces so you've got m a larger number of coated pieces and the idea is that the peers only need to collect k out of the mced pieces or maybe a few more than K so then uh you don't have to fill in the complete collection the hardest thing about collecting with random coupons is getting those last few few coupons in and if you've got this coding here you just have to get enough idea of digital Fountain codes from Luby shaki midson marker you just have a a glass there and you've got a fountain of digits coming and you just collect enough and it doesn't matter which ones you collect you just have to have enough and then you can you know invert a matrix and recover your file okay so that's that's nice and then some another step is use Network coding and here each Pier collects and produces coded pieces so you've got K pieces and then maybe a seed gives that pieces uh 2 + 8 to appear and then later gives piece 1 + 8 + 7 to the pier and then this pier could add these two pieces together using mod 2 addition and then the eights would cancel out and it can produce piece one uh 27 and send it to that that pier and then as peers get more pieces they just every time they get pieces they put it in their collection and when they want to skip someone else a piece they take a random linear combination okay and there's a paper of a Deb Mard and shot showing that you can achieve all to one dissemination in K plus log n time optimal time times the constant C which is about experimentally it's a little bit more than two but maybe the proofs that come three or four something like that without exchange of Piece list you just send those pieces out you don't have to say what pieces you have and and U so we were kind of intrigued by this and we were wondering if you really need coding what if you just um just send pieces at random and well you get this coupon collector problem but uh what if you also could pull pieces and and you go you you're missing one piece and you go around asking people do you have pie P 49 okay and maybe half the people should have piece 49 if they're not done yet so um so we found out that just with a combination of push and pull we got this um I wouldn't claim it works as well but uh the the theorems we have have the same bounds so it's the same C Works uh in fact a lot of the it's hard to prove things about Network coding and a lot of problems that don't involve Network coding are really used to prove theorems about Network coding and um so anyway so that that's sort what a paper a result we had here um another but then if you take protocols further when you think about we think about it the number amount of information you have to exchange exchange a pie list is actually very small and bit torrent for example a file is broken into quarter megabyte files this is 250 kilobytes and the into 200 pieces so if you want to say what pieces you have it's just a vector of a binary Vector of length 200 okay so it's just 25 bytes which is nothing compared to the large size of the the files so you could easily collect and update the collections of all your peers and and and the neighbors you know all your neighbors and the neighbors of your neighbors and so forth so it's not that difficult so this is a a result I have a conjecture here we haven't worked too much on this and this the case when there's n peers and n pieces and the initial state is that each Pier has one piece and we use an exchange of piece lists and it's a discrete time thing so each Pier is an and and for the protocol we use each peer is an advocate for One Piece they want to see that piece get distributed and we assume there's random contacts and then if when someone contacts if P if Pier two contacts Pier Six so the peers are going to be the rows here again then if Pier Six if Pier 2 already has P six then uh the Pier 2 gets a random piece but otherwise Pier 2 doesn't have Pier Six yet since Pier Six is an advocate for P6 it makes sure that you know it gives priority to that piece so if anyone contacts Pier six it always gives out P6 first and then something else okay so actually for this model it's hard to tell what the if the peers are the rows and the pieces are the columns or vice versa it doesn't matter very much um okay there was one piece of there's a problem here at this point uh one Pier had pieces two three and six another Pier had piece two three and six so if this pier contacts that Pier can't get anything useful okay so that's why that Pier only has three pieces and everyone else has four pieces and at the end takes one extra okay so we we showed that this completes in time n plus o of log N I think it's pretty small constant but we believe that the completion time is n plus 2 with high probability okay this one I the scenario I just showed here was n + one and it's because it's so unlikely that some two peers have the same size collections it's very unlikely that they're identical so it's very unlikely that one peer can't help the other peer but there's very subtle dependencies among the collections of the peers because they've been franzinger of a matrix where you've got peers and pieces and you're trying to fill in this Matrix and you can kind of look at the processes that by rows and say how many pieces does each peer have or you can say how many peers have a given piece that's like looking at the columns and I think it's interesting but it's uh it's hard for us to to to really get I don't know if there's a really good handle on really sort of looking at both both aspects at the same time we can prove things but every time we prove something we're a little bit disappointed because we say well that worked that time but we don't have some really General way to to work with the rows and Columns of these matrices at the same time okay it's similar in that uh the one I showed you with the uh like the jet things for the live streaming there's rows and columns and you can't you can make Independence assumptions but there may not be true we'll see a little bit more of that later in fact with this so I want to move on to the third part which is file exchange with continuous arrival of peers I'll start out with a model it's largely the the in the paper of mul V 07 I'm wondering if that data is Right might be 06 um okay this is the model so have a little diagram here so the peers are coming in and so this is uh the first model I talked about I assume that all the peers were already in the system here the peers are arriving continuously so this could be after the big startup phase so peers are coming when they get their complete their collection then they leave and there's a seed that could give peers pieces there might be an initial seating so when a pier starts downloading a file it goes to some Central website and gets one piece or some small number of pieces so that it has something to give away to other peers so it starts uh somehow gets some pieces and starts uploading those two other peers it starts downloading so I'm using the the dark solid lines the flow of the peers and the dashed blue lines is the flow of the pieces so I've got a loop here this is It's like a queuing system of coupon collectors they're all in there trying to get complete collections of coupons they're trading with each other and when they get a complete collection then they leave I also view this as a model for acquisition of knowledge by a community of monks or something like that so I know there are some ancient religions where there's some they want to memorize some holy book and they can't write it all down so different people memorize different parts of the book you know when somebody dies you lose chapter 17 you know see got to make sure that people you have enough people uh sort of memorizing each piece and as people get older they know more of the book but you lose someone that's got all that knowledge and they leave right away could lead to problems okay so there's these K pieces like chapters in a Booker pieces of a file okay so uh we let C be the set of strict subsets of of this uh one Decay and then a period that has a set of pieces C is called a type c Pier okay and a type c Pier becomes a type c Union I Pier if it downloads piece I it gets that one more piece so the types of the peers are changing as they get more knowledge and the downloads are modeled as being instantaneous and a detailed Market Markoff state would be X of C uh indexed by the set of subsets proper subsets of uh of 1 to K and just keep track of the number of peers of type uh C and exogenous arrivals come and in the general model we assume that the arrival of of peers that have a collection C when they arrive is is Lambda C that's the arrival rate you could take special cases that Lambda C is zero unless C is the empty set in which case all the peers arriving come with no pieces with them and then they would rely on this fixed seed or the peers that are already in the system to to give them pieces okay we're going to assume random uniform contacts which means that the peers contact other peers I don't have a after some waiting time and then they instantaneously download a piece so offsetting this instantaneous download time is the fact the peers have to wait exponentially distributed uh period with parameter me between the downloads and and those thinking times correspond to the download times but then they make the model A Lot simpler because we don't have to keep track of who's uploading or downloading or what happens if you complete your collection while you're uploading do you just leave then or do you finish uploading to somebody else so opportunities to upload or download from another Pier occur at rate Mew got cut off it should be rate me random useful piece selection so once you decided who you're going to get a piece from you exchange a piece list at least one direction see what pieces you don't have that they have and then a random piece from that set of useful pieces is is exchange if there aren't any then that exchange is just wasted and then you have to wait another exponential amount of time with parameter me to do it again Sate but why can you canot take everything you take only one well then that's like U the first generation system where you get the whole file at once so so um okay so if I had if we if we did that from the outset I would have the whole file and I contact you I give you the whole file that could take a long time and then you give the whole file to somebody else I give the whole file to somebody else that's the so-called first generation system so the second generation system is you pick up the pieces so um you could have some adaptive chunk size or something and uh just yeah just because of time because there a tradeoff but this is the model uh and U so whether the the peers are operating in push mode or pull mode doesn't really matter in the mathematics because each peer has these opportunities at expon sort of according to a pone process of rate me independently of how many peers are in the system and you could think of that they're they're waking up and and pushing to people at that rate or that they're pulling from that rate it doesn't matter because it it scales up the total rate of these transfers is uh if there's n peers in the system it's n * mu and there so each uploading at rate mu and each downloading at rate mu okay and the peers depart immediately upon completing a collection this model so you could write down a uh Q Matrix for a Markov chain so the rate going from X to X Plus EC this is a a indicator Vector of a type c with rate Lambda C this a new arrivals or you could have U some perer that's a type c gets one piece and become C plus I so then uh this x would would increase by one in coordinate C+ I this is if C is uh strictly you know strictly smaller than K minus one pieces so that when the new perer gets another piece doesn't leave right away otherwise system collect the set system distri pardon distrib the the system will collect the whole colle that's a good question that's not part of the model that's yeah that's a good question it's a complicated question because uh these so the state if there's uh K pieces then the the set of possible types is 2 to the K minus one and uh you can have lot lots of peers could have different sets of pieces it's like I said it's like a matrix where you've got peers on one side one one side and then the pieces on the other side and you put a one or a zero which pier has which piece and and the number of peers is variable also so the number of rows would be varying so it's it's it's quite difficult to uh calculate the distribution of the time in the system for that yeah indic the compliment correct indicator of the compliment of this well see here is a set of proper subsets so this is just a way to say that c plus I is still a proper subset okay so so uh it goes down if a if type c pair becomes a type c plus I pair and and and and then coordinate C plus I will go up by one but if C+ I is a complete collection then you just have one going down and nothing up okay so it's a Markov model so there's uh in this paper was 20068 yeah this was a infocom paper and then transactions on networking uh they appli cts's theorem on density dependent jump Markoff process processes the index the processes by n parameter going to Infinity the Ral Vector scaled up by a factor n and in this model there's no seed no fixed seed okay so that all the pieces are coming with the uh arrivals and and one model is uh one piece at the door uh so you just get one piece when you enter and U it's a special case and then you scale and you you take the this state divided by n and it converges uniformly ounded intervals to OD solution X satisfying X doal QX sort of the fluid model and then they analyze that it's a symmetric system right the statistics are symmetric and uh so they it's natural thing to analyze um the symmetric starting out with a symmetric State like empty or something like that and then it simplifies because you can just keep track of the number of peers that have eight pieces and then you don't and then you s assume that all K choose eight sets have equal possibilities okay so that's what they did so they analyzed the OD for symmetric one piece upon entry model they identified the resting Point conjecture Global ASM totic stability and at the resting points they found that the sojourn times this is analyzing the OD or the the resting point of OD let T1 T2 Etc be the how long the peers spend in the different stages so this is when they all come with one piece so T1 is how long it takes them to get the second piece T2 how long it takes them to get the third piece and so forth and they found these are increasing they're increasing because the more pieces you have the longer you have to wait to get additional pieces but they're all less than two because under this model almost half the people have each piece so even if you're just missing one piece when you make the random contact you have a 50/50 chance that they're going to have the piece so the time it takes to get that last piece should be two time units okay so it's like that and this refines an earlier two-state model of Chu and Sant which has a a two-dimensional State space which kind of assume that everybody has that the number of pieces they have is uniformly distributed between one and K and then you just have a one parameter interaction and you do a calculation saying if I have a uniformly distributed number of pieces and you have what's the probability I'm useful to you okay and it'll be one given my size is bigger than your size and even even if my collection's smaller than your collection I'm still probably very likely to have something to help you and and yang and DEET had a similar uh two-dimensional model so these models basically assume that these T's are all the same and this mul evion ofic shows that it's actually a good approximation because these numbers just vary between one and two so that's good so and uh G was simulating this stuff and we found that the U stochastic packet level models showed poor performance and so we're going to focus here in a similar scenario where the next slide shows simulations for no pieces upon P entry but uh seed rate one and uh IL noros say are you are you here he he gave a talk here about a week or two before I came and I just saw the U uh the slides of it he made the same observations and some simulations there and he wrote a paper the paper uses uh the case k equal to two so that the file is broken into two pieces but I made this observation that uh although things look really nice in that mosion of a paper when you simulate it it doesn't always work as guaranteed so um this is part B here looking at the direct stochastic analysis that G and I did here so this is our first simulations that X did um so here uh the we've got pieces we get peers coming in and mu is the uh the rate that they they wake up and and try to download or the rate that they're requested to upload and then there's a seed that doesn't scale it's a rate one and rate one it it it chooses one of the peers at random and and uploads a a random useful piece to that Pier okay so this me part scales cuz it's uh which is one so if there's 100 pieces in there the upload rate is 100 + one okay that's as long as all the exchanges are useful but if they start getting the same collection of pieces then they're not useful so this is simulation uh this is the number of peers in the system and if the Lambda is8 if and this is for a k equal to 4 40 so uh if it took 80 time units upper bounding it to U download then 80 time8 would be 64 so then you would expect by Little's law to have 64 peers in there on the average and when lambda's 6 looks s so this all looks nice but then when Lambda is 1.2 or 1.4 the number of peers just starts growing like that okay so then we're wondering what what's going on and Ill talked about this four weeks ago here um so what is going on what's that mean you here this picture what yes it's up and down okay exchange yeah exchange uh yeah well maybe with K to two something I'm not sure um what happens is there there's one p that gets missing in other words symmetry gets broken and it's easy to see starting out uh if no one has anything then somebody gets a piece okay everyone's got everyone gets piece two someone comes in or some more peers come and then the seed uploads piece three and they exchange they all have pieces two and three and grows they might all have um most of the same pieces but they can't leave because that the the seed might not even uploaded one of the pieces and then when the seed uploads that piece if it uploads it to someone that's already got all the other pieces that Pier leaves it doesn't give that piece to other peers so so this is a a simulation with lambda's 6 1.4 here piece number four this is the number of peers holding piece number four on the average during the duration of the simulation okay so uh and it was it's a symmetric model so it was random but this particular sample path piece four was the rare piece okay and uh so so we have a theorem that in this case so if Lambda C is zero when C is not the empty set so peers don't come with pieces so they all come at rate Lambda with an empty set so that means they're type empty set uh then the process is positive recurrent if Lambda is less than the seed rate and transient if Lambda is bigger than the seed rate okay so so this in this model again the there's a seed here the peers are coming with no pieces and i' uh like to spend a few minutes talking about a proof here so this is a an if and only if result so there's a a positive part and a negative part talk about the negative part first it just follows the I mentioned that that you see in that slide that you end up with one piece that's that's missing so we select a initial state with many peers that are all in the one Club so one Club means they have all the pieces except piece number one it could have been piece number four as I mentioned before but since we get to choose the initial State let's just suppose uh we've got a large number peers that are all missing piece number one that's right here and then we want to show what positive probability that the system just goes off to Infinity this is assuming that the arrival rate of new peers is larger than the upload rate of the fixed seed so we start at Point like that and we want to show that we go off like that and we use a localization so we assume uh that the process restarts if ever the fraction appears in the one Club Falls less than one minus C or C is some small number so we kind of want to show that we stay in this Corridor where the number of peers uh in the one club is always a high fraction okay so I drew a picture here to show what's going on this large bloated thing here is a one Club showing that most peers are in the one Club so the new peers come we call them normal young peers if they don't have all of the other pieces yet okay they and they don't don't have piece one either if they're normal and what usually happens is they're in here and then uh all those one Club peers are are doing contacts so each of these peers gets contacted at rate me and most of the contacts come from the one Club so they get all the other pieces except piece one from these one club members there's this population here that has all that knowledge except piece one so they they go up there normally but the seed might in fact one of these and if the seed contacts one of these it might give them piece one okay then that normal young peer becomes infected got the missing piece and then they go over to this box and they can they can give other pieces to the other infected peers but uh and but here they can give that piece to the one club members and then the one club members can depart okay and the seed can also cause the one club members to depart and the infected young peers can infect other young peers with that Forbidden Knowledge like that secret knowledge okay um and uh but what we want to show is that this it's like a branching process here when these infected young peers contact another peer most peers are in the one Club so mostly they're just going to be contacting other peers in the one club and so the idea is it's a highly subcritical branching process and it dies out fairly quickly and so this stuff down here is the idea is to show that that's not important and so the main trajectory is the peers come here and they go into the one club and the main way they get out is that the seed is getting them out at rate use at s which does not scale so if Lambda is bigger than use sub s the one club just gets bigger and bigger and um and it just goes off to Infinity okay so we did a proof of that so one part is that if you look at the total number of young peers it's stochastically bounded by an MGI Infinity queuing system because rate because they've got to get their uh K pieces or k minus one pieces uh to get out of here and they're getting them at rate mu * 1 - c because one - is the fraction appears in that one club and they just have to get downloads from that one club to get get old I mean not be a young here anymore and move either you know move into the one club or if they happen to get infected then to leave the system okay so if a seed creates a new infected peer that peer can affect other peers and the sum of the times the infected peers are in the system is stochastically smaller than a busy period of an MGI 1 System you know the busy periods of queuing systems have a branching process analysis and the sum of the the times in the system during a busy period is exactly the sum of the times of how long these uh the The Infected a root infected peer is and then how many other infected peers get infected sort of how long they're going to be in the system uh infecting one Club peers and so you can bound that mean and then basically show that the mean number of peers that get that get kicked out of the one Club due to one infected Pier being infected by the seed as a bound mean and variance and then U and then the arrival rate of infected peers caused by the seed is also small and uh so basically what I said before works you can just sort of ignore this this bottom part so that's for the positive part and then um G said okay let's prove the negative part and I said gosh we got all these interactions of this Matrix how are we going to do that and we only know one technique for proving negative or positive results what's that fer Foster criteria H Foster criteria Foster criteria what you got to find a lop function so quadratic yeah so at least we can try a quadratic liop function of foster criteria it works uh and not only that uh we don't have to keep track of the detailed state but we just need to keep track of how many peers have I pieces for each value of I and that works um we're a little surpris at least I was maybe g wasn't surprised I was surprised so uh there's like two cases to think about one is if all the peers have the same number of pieces they all have ey pieces that's a bad State potentially because they could have the same set of pieces and they couldn't help each other but here we're assuming that the arrival rate of new peers is less than use of s so the fixed seed would be getting peers out of this state faster than new peers are arriving and could be getting into this state okay on the other hand if if the peers are not all have the same number of pieces so some peers have I pieces and other peers have J pieces then all of these peers with J pieces can help all of these peers with I pieces so you can have a high exchange rate there okay and and basically like by looking at these two pieces you could show that a lopo fun C I times the number of peers with I or fewer pieces squared should be a square there quadratic is the lopa function and you can show that the uh the drift of this is less than Epsilon times the number of peers in the system just by looking at these two cases you can figure that out so um so so basically that's it that proof works and um so the one Club problem shows up as additional rest so this is a stochastic analysis which was not detected in the fluid model and I think it was not detected not because the fluid model can't detect this but because they only looked at symmetric starting points so if you see the the one Club intuition that you can get from simulation and then go back to the OD and start with the initial point being asymmetric with a lot of fluid in the one Club State then you'll see that uh here so the one Club shows up as additional rest points the OD but non-symmetric states must be considered even if the model is symmetric so take the the initial State corresponding to large one club uh this model is a little bit different than in their paper and their paper they assume that each piece Pier comes with one piece chosen uniformly at random and that one's right on The Cutting Edge the seed rate is sort of proportional to the number of peers it's it's almost like use of s equal to one in the previous model and G has a poster on Thursday explaining how if you let mu go to Infinity you come up with something that's null recurrent just on the borderline between being positive recurrent and transient okay um I'll just close with this last slide there's three mechanisms are implemented or commonly discussed to enhance peer-to-peer systems one is rarest piece first selection rather than random useful and Ilia talked about that also we I think he talked about contacting three peers seeing which piece is under represented and then downloading a piece that's under represented and bit Tor also goes for rare pieces second is Network coding where peers in the seed exchange linear combinations of uh packets the third is that some peers remain in the system for some time after completing a collection they're sort of generous to stay behind so which ones of these defeat the the the one club we call it the missing piece syndrome or the one Club problem the third one third one definitely if a per remains in the system for some time after completing a collection this is against early retirement uh then you you can keep on uh uploading those pieces even after you have a complete collection how about uh rarest piece first selection what if you get stuck in that state where you've got a large number of peers that all have all the pieces except for piece one in our model we're assuming that anytime anyone can they'll always get Piece One Piece one's a rare piece and there's definitely a priority on it and it doesn't help it's still the same problem although it's probably a lot lower probability if you do simulations you might not even find that it's a a problem but um at least in theory uh you still have a problem uh and network coding it depends on the formulation and some versions of this like the one I talked about it's still a problem even with network coding that if um if you're s of missing in one dimension and it just takes one last piece to come in uh then uh the peers would um this is in the case where there's a seed so suppose everyone has a they're co-dimension one they're all missing one dimension and there's a seed that can give you a random linear combination every time someone gets that random linear combination from the seed they depart but if the total arrival rate is larger than the seed rate you'll be building up this uh one dimension Club where they're missing one dimension faster than the seed can knock them out okay but if you take the mul evion ofic model where the peers come with a random linear combination then each new pier is basically infected because each new pier could could complete the collection of any other pier and then you don't have a problem so it kind of depends on which model you're talking about uh if to see whether notwork coding U um doesn't work so that's one I want to talk about I mention the references here so what the the third one for sure and the second one for the model first model I talked about it would not help but for the Mula model if you come with one random piece upon arrival it would help because you you wouldn't get stuck um that way first one is yeah pardon the first one is open uh the rarest piece does not work it's not open it does not work rarest piece first does not uh eliminate the the missing peace syndrome because if if you're if you get into a state which Could Happen by the randomness of arrivals where there's a large number of people that all have all the pieces except for piece one then piece one is rare and they're all going to be going after the rare piece but if if a pier leaves when it gets that rare piece and if Lambda is larger than us us is the only way they can get the rare pieces from the fixed seed then it will be unstable so you so there's a proof of this what they is ination be well the proof that's I just gave the proof no no so so this is an open question it's not an open question it's closed question okay I was posing it as a rhetorical type question for the presentation I wasn't uh posing it as an open question for you to work on for the next month okay because it comes from the proof and the proof of the the negative part we're assuming every time the seed contacts anybody it always uploads piece one that would be uh because it's it's hard to analyze it any other way and uh so it basically is giving already we're assuming that priority is given to the rare piece and it's still unstable if Lambda is larger than us okay so uh yeah those are references um there's a this neuros paper that was talked about here on stability of a two trunk file sharing system um thank you [Applause] what a what a great lecture brilliant timing uh and including the questions as well we've got time for some questions or comments please can I have two question please uh the first question is uh about the t solution when you allow a compl user to remain in the network for some time to become so in this case if you increase the the arriving intensity then they I'm I'm sure that there could be some threshold that if you go beyond this this limit then the system will become unstable so in this Cas what is the reason for for the unate unstability come from the the red part denominal or for some other reason uh I've written down down a condition uh if you assume that the peers stay for exponentially distributed amount of time with parameter gamma after they leave then uh basically one over Gamma or or mu over gamma is the expected number of pieces they upload when they're there so if that's one or more then it would become stable or if it's less than one then that plus use sub s uh some linear combination you can write down the uh condition so so they they do have to stay long enough if they just stay but basically if they stay long enough to upload one piece intuitively I think you could even match that to say the peers aren't aren't useful until they get one piece so there's some some time there they're not doing anything so to make up for it they have to stay one unit of time enough to upload one piece and that seems to be just enough to make it stable so if if anyone just stays for one year after retirement or before they would retire to upload one last chapter then it would be stay very relevant for me because I thought I was retiring from another job two or three years ago it's called double dipping actually and it's a good thing yeah another questions I mean I wonder if I could um make a comment I it's a fascinating talk for me to see how you can get really quite subtle and and not intuitively obvious Dynamics out of these stochastic systems and we did have a fantastic example of this as well um a couple of years ago when a guy gave a talk about Futures Trading yeah yeah in Futures Trading you take one of the Futures that you're talking about you have a stack of bids and a stack of offers and it's trading it's event driven on the millisecond time scale and the example that he showed and this is probably easy for you guys to explain the example he showed was when a Trader without realizing it brought a new system in which had delay built into the router the delay in their system in their router drove the system into 5 Seconds of instability in which because of the delay they were buying high and selling low they lost $150 million in 5 seconds and then pulls the so I think there's a real future if you guys can understand and and counter that system but I think it's just a great talk Bruce and thank you very very much for [Applause] the