Subject: [Ecrit] LoST civic caching issue

From: Henning Schulzrinne <[email-masked]>
Date: Tue, 10 Apr 2007 16:06:41 -0400

During our implementation of caching in LoST, one of my students came  
up with the following interesting issue:

Suppose that a system has cached a mapping for city=New York,  
state=NY and somebody moves the client to a place within that region  
that has its own mapping, e.g., a college campus. (Similar issues  
arise for places where a county has one mapping, with some part,  
e.g., the incorporated area, having a more specific mapping.) In  
those cases, a client would notice that the address has changed, but  
it still matches the old mapping, so it will not re-query.

A related problem occurs if, during a failure, a default response has  
been returned.

For geo coordinates, 'donuts' and other ways to express 'all but this  
area' conditions, which would trigger re-querying. This doesn't work  
for civic coordinates, obviously.

There seem to be several possibilities:

(1) Don't do that. In other words, if an area knows that there are  
more specific mappings, it has to be split up in some way, e.g., by  
enumerating all such areas explicitly. For example, for the  
unincorporated areas, the community name is part of the mapping, even  
though they all share the same county-wide mapping.

This probably works for most cases, but fails for the campus example,  
since the surrounding city doesn't really know about these.

(2) Mark such cases as non-cacheable. Since civic coordinates are  
only used for stationary and nomadic devices, the additional query  
load is rather modest. This is the safe approach.

(3) As a compromise between (1) and (2), mark mappings that are known  
to be leaf nodes. For example, a campus could mark its mapping as  
such since it can be pretty sure that there's nothing below that  
level. That way, laptops moving within a building don't have to  
requery. These could simply be marked as cacheable, so that no  
additional XML tags are needed.

Henning

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

---

From: Andrew Newton <[email-masked]>
Date: Wed, 11 Apr 2007 20:55:40 -0400

What about option 4?
4) Any time the civic location changes, including when it becomes  
more specific or less specific, re-query.

Also, I don't know if option 2 holds based on your description.   
There might be valid reasons to get civic location information on a  
wireless, that is wifi, link.  Or do you count wifi in the nomadic  
category?

-andy

On Apr 10, 2007, at 4:06 PM, Henning Schulzrinne wrote:

> During our implementation of caching in LoST, one of my students  
> came up with the following interesting issue:
>
> state=NY and somebody moves the client to a place within that  
> region that has its own mapping, e.g., a college campus. (Similar  
> issues arise for places where a county has one mapping, with some  
> part, e.g., the incorporated area, having a more specific mapping.)  
> In those cases, a client would notice that the address has changed,  
> but it still matches the old mapping, so it will not re-query.
>
> A related problem occurs if, during a failure, a default response  
> has been returned.
>
> For geo coordinates, 'donuts' and other ways to express 'all but  
> this area' conditions, which would trigger re-querying. This  
> doesn't work for civic coordinates, obviously.
>
> unincorporated areas, the community name is part of the mapping,  
> even though they all share the same county-wide mapping.
>
> This probably works for most cases, but fails for the campus  
> example, since the surrounding city doesn't really know about these.
>
> (3) As a compromise between (1) and (2), mark mappings that are  
> known to be leaf nodes. For example, a campus could mark its  
> mapping as such since it can be pretty sure that there's nothing  
> below that level. That way, laptops moving within a building don't  
> have to requery. These could simply be marked as cacheable, so that  
> no additional XML tags are needed.
>
> Henning
>
>
>

---

From: Henning Schulzrinne <[email-masked]>
Date: Wed, 11 Apr 2007 22:45:17 -0400

> more specific or less specific, re-query.

There are two somewhat separate caching issues: resolver and client  
caching. In the statement above, which one are you referring to?  
(Depending on the rules, for resolver caching, you could either run  
into the same problems I mentioned or never cache at the resolver.)

> wireless, that is wifi, link.  Or do you count wifi in the nomadic  

Borderline case. Usually, it's nomadic in that it's of the "open- 
laptop", "close laptop", "change location" variety characteristic of  
nomadic activity. I don't think this much matters for the problem at  
hand.

Henning

---

From: Hannes Tschofenig <[email-masked]>
Date: Sat, 14 Apr 2007 18:41:45 +0200

Hi Henning,

thanks for raising this issue and it is in fact a difficult problem.

I see two aspects with the "the donut problem",  i.e., there is a larger 
service boundary with another service area within (the hole in the 
donut). There are two cases:

* The entity responsible for the larger service area knows that there is 
a donut problem. In this case it would be reasonable to assume that this 
entity could mark the response as "non cachable". For geo one would want 
to express the service area as a donut -- currently we don't have a 
description how to describe such a shape. I  now believe that we should 
add something to the PIDF-LO profile draft.

* The entity responsible for the larger service area does NOT know about 
a potential donut problem. This case is actually not related to civic 
since it can appear in geo as well. I don't have an easy and nice answer 
for this case.

Ciao
Hannes

