Subject: RE: [Ecrit] FW: LoST synchronous query and referals

From: "Rosen, Brian" <[email-masked]>
Date: Fri, 1 Sep 2006 07:42:03 -0400

Michael

The question I'm asking is not how long an HTTP query takes.  The
question I'm asking is how long a point-in-polygon operation takes.  The
question I raised was for a geo query.  

I do thing the "avalanche restart" problem should be addressed in
-phonebcp.  I lost track of that, Jonathan was working on it.  A very
quick Google query shows it's mentioned in -outbound and -overload, but
I don't see the randomization at the client end.

Brian

> -----Original Message-----
> From: Michael Haberler [mailto:[email-masked]]
> Sent: Friday, September 01, 2006 2:03 AM
> To: Rosen, Brian
> Cc: Henning Schulzrinne; [email-masked]
> Subject: Re: [Ecrit] FW: LoST synchronous query and referals
> 
> Rosen, Brian schrieb:
> > Do you really get a few millisecond response to a geo query with a
full
> > set of polygons?  I thought it was a bit more (but not a whole lot
> > more).
> >
> sub-5ms is doable with standard Apache / DBMS / PC platforms
> 
> I wouldnt be concerned much about steady-state load but more the
convoy
> effects after a major net outage, when many devices try to fetch
> concurrently
> 
> analogy from my ISP past:  an E3/T3 outage and re-sync on a fully
loaded
> dialup server used to have spectacular effects on the Radius servers
(up
> to 480 instantaneous session disconnects, and a clogged queue of
access
> requests/session starts thereafter)
> 
> this affects more the L7 location aquisition protocol than LoST,
though
> 
> -Michael
> 
> > Brian
> >
> >
> >> -----Original Message-----
> >> From: Henning Schulzrinne [mailto:[email-masked]]
> >> Sent: Thursday, August 31, 2006 5:30 PM
> >> To: Rosen, Brian
> >> Cc: [email-masked]
> >> Subject: Re: [Ecrit] FW: LoST synchronous query and referals
> >>
> >> The difference between the response time for a loaded (but not
> >> collapsing) and unloaded server is likely to be no more than 1:10,
at
> >> most. This is based on some extrapolation from SIP server
measurements
> >> we have done; in most systems, response time follows the classical
> >> hockey stick trajectory, with an extremely rapid rise to infinity
when
> >> the load starts to exceed 80 or 90% of capacity. (The knee of the
> >>
> > curve
> >
> >>   and the slopes depend on the variability of the arrival and
service
> >> process; details are in any book on queueing theory.)
> >>
> >> In other words, the chance that waiting a long time will help is
> >>
> > small.
> >
> >> The server is either operating in the 80%-or-below load and you'll
get
> >> an answer almost immediately or it is just as likely in the
collapsing
> >> phase where any amount of waiting isn't going to help much. For
these
> >> systems, it is much better to limit the queue size to a small
number
> >> (say, 10), as that prevents congestion collapse. Increasing the
queue
> >> size will not significantly improve the throughput.
> >>
> >> Example: For the classical M/M/1 system, a load of 0.9 produces a
> >>
> > queue
> >
> >> length of 10, so making the queue larger will only yield, at most,
10%
> >> more throughput. 20 gives you 95%, 100 pushes it to 99% load, so
lots
> >>
> > of
> >
> >> waiting for minuscule performance gains. (A real system is likely
to
> >> have smaller variability.) The TCP listen queue does this already;
I
> >> think it's typically set to 5.
> >>
> >> Typical service times without load should be on the order of a few
> >> milliseconds if you want to support more than 100 request/seconds.
> >>
> > Thus,
> >
> >>    a queue of 10 might yield you a waiting time of maybe 50 ms.
> >>
> >> In other words, not a major issue if the system design is at all
> >> competent.
> >>
> >> Henning
> >>
> >>
> >> Rosen, Brian wrote:
> >>
> >>> And I made the same mistake twice before Andy corrected me.
> >>>
> >>> -----Original Message-----
> >>> From: Rosen, Brian
> >>> Sent: Thursday, August 31, 2006 2:13 PM
> >>> To: GEOPRIV
> >>> Subject: LoST synchronous query and referals
> >>>
> >>> I think we all imagine the LoST server to be a synchronous
> >>> query/response: from a single port open to the server, you send a
> >>>
> > query
> >
> >>> and wait for the response before sending another query.
> >>>
> >>> Give a little thought to system architecture, where we are
expecting
> >>>
> > all
> >
> >>> devices to query LoST periodically (with periodicity in perhaps
tens
> >>>
> > of
> >
> >>> hours to days), or when they move out of the region/boundary
> >>>
> > supplied.
> >
> >>> That makes the query load on the server fairly high, but not
really
> >>>
> > too
> >
> >>> bad.  Certainly, a synchronous response is still appropriate, with
> >>> possibly the server permitting many simultaneous ports open.  We
do
> >>> expect to see many non-authoritative copies of the authoritative
> >>>
> > data to
> >
> >>> spread load.
> >>>
> >>> Now, suppose there was a bulk querier.  Could be a LIS
periodically
> >>> revalidating locations for example, but suppose it was the E-CSCF
in
> >>>
> > a
> >
> >>> 3GPP environment.  I chose that because response time there
matters,
> >>>
> > and
> >
> >>> it may very well have more than one outstanding call at a time.
> >>>
> >>> Now, recall that there may be a referral mechanism: you ask a
> >>>
> > question,
> >
> >>> and the local server may not have the answer, but may refer to
> >>>
> > another
> >
> >>> server for resolution.  We don't have details on that.
> >>>
> >>> If the query is actually forwarded by the original server, and the
> >>> response comes back through that server, then we do have a
problem?
> >>>
> > A
> >
> >>> query could take a long time to complete.  Is that a problem worth
> >>> worrying about?  How do we address it?  I'm not asking for an
> >>> asynchronous query.  I think that is the wrong direction.  It may
be
> >>> that the referral is NOT a forward, but a redirect.  That would
make
> >>>
> > the
> >
> >>> server not have to wait to respond.
> >>>
> >>> I think a high volume querier could have multiple persistent TCP
> >>> connections maintained (if the protocol is TCP based) and choose
an
> >>> available one as the way to handle the routine cases.  If the
server
> >>> multithreads, that combination may even work for a long duration
> >>>
> > query.
> >
> >>> Brian
> >>>
> >>> _______________________________________________
> >>> Ecrit mailing list
> >>> [email-masked]
> >>> https://www1.ietf.org/mailman/listinfo/ecrit
> >>>
> >
> > _______________________________________________
> > Ecrit mailing list
> > [email-masked]
> > https://www1.ietf.org/mailman/listinfo/ecrit
> >
> >

