BearNotes

Matt wrote:If we do decide to use the negative responses, it would probably be best if every peer replies with a negative response, whether or not they have search results. They can just send their search results along as they get them, and then when they know there aren't anymore coming (all its peers have returned negatives), then it can send a negative to close its end of the search. Makes sense to me.

That's how the protocol is currently implemented. This way allows for the table to grow as needed, but never need to grow more. Parts of the protocol require a peer to keep track of it's connected peers using a single byte ID. This can be implemented anyway the client chooses, as it's only for that clients use, however it must fit in 1 byte and use the entire range before reusing ID's. My suggestion would be to use this along with a table of boolean values. . . adding <10 bytes per search (which should already be under 100 bytes), for tracking all the return information.

While the circular array was just an example of an implementation, I do realize that it might not be very scalable and would have the tendency to drop searches. On the other hand, I think in either case the tables will end up being pretty large no matter what. Without dropping searches, there would be no way to maximize the size of the table, but in practice it might never come up that the tables are so large that it would cause any problems.

In any case, I have to note that it will be annoying to keep track of every peer who has responded with a negative so that we can know when to delete a search from the table. Granted, just because its annoying doesn't mean we shouldn't do it or its a bad way, but if there is an equal alternative that isn't annoying, we should be doing that instead. As I tried to mention earlier, implementing the negative responses table would require keeping track of who the search was sent to, who replied with a negative, and who was no longer even there. That information could enlarge the size of the table in memory by quite a chunk. Of course, running out of memory may never be a problem in practice, but its worth consideration.

I guess the bottom line is: how easy is it to code, how well does it support the network, and how well does it run on the users machine. The non-negative response would be the easier to code, I think, but both are quite doable. The negative response would be the best for the network, to be certain, though modifications/new ideas for a non-negative approach could help that idea out a little bit. Its hard to be certain about how good either approach would be for the user's machine, but the non-negative approach would be better off if we could cap the size of the search query table.


If we do decide to use the negative responses, it would probably be best if every peer replies with a negative response, whether or not they have search results. They can just send their search results along as they get them, and then when they know there aren't anymore coming (all its peers have returned negatives), then it can send a negative to close its end of the search. Makes sense to me.

I had another thought, but I've lost it now. Maybe it will come back to me.

In order to do the circular aray idea, you would have to have an extremely (practically infinitely) large array. If you delete entry's when the negative packets are completed (all P [number of connected neighboring peers] are returned), then the table will never be larger than it needs to be. This guarantees scalability with network size and current flow of search queries/results, and no more resources/memory need to be allocated than necessary. There will also be no limit on how large this can grow (other than physical capacity), but only as needed. Scalability and search results can then be essentially guaranteed.

If you're at the beginning of a search, the end results could take a while to return, and if you delete the entry before they come back, you have lost a search. If you delete them after you get negative responses back, then it is guaranteed a search will not be lost.

Obviously, you still have the possibility of peers going down. If you lose a peer then you can assume he has negative search results, as there is no possible way to retreive the file through that peer anyway. If a new peer comes in, he will not return search results for that search, so it doesn't effect anything. No peer will have to keep track of more than P number of responses.

The spec outline that was designed in class also states that we will have negative responses, as there is no other way to determine that the network has been fully traversed.

You could just not remove an entry in the field until it becomes too old. In order to remove a search from the table, you would have to wait for every peer to return a negative (which would take some time), but you would also have to keep track of how many peers replied with a no or a yes. And then it gets even hairier if you think about, what if old peers leave and new peers arrive while a search is in progress. Maintaining a list like that would get a bit messy.

Instead, you could just have a list that is only so long, and after a number of searches, the oldest start getting bumped off. A circular array type access method would work well for this. Then, if search results ever do come back, a table look up on the unique ID would have the right routing information and the results could be passed on, or the results could be dropped if the ID no longer exists in the table. This way there is no need to keep track of who has responded to the search query, and there's no need to remove any entries.

A weakness for both of them is that if a fleet of searches come through (you might be able to assume that everyone on the network will have a search, and that a lot of them will search at once) new searches could start overwritting new searches, which would be pretty bad. The only way to fix this would be to increase the size of the array/table, which is something both methods would really have to do in a case like that. However, this is something worth thinking about, since a search will be routed through just about every peer in the end, and with a million users online we could have a couple hundred thousand active searches running concurrently. That starts to make for a pretty big table.

Well the original idea was for the end of search method to be equivelent to a stack pop. A peer would ONLY receive messages from it's neighbor peers. End of search messages would not be forwarded as a result would be. The point is that every peer must maintain a lookup table of all active searches so that it is known where to send the search results to. If there is no end of search message, it cannot be known when it is allowed to delete the lookup table entry. It could lead to less reliability.

I think that a no negative response system will be best. I think a search time limit method will be best for this. Then if the user doesn't feel like they are getting enough responses, they can adjust their search lifetime.
Plus, if every node in the network sends a negative response, the search originator will recieve at least N responses, which is quite a few to handle if the network gets large at all. Not to mention that each message passes through multiple nodes, so a search originator's neighbors will also receive a large number of negative responses.

some thoughts,
Jason

I guess the only real point is to let someone know that yes, the entire network has been searched, but I guess if we just live with the assumption That the entire network will be searched, I guess it's not needed.

The message would allow a client to display a "No results found" end of search message. However on a global scale network, this would probably come back after the client gave up waiting.

Anyone else have opinions?

Is there really a need for a negative response? The way I understand it, a peer wouldn't send a negative response until everyone of its peers had replied negative, and if that's the case then the entire network would be searched before all the negative responses would really come back, and that doesn't seem like it'd help much.

Why send negative responses at all, especially since that would add a ton of traffic to the network? Why not just let the user see what's come back and they can decide when to "time it out" by closing that search or whatever?

And does this board work?