Henning Schulzrinne wrote:
> Suppose that a system has cached a mapping for city=New York, state=NY 
> and somebody moves the client to a place within that region that has 
> its own mapping, e.g., a college campus. (Similar issues arise for 
> places where a county has one mapping, with some part, e.g., the 
> incorporated area, having a more specific mapping.) In those cases, a 
> client would notice that the address has changed, but it still matches 
> the old mapping, so it will not re-query.
>
> (2) Mark such cases as non-cacheable. Since civic coordinates are only 
> used for stationary and nomadic devices, the additional query load is 
> rather modest. This is the safe approach.
>
> to be leaf nodes. For example, a campus could mark its mapping as such 
> since it can be pretty sure that there's nothing below that level. 
> That way, laptops moving within a building don't have to requery. 
> These could simply be marked as cacheable, so that no additional XML 
> tags are needed.
>
> Henning
>
>
>

---

From: Henning Schulzrinne <[email-masked]>
Date: Sat, 14 Apr 2007 19:32:16 -0400

On Apr 14, 2007, at 12:41 PM, Hannes Tschofenig wrote:

> I see two aspects with the "the donut problem",  i.e., there is a  
> larger service boundary with another service area within (the hole  
> in the donut). There are two cases:
>
> * The entity responsible for the larger service area knows that  
> there is a donut problem. In this case it would be reasonable to  
> assume that this entity could mark the response as "non cachable".  
> For geo one would want to express the service area as a donut --  
> currently we don't have a description how to describe such a shape.  
> I  now believe that we should add something to the PIDF-LO profile  
> draft.

Polygons can be used to describe structures with holes - you just  
have to have the polygon 'wrap around' the hole and overlap in the  
middle. It gets tedious for multiple holes.

Also, it appears that common SQL databases with geo extensions, such  
as the popular PostGIS, do not support such complicated shapes. Thus,  
it may be a better idea to compose this, as a set of coverage  
polygons [we got that] and a set of exceptions.

>
> * The entity responsible for the larger service area does NOT know  
> about a potential donut problem. This case is actually not related  
> to civic since it can appear in geo as well. I don't have an easy  
> and nice answer for this case.

That is indeed the hard case. However, I believe it is properly the  
responsibility of the exception case to notify the surrounding entity  
that it wants to be considered a 'hole'. My perception is that  
institutions, such as university campuses, with their own police  
force or ambulance corps coordinate with the local civic authorities,  
rather than just freelance. I don't know the politics or legalities  
of whether, say, the NYPD would allow the Columbia police force to be  
declared officially in charge. If all else fails, the local LoST  
resolver would have to implement local policy. This is similar to  
what happens today: If you dial 911 on a cell phone while on the  
Columbia campus, you'll be connected to the NYPD, not campus police.

Henning

---

From: "Thomson, Martin" <[email-masked]>
Date: Sun, 15 Apr 2007 19:10:45 -0500

I'm opposed to the idea of using polygon wrapping to deal with holes.  It is overly complicated, particularly when holes can easily be included in the data by linking a 0..n holes with each area.  Database schema might become more complicated, but not unmanageably so; and better that than push the problem on those who populate the database.

I agree that holes can only really be properly addressed by some form of coordination.  At the very least, we can expect that the campus authority to talk with the city authority.

Following that principle, the description of coverage areas is similar for both geodetic and civic data.  Geodetic includes a polygon (exterior) with 0..n holes (interior).  Civic includes a coverage area (a civic address, specified down to a specific level) with 0..n holes (specific civic addresses that share elements with the higher level address, but are not covered).

Such a solution is easily generalized without significantly affecting the LoST server.  The hope is that holes are not so prevalent that either data structure becomes large and onerous.

Cheers,
Martin

> -----Original Message-----
> From: Henning Schulzrinne [mailto:[email-masked]]
> Sent: Sunday, 15 April 2007 9:32 AM
> To: Hannes Tschofenig
> Cc: ECRIT
> Subject: Re: [Ecrit] LoST civic caching issue
> 
> 

------------------------------------------------------------------------------------------------
This message is for the designated recipient only and may
contain privileged, proprietary, or otherwise private information.  
If you have received it in error, please notify the sender
immediately and delete the original.  Any unauthorized use of
this email is prohibited.
------------------------------------------------------------------------------------------------
[mf2]
_______________________________________________
Ecrit mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/ecrit

---

From: Henning Schulzrinne <[email-masked]>
Date: Sun, 15 Apr 2007 21:39:42 -0400

On Apr 15, 2007, at 8:10 PM, Thomson, Martin wrote:

> I'm opposed to the idea of using polygon wrapping to deal with  
> holes.  It is overly complicated, particularly when holes can  
> easily be included in the data by linking a 0..n holes with each  
> area.  Database schema might become more complicated, but not  
> unmanageably so; and better that than push the problem on those who  
> populate the database.

I'm no friend of wrapping, either, but the problem is not the schema.  
As far as I can tell, existing open source geo databases just don't  
support these, so you have to write a custom database. Not a good idea.

