TOC |
|
Algorithms for decision-making based on civic address inputs are described. This includes an algorithm for determining whether one civic address is entirely contained within another. Other algorithms and supplementary discussions relating to the use of civic addresses in describing boundaries are included.
This Internet-Draft is submitted to IETF in full conformance with the provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as “work in progress.”
The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html.
This Internet-Draft will expire on July 29, 2010.
Copyright (c) 2010 IETF Trust and the persons identified as the document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the BSD License.
1.
Introduction
2.
Civic Address Model
3.
Civic Address Boundaries
3.1.
Determining if an Address is Within a Boundary
3.2.
Algorithm Summary
3.3.
False Negatives
3.4.
False Positives
3.5.
Address Boundary Limitations
4.
Boundary Combining Algorithms
4.1.
Boundary Unions
4.2.
Boundary Intersections
4.3.
Avoiding False Positives
5.
Example
6.
IANA Considerations
7.
Security Considerations
8.
Informative References
§
Authors' Addresses
TOC |
Civic address information ([RFC4776] (Schulzrinne, H., “Dynamic Host Configuration Protocol (DHCPv4 and DHCPv6) Option for Civic Addresses Configuration Information,” November 2006.), [RFC5139] (Thomson, M. and J. Winterbottom, “Revised Civic Location Format for Presence Information Data Format Location Object (PIDF-LO),” February 2008.)) can be used to describe the location of an entity in terms of the human-constructed environment. This description can be be made more or less precise through the addition or removal of labels (respectively).
A less precise civic address can be used to describe a zone or region by only including sufficient labels to identify the region. This method is used in the Location-to-Service Translation (LoST) protocol (Hardie, T., Newton, A., Schulzrinne, H., and H. Tschofenig, “LoST: A Location-to-Service Translation Protocol,” August 2008.) [RFC5222], to convey information to a client about the extents of a particular region where service is guaranteed to be consistent.
This information, called a service boundary, allows a client to make decisions about civic addresses other than the one used to query. If another civic address is determined to be "within" the service boundary, the client does not need to request service information from the LoST server.
LoST does not provide a definition of "within" for civic addresses. This document describes an algorithm that provides a definition for whether a civic address is contained within another address.
Other operations on civic addresses are described, allowing client software to make decisions about the intersection and union of two civic addresses.
TOC |
The simplest model of a civic address is that which considers it as an unordered set of labels. Each label is assigned zero or more values; each value has an associated language (and script).
The format in RFC 4776 (Schulzrinne, H., “Dynamic Host Configuration Protocol (DHCPv4 and DHCPv6) Option for Civic Addresses Configuration Information,” November 2006.) [RFC4776] allows for values to be given to labels with different languages or scripts. No special considerations apply in applying this model.
The format in RFC 5139 (Thomson, M. and J. Winterbottom, “Revised Civic Location Format for Presence Information Data Format Location Object (PIDF-LO),” February 2008.) [RFC5139] uses multiple civicAddress elements to form a single address if labels are provided in multiple languages. Thus, when extracting address information from a PIDF-LO (Peterson, J., “A Presence-based GEOPRIV Location Object Format,” December 2005.) [RFC4119] document, a civic address in this model is formed from all civicAddress elements in the same tuple.
A civic address describes a series of spatial partitions or regions. Every address includes an implied partition that identifies the habited portion of the Earth. Every label with a value describes a partition of space at a specific scale. The intersection of the spaces described by all the included labels is the resulting location.
The algorithm described in this document relies on the following rule:
The location described by a set of civic address labels is entirely contained within the location described by any subset of those labels.
The following characteristics of civic addresses have no bearing on the algorithms described:
More sophisticated models and algorithms are possible in the presence of additional information about the address data. If this sort of information is present, many more options are available for processing addresses. The simple algorithms in this document operate on the address information only, but do not preclude use of outside information.
TOC |
A civic address boundary has the same format as a civic address.
A civic address boundary describes a region by containing fewer labels than the addresses of locations contained within the boundary. In that respect, the boundary might be considered an incomplete address, allthough a boundary is actually a valid civic address that simply describes a larger location.
A larger region is described by including fewer labels; a smaller region might be described by including more labels, or labels that are more specific.
For example, if the described region is the province of Zeeland in the Netherlands, only two labels are required: a country of NL and an A1 field of ZE.
A label that is omitted from the civic address boundary indicates that civic addresses within the boundary may have any value for the label.
This process does not provide any assurance that a civic address exists, only that if it does exist, it is contained entirely within the described boundary. Determining whether such an address actually exists usually requires additional information, and is therefore not considered by this document.
TOC |
A civic address is entirely enclosed within a boundary if every label of the boundary that has a value has an equivalent value in the address. A civic address boundary can entirely enclose another civic address boundary.
Case folding is performed on values before comparison.
A label is considered equivalent if at least one value from the boundary has the same value in the address for the same language (and script). If values are provided in multiple languages, any language that is present in both boundary and address can be used.
[[TBD: If the label contains different values for the same language, does this override the above - in light of the Austrian example below, it's probably better that the more lenient equivalence test is used.]]
Labels that have the same value, but a different language, are not equivalent. Without information on different translations of the label, the label must be considered to be different.
TOC |
The algorithm for determining whether an address is contained entirely within a given boundary can be summarized by the following pseudocode:
SET iswithin = true FOR EACH label IN boundary DO: IF boundary[label] exists THEN: SET equivalent = false FOR lang IN boundary[label] DO: IF boundary[label][lang] == address[label][lang] THEN: SET equivalent = true END END IF NOT equivalent THEN SET iswithin = false END END RETURN iswithin
TOC |
This test can produce false negatives for a number of reasons:
By using additional information, a system might be able to identify more equivalent labels than the basic algorithm. This can remove some, if not all such false negatives. However, a system should not rely on another system having and employing such knowledge.
TOC |
This algorithm guarantees, that a civic address that exists is entirely contained within a boundary.
No allowance is made for addresses that do no exist. It is trivially possible to construct a non-sensical or non-existent civic address that is considered "within" a boundary using this algorithm. This can be done by starting with the civic address boundary and adding arbitrary values to labels that do not already have values.
TOC |
The address format allows a limited expression for address boundaries. This representation can only be used in limited applications. This simple boundary expression is not suitable for any application that is sensitive to false negatives.
In the case of boundary interchange between LoST servers (Schulzrinne, H. and H. Tschofenig, “Synchronizing Location-to-Service Translation (LoST) Protocol based Service Boundaries and Mapping Elements,” March 2010.) [I‑D.ietf‑ecrit‑lost‑sync] would likely require multiple specific boundaries to describe a single boundary. A number of well-known cases would generate a very large number of such boundaries. For instance, if a boundary runs up the middle of street that places odd and even house numbers on opposite sides of the street, each house on that street would require an individual address.
Concatenation of address data can introduce other limitations. The limited set of address labels can mean that each field can hold several discrete units of data. An address mapping (Wolf, K. and A. Mayrhofer, “Considerations for Civic Addresses in PIDF-LO - Guidelines and IANA Registry Definition,” July 2009.) [I‑D.ietf‑geopriv‑civic‑address‑recommendations] might specify that underlying data be concatenated and mapped to a single label.
The algorithm described here operates on entire labels only. The algorithm and boundary expression does not allow only part of a label to change. If concatenated data is included in the one label, a generic processer cannot know of this and distinguish between parts that must match and parts that do not matter. To do so would require knowledge of the modes of concatenation, what delimiters were used and it would require syntax that distinguishes important parts from unimportant parts.
TOC |
In some cases, it might be necessary to combine boundaries. This section describes three algorithms, including simple union and intersection.
TOC |
The union of two civic address boundaries (or addresses) is a single boundary that contains all civic addresses that are contained within either original boundary.
The boundary that forms the union of two other boundaries is formed of all labels that are equivalent in both boundaries.
If labels differ in the two boundaries, then the resulting union might also include addresses that are in neither boundary. Only use this algorithm if false positives are acceptable.
SET union = empty address FOR EACH label IN boundary1,boundary2 DO: IF boundary1[label] EQUIV boundary2[label] THEN SET union[label] = boundary1[label] END END RETURN union
The value of any label in a union of boundaries should include a value for all languages that are present in both boundaries.
TOC |
The intersection of two boundaries (or addresses) is a single boundary that contains all addresses that are found in both original boundaries.
The boundary that forms the intersection of two other boundaries is formed of the combined value of the labels from both boundaries.
If the value of any label is present in both boundaries, but not equivalent, the two boundaries do not intersect for the purposes of this algorithm. In practice, while it is possible that two such boundaries could overlap, this algorithm cannot detect this. Furthermore, the civic address representation does not provide a way to express such an overlap.
SET intersection = empty address FOR EACH label IN boundary1,boundary2 DO: IF boundary1[label] exists AND boundary2[label] exists AND boundary1[label] NOT EQUIV boundary2[label] THEN ERROR No overlap END IF boundary1[label] exists THEN: SET intersection[label] = boundary1[label] ELSE SET intersection[label] = boundary2[label] END END RETURN intersection
The value of any label in an intersection of boundaries may include a value for all languages that are present in both boundaries.
TOC |
The service boundaries in LoST (Hardie, T., Newton, A., Schulzrinne, H., and H. Tschofenig, “LoST: A Location-to-Service Translation Protocol,” August 2008.) [RFC5222] rely on the absence of false positives when determining if an address is within a boundary. False negatives are tolerated, because this only results in the LoST client making another request to discover an unchanged service. A false positive is not desirable because a device could retain a service mapping that is likely to be invalid.
[I‑D.ietf‑ecrit‑rough‑loc] (Barnes, R. and M. Lepinski, “Using Imprecise Location for Emergency Context Resolution,” January 2010.) describes an algorithm where an address is formed of the intersection of multiple boundaries. If no intersection the result of this algorithm was failure, then usable location information cannot be provided to the LoST client.
For a LoST service boundary, the goal is to provide a boundary that contains as few labels as possible. For a rough location, the goal is to provide an address with as few labels as possible. False positives are not desirable in either case.
Thus, both cases have a similar goal, and both have a more precise address to operate on. In LoST, this is the address used to query the server; for rough locations, this is the address that is to be hidden.
To avoid false positives in determining whether an address falls within a boundary, labels from the more precise address are added. Any label where the inputs to the union or intersection disagree is given a value from the precise address. This ensures that the resulting address or boundary entirely contains the precise address.
Alternatively, given a precise address and a number of boundaries that are to be combined by either union or intersection, an address or boundary can be formed by removing all labels from the precise address that do not have a value in any boundary. This algorithm produces an identical result.
SET result = precise address FOR EACH label IN result DO: SET found = false FOR EACH boundary IN boundaries DO: IF boundary[label] exists THEN SET found = true END IF not found THEN CLEAR result[label] END RETURN result
TOC |
The following civic address boundary (shown in XML form (Thomson, M. and J. Winterbottom, “Revised Civic Location Format for Presence Information Data Format Location Object (PIDF-LO),” February 2008.) [RFC5139]), describes a region of Los Angeles, USA.
<civicAddress xmlns="urn:ietf:params:xml:ns:pidf:geopriv10:civicAddr"> <country>US</country> <A1>CA</A1> <A2>Orange</A2> <A3>Los Angeles</A3> <A4>Anaheim</A4> <PC>92802</PC> </civicAddress>
The following address includes additional labels, it does not change the value of any label.
<civicAddress xmlns="urn:ietf:params:xml:ns:pidf:geopriv10:civicAddr"> <country>US</country> <A1>CA</A1> <A2> Orange </A2> <A3>Los Angeles</A3> <A4>Anaheim</A4> <PRD>South</PRD><RD>Harbor</RD><STS>Boulevard</STS> <HNO>1313</HNO><NAM>Disneyland</NAM> <PC>92802</PC> </civicAddress>
An equivalent address that would not be considered "within" the boundary by the generic algorithm would be one that specified Orange County for the A2 label. It's also possible to unambiguously describe the location without fields A1 through A4, since a ZIP (postal) code of 92802 provides sufficient information.
Thus, the following variant is not considered "within" the boundary, even if it is the same address. That is, without context-specific knowledge, the algorithm produces a false negative on this address.
<civicAddress xmlns="urn:ietf:params:xml:ns:pidf:geopriv10:civicAddr"> <country>US</country> <PRD>South</PRD><RD>Harbor</RD><STS>Boulevard</STS> <HNO>1313</HNO><NAM>Disneyland</NAM> <PC>92802</PC> </civicAddress>
TOC |
This document has no IANA actions.
[[RFC Editor: please remove this section prior to publication.]]
TOC |
This document describes a civic address model and algorithms for manipulating civic addresses and boundaries in the same format. There are no known security considerations arising from the described application of these algorithms.
TOC |
TOC |
Martin Thomson | |
Andrew Corporation | |
Andrew Building (39) | |
Wollongong University Campus | |
Northfields Avenue | |
Wollongong, NSW 2522 | |
Australia | |
Phone: | +61 2 4221 2915 |
Email: | martin.thomson@andrew.com |
Karl Heinz Wolf | |
nic.at GmbH | |
Karlsplatz 1/2/9 | |
Wien A-1010 | |
Austria | |
Phone: | +43 1 5056416 37 |
Email: | karlheinz.wolf@nic.at |
URI: | http://www.nic.at/ |