_______________________________________________
Ecrit mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/ecrit

---

From: Michael Haberler <[email-masked]>
Date: Mon, 04 Sep 2006 16:03:27 +0200

> question I raised was for a geo query.  
since you asked, I looked into that question. Here is what I found.

I have a data collection of shapes for Austria which would map quite
nicely on the to-be-expected shapes in an actual LoST Server ( Republic
of Austria, counties, districts, communities, and because I had them at
hand, calling areas. ).

I'm interested how the point-in-polygon (actually shape-in-polygon in
the general case) operation behaves. I only tested point-in-polygon.
Object statistics  - counts, areas, and number of points-in-polygon are
in the Excel file (see link below).

One would execute a geo LoST query in two steps: first, intersect the
point (or in case of a cell, its bounding box) with the bounding boxes
of the requested service areas. So this gives a set of candidate service
areas. All candidate areas need to be tested for exact match if there is
more than one BB match.

so in postgresql/postgis, the query would be something like:

select * from  servicearea
    where
        (create location geometry here) AND
        (qualify service area type here) AND
        location.geometry && servicearea.geometry AND      (1)
        within (location.geometry, servicearea.geometry);       (2)

The interesting operations are (1) - the bounding box intersection test
and (2) the actual test for arbitrary shapes. The BB test would involve
a spatial index and probably very fast (it is). The within-polygon test
calls upon a function (in case of Postgis from the GEOS library), which
would much slower.

My questions were:
    - how many matching BB's might be expected on average (and maximum,
while we are at it)?
    - what's the cost of the bounding box test?
    - what's the cost of the within() operator on the result set?

Results are here: http://static.mah.priv.at/public/lost-perf.xls .

Comment:
To determine the average result set size of the BB test, I used a set of
114.000 points within Austria, and recorded for each structure the count
of matching bounding boxes for that point.

Depending on the shape, there's an average of  1.5 - 1.95 bounding box
matches per point. So that means for any given point, one would have to
run within(point, shape) less than two times on average. The maximum set
size was 7 (the smaller the structure, the larger the average  result
size and also the maximum).

- The BB test costs next to nothing - testing a point wether it lies in
Austria's BB costs something like 5 mikrosecs.
- the cost of the within() operator depends heavily on the number of
points in the polygon. At 200 points, the test time is less than 20
microseconds. At 16.000 points, it can be on the order of 50 milliseconds.
- the higher number of BB matches for smaller structures is
more-than-overcompensated by the higher speed of the within() test due
to less edge points per polygon.
- for average service areas (like district or community) is always below
1msec total

So I guess that backs up my statement, Brian - especially you folks with
your many trivially-shaped counties and states in the US would be extra
fast ;-)

Note that I did not try any optimization on the data itself, or the
system (os+dbms) and there would be several ways which could speed up
operations significantly, if that is needed at all.

One strategy could be to sub-divide a shape by inscribing fully
contained rectangles, which would reduce most matches to an extremely
fast spatial index search. The remaining polygon "snippets" would be of
significantly reduced complexity and therefore fast as well.

Another approach would be reduction of the complexity of the remaining
shape tests. One would have to determine the needed accuracy, and could
e.g use the Douglas-Peuker algorithm to reduce the number of points per
polygon. Souch an optimzation would involve specifying an accuracy
parameter (like +/- 5m) and one would have to "treat" all neighbouring
polygons identically so as not to "lose coverage" at the boundaries. See
for example
http://foo.keybit.net/~simm/swfview.swf?units=dd&autocolor=1&alpha=50&map=maps/vectors/simp/all/simp.swf
and
http://postgis.refractions.net/pipermail/postgis-users/2003-February/002146.html
.

For civic addresses, all this can be pre-computed and e.g. updated
on-demand with a trigger - civic would be index compares only.

Vehicle was postgis 8.1, linux 2.6.17, dual xeon 2.4 ghz, 1 GB, scsi raid.

-Michael

ps: If you play with such queries and PostGIS - note that these queries
originally suffered from the problem described in
http://postgis.refractions.net/docs/ch05.html (small tables with large
geometries) which cause the Postgresql query planner not to use an index
even if present. This was fixed by introducing an explicit bbox geometry
column and setting it to envelope(geometry).

psps: this is not a scientific study, but back-of-the-envelope
scribblings - in particular I hope I got the execution count figures right.