>
> I agree that holes can only really be properly addressed by some  
> form of coordination.  At the very least, we can expect that the  
> campus authority to talk with the city authority.
>
> Following that principle, the description of coverage areas is  
> similar for both geodetic and civic data.  Geodetic includes a  
> polygon (exterior) with 0..n holes (interior).  Civic includes a  
> coverage area (a civic address, specified down to a specific level)  
> with 0..n holes (specific civic addresses that share elements with  
> the higher level address, but are not covered).
>
> Such a solution is easily generalized without significantly  
> affecting the LoST server.  The hope is that holes are not so  
> prevalent that either data structure becomes large and onerous.
>

I'm proposing that the holes are separate entities from the enclosing  
polygon or civic coverage area, as in

[enclosing polygon/civic without hole]
<except>
  [exception 1 (geo or civic)]
</except>
<except>
  [exception 2 (geo or civic)]
</except>
...

Obviously, no mixing of geo and civic is allowed.

I'm not sure if that's the same thing you're proposing.

This has the advantage that you can search efficiently. For polygons,  
you'll get two matches: the hole, which refers to the exception  
record, and the enclosing polygon.

---

From: "Thomson, Martin" <[email-masked]>
Date: Sun, 15 Apr 2007 21:01:59 -0500

> Sent: Monday, 16 April 2007 11:40 AM
> To: Thomson, Martin
> Cc: Hannes Tschofenig; ECRIT

I'm not sure what you mean by "support" then.  Holes as exceptions, as you show below, are easy.  But semantically, Polygons with <exterior>/<interior>* are no different.

> Obviously, no mixing of geo and civic is allowed.

That works.  It has the advantage of being the same for geodetic and civic.  It also means that the geodetic profile remains simple.

> I'm not sure if that's the same thing you're proposing.

Close enough - I wasn't thinking of any specific encoding, but the generalization is a good fit.

> record, and the enclosing polygon.

I can see several options for database design.  Determining that this isn't impossible (or at least it isn't really hard) should be enough for specification purposes.

---

From: Hannes Tschofenig <[email-masked]>
Date: Tue, 17 Apr 2007 08:05:30 +0200

Hi Henning,

Henning Schulzrinne wrote:
>> larger service boundary with another service area within (the hole in 
>> the donut). There are two cases:
>>
>> * The entity responsible for the larger service area knows that there 
>> is a donut problem. In this case it would be reasonable to assume 
>> that this entity could mark the response as "non cachable". For geo 
>> one would want to express the service area as a donut -- currently we 
>> don't have a description how to describe such a shape. I  now believe 
>> that we should add something to the PIDF-LO profile draft.
>
> Polygons can be used to describe structures with holes - you just have 
> to have the polygon 'wrap around' the hole and overlap in the middle. 
> It gets tedious for multiple holes.
>
> it may be a better idea to compose this, as a set of coverage polygons 
> [we got that] and a set of exceptions.
>
>

This is indeed an alternative. I wonder how long it takes to 
"standardize" it.
We should probably consult with Carl about this aspect.

>> about a potential donut problem. This case is actually not related to 
>> civic since it can appear in geo as well. I don't have an easy and 
>> nice answer for this case.
>
> institutions, such as university campuses, with their own police force 
> or ambulance corps coordinate with the local civic authorities, rather 
> than just freelance. I don't know the politics or legalities of 
> whether, say, the NYPD would allow the Columbia police force to be 
> resolver would have to implement local policy. This is similar to what 
> happens today: If you dial 911 on a cell phone while on the Columbia 
> campus, you'll be connected to the NYPD, not campus police.
>
I think we have to spell-out this case clearly in the document.

Ciao
Hannes

---

From: "Thomson, Martin" <[email-masked]>
Date: Tue, 17 Apr 2007 01:11:48 -0500

> We should probably consult with Carl about this aspect.

In relation to this point - I think we have concluded that this can be addressed without a dependency on database implementation.  Exceptions will need to be handled for civic - so a general solution can be used for either.

Ta,
Martin

p.s. I just noticed that one of the major commercial vendors claims support for holes; they also tout support for GML.

---

From: Henning Schulzrinne <[email-masked]>
Date: Tue, 17 Apr 2007 07:11:40 -0400

> We should probably consult with Carl about this aspect.

This is strictly a LoST syntax issue and just uses existing GML  
polygons. Thus, we don't have to wait for or depend on OGC, the pdif- 
lo draft or anything else.

Henning

---

From: Hannes Tschofenig <[email-masked]>
Date: Tue, 17 Apr 2007 14:13:19 +0200

OK. There are certainly different ways to come to the same result.
We could obviously create a structure, like
>   [exception 2 (geo or civic)]
in LoST itself.

Maybe this is just the simplest approach to pick.

Ciao
Hannes

Henning Schulzrinne wrote:
> polygons. Thus, we don't have to wait for or depend on OGC, the 
> pdif-lo draft or anything else.
>
> Henning
>