The UP PIO Field: Finding Up in an Unmanaged Network
draft-howard-up-pio-00

Abstract

It is difficult to find a path through an unmanaged network with multiple routers. This document describes a new Prefix Information Option field which can provide information to routers to find a path.

Status of this Memo

This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.

Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at http://datatracker.ietf.org/drafts/current/.

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."

This Internet-Draft will expire on May 20, 2012.

Copyright Notice

Copyright (c) 2011 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 Simplified BSD License.

This document may contain material from IETF Documents or IETF Contributions published or made publicly available before November 10, 2008. The person(s) controlling the copyright in some of this material may not have granted the IETF Trust the right to allow modifications of such material outside the IETF Standards Process. Without obtaining an adequate license from the person(s) controlling the copyright in such materials, this document may not be modified outside the IETF Standards Process, and derivative works of it may not be created outside the IETF Standards Process, except to format it for publication as an RFC or to translate it into languages other than English.

Table of Contents

• 1. Introduction
• 1.1. Requirements Language
• 2. Format
• 3. Use Cases
• 3.1. Default Route
• 3.2. Walled Garden
• 3.3. ULA
• 3.4. Delegated Prefix
• 4. Implementation
• 4.1. Host Behavior
• 4.2. Tie Breaking
• 4.3. Multiple Paths
• 4.4. Route Withdrawal
• 5. Examples
• 6. Evaluation
• 7. Additional Work Required
• 8. Alternatives
• 9. Security Considerations
• 10. IANA Considerations
• 11. References
• 11.1. Normative References
• 11.2. Informative References
• Author's Address

1. Introduction

This document describes a new Prefix Information Option field to be used in unmanaged networks (such as home networks) to find a path to a given prefix. This PIO field is not intended to replace dynamic routing protocols, and will not find the best path to a given destination, though it can provide useful information to routers.

1.1. Requirements Language

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119. [RFC2119].

2. Format

       0                   1                   2                   3
       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |     Type      |    Length     | Prefix Length |L|A|R|U| Rsvd1 |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                         Valid Lifetime                        |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                       Preferred Lifetime                      |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      | Distance      |           Reserved2                           |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                                                               |
      +                                                               +
      |                                                               |
      +                            Prefix                             +
      |                                                               |
      +                                                               +
      |                                                               |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

The use of L and A bits are specified in rfc4861. The use of the R bit is specified in rfc3775.

This format represents the following changes over those RFCs:

• Upstream Prefix (U) 1-bit router address flag. When this UP bit is set to 1, indicates that the prefix was learned, rather than configured.
• Rsvd1 Reduced from a 5-bit field to a 4-bit field to account for the addition of the above bit.
• Distance An 8-bit metric used to determine distance and prevent loops.

The UP bit is used to find a path through an unmanaged network. When a router learns prefix information from a Router Advertisement with the UP bit sent, the router SHOULD add that prefix to its own RAs. When sending RAs containing the learned prefix, it MUST increment the Distance value by one.

3. Use Cases

3.1. Default Route

The most common implementation of this field would be the advertisement of a default route, where Prefix Length = 0 and Prefix = 0. An Internet access provider could use Router Advertisements to customer gateways with the UP bit set, and a distance of 0, to indicate the border of the administrative domain and the default gateway for the customer access router. That customer access router, having learned the default gateway, SHOULD add the prefix to its routing table, then SHOULD include this information in its own RAs. When the router sends RAs including this prefix, it MUST increment the Distance in those RAs to indicate that it is one hop further than the origin or the prefix.

3.2. Walled Garden

For a network provider who does not provide a default route, the UP option can be used to indicate that a prefix is available. For instance, an operator who only wanted traffic for its hosted services on 2001:db8::/32, would send an RA for that prefix to the access gateway, with Distance=0. That gateway SHOULD add the prefix to its routing table, then SHOULD include the prefix in its own RAs, and MUST increment the Distance in those RAs to indicate that it is one hop away from the border.

3.3. ULA

Unique Local Addresses may be used for a variety of reasons [RFC6204]. When a router generates a ULA prefix, it MUST include that prefix in RAs. It SHOULD include the UP option field, with a Distance = 0. When another router learns that prefix, it SHOULD add the prefix to its routing table, then SHOULD include the prefix in its own RAs, and MUST increment the Distance in those RAs to indicate that it is one hop away from the border.

3.4. Delegated Prefix

In home network scenarios, routers are often also DHCPv6 servers. When a device is a DHCPv6-PD server, and receives a prefix to be used for host address assignments (regardless of setting of M-bit), if that device is also the router for that prefix, that router becomes authoritative for the prefix. "Authoritative for the prefix" is analogous to the notion of the "delegating router" responding to a request from the "requesting router" per [RFC3633]. In other words, when a router receives Prefix Delegation, it SHOULD include that prefix in its RAs, and SHOULD set the Distance to 0. Note that other values are possible, but reduce the possible diameter of the network.

Note that in this way, more specific routes may be propagated through the network via Router Advertisements. The longest match rule applies, and establishes the route preference. See Examples section.

4. Implementation

4.1. Host Behavior

Hosts use RAs and the PIO to find their next hop, and for address autoconfiguration. Nothing in the use of the UP bit changes these behaviors, though it is possible that hosts will learn multiple prefixes, and might have multiple paths to the same prefix. It is expected that these are harmless. Details of path selection are left to implementers.

A host MAY use the Distance metric to select a better bath for a prefix. A host might learn multiple prefixes from which SLAAC may be used. This is not a new function introduced with the UP bit, and host behavior is expected to be unchanged.

4.2. Tie Breaking

When a router learns the same prefix from two other routers, and both RAs have the same Distance, a tie-breaker mechanism is required. The tie-breaker could be arbitrary, such as the time the RA was received, or it could be based on (e.g.) the Preferred Lifetime value, the layer 2 link type, or other suitable informationr. Implementers MUST have a tie-breaker rule or rules to resolve all ties.

4.3. Multiple Paths

A router receiving multiple RAs for the same prefix may choose to discard the path not chosen, or may add the route to its routing table with a higher Administrative Distance.

4.4. Route Withdrawal

As with other RAs, when an RA is received from a router with no information for a prefix, even if that router had previously provided prefix information, the receiver SHOULD remove references to that prefix from its routing table. Similarly, if no RAs are received from a router, the prefix SHOULD be removed. Further, it SHOULD send RAs without that prefix.

When the Valid Lifetime has passed, the route MUST be removed. When the Preferred Lifetime has passed, the route MAY be lowered in preference.

5. Examples

Consider the example in Figure 1, in which a network has two upstream ISPs, ISP A and ISP B. A different router connects to each ISP. Routers A and B connect to their respective upstream ISPs, and a Router C and Router D connect to the same link. Routers C and D share another link, causing a potential loop situation. A Host #1 connects to the shared link between Routers A, B, C, and D. A Host #2 connects to the shared link between Routers C and D.

   +----+-----+                              +-----+----+    \
   |   ISP A  |                              |   ISP B  |     \
   |          |                              |          |     | Service
   +----+-----+                              +-----+----+     | Provider
        |                                          |          | Network
        |                                          |          / 
        |                                          |         / 
   +----+-----+                              +-----+----+    \
   | Router A |                              | Router B |     \
   |          |                              |          |      |
   +----+-----+                              +-----+----+      |
        |                                          |           | Home
        |                                          |           | Network
    ----+---------------------+--------------------+---        |
        |                     |                    |           |
   +----+-----+          +----+-----+        +-----+----+      |
   |IPv6 Host |          | Router C |        | Router D |      |
   |    #1    |          |          |---+----|          |     /
   +----------+          +----------+   |    +----------+    /
                                        |
                                        |
                                  +-----+----+    
                                  | IPv6 Host|    
                                  |   #2     |    
                                  +-----+----+      

Suppose ISP A and ISP B both provide a default route via Router Advertisements. Further suppose that ISP A delegates (via DHCPv6) the prefix 2001:db8:000a::/48, and ISP B delegates the prefix 2001:db8:0000:00b0::/56.

Router A sends 0::/0 with UP bit and Distance=1, and sends 2001:db8:a::/48 with UP bit and Distance=0.

• Router B receives the RA. It prefers the default route from ISP B, because its Distance=0. It learns prefix 2001:db8:a::/48 and adds it to its routing table.
• Router C and Router D receive the RA. They each install the default route and the /48 prefix in their routing tables.
• Host #1 might configure an address from the prefix via DHCP or SLAAC.

Router B sends 0::/0 with UP bit and Distance=1, and sends 2001:db8:0:b0::/56 with UP bit and Distance=0.

• Router A receives the RA. It prefers the default route from ISP A, because its Distance=0. It learns prefix 2001:db8:b0::/56 and adds it to its routing table.
• Router C and Router D receive the RA. They compare the default route to the existing default route. Each applies its tie-breaking rule, and installs the winning route. Suppose they have different methods, and Router C uses the default to Router A, and Router D uses the default to Router B. They each add the /56 prefix to their routing tables.
• Host #1 might configure an additional address from the prefix via DHCP or SLAAC. Whether it does is beyond the scope of this document.

Router C sends 0::/0 with UP bit and Distance=2, and sends 2001:db8:a::/48 with UP bit and Distance=2, and sends 2001:db8:0:b0::/56 with UP bit and Distance=2.

• Routers A and B receive the RAs, but ignore the duplicate prefixes within them because they already have those prefixes with a shorter Distance.
• Router D receives the RA for 0::/0, but already has a route with a lower Distance. Router D receives the RA for 2001:db8:a::/48, but already has a route with a lower Distance (from Router A, where Distance=0). Router D receives the RA for 2001:db8:0:b::/56, but already has a route with a lower Distance (from Router B, where Distance=0).

Router C then receives delegated prefix 2001:db8:a:c::/64. Host #2 gets an address for this prefix, either via SLAAC or DHCP. Router C sends RAs for 2001:db8:a:c::/64 with UP bit and Distance=0. The host also receives RAs for the /64 prefix.

• Router D receives the RA for 2001:db8:a:c::/64. It is a longer (more specific prefix) than its previous 2001:db8:a::/48 route, so it adds the more specific to its routing table.
• Routers A and B receive the RA for 2001:db8:a:c::/64. It is a longer (more specific prefix) than their previous 2001:db8:a::/48 route, so they add the more specific to its routing table. They will update their own RAs, but Routers C and D already have routes with lower Distance.
• If Router A or Router B sends the more-specific prefix to the ISP, the ISP MAY choose to add the route or ignore it if a route preferred by policy exists (for the delegated prefix).

6. Evaluation

Here follows an evaluation of whether this solution meets all of the Homenet routing requirements.

• Can Host #1 reach Host #2? Yes, via a path through either router.
• Is the network border clear? Yes, as Distance=0 for the shortest prefix.
• Can it handle a router being added? Yes, the new router will learn prefixes via RAs quickly.
• Can it handle a router being moved? Yes, with some delay in relearning the routes. If Host #2 were a Router E, and it was moved to the shared ABCD link without the router or interface going down long enough for RAs to be missed, it might propagate RAs learned from Routers C and D. It would have a higher Distance for the shorter prefixes (the /0, /48, /56), so neighboring routers would ignore its RAs. If it were two layers deeper in the network, such that it had a Distance=2 for a more-specific, which was better than the Distance previously seen by Routers A and B, neighbors would prefer its RAs. However, it would stop sending those RAs once it stopped receiving them. The router would continue sending RAs for its delegated prefix for as long as it had that prefix; this problem is related to addressing, not routing.
• Can it handle a router being removed? Yes. Some routers may install multiple routes; as soon as they miss seeing an RA for a prefix, they will have a back route. Other routers may have to wait until they see a new RA before having a backup path to the prefix.
• Will it work in a no-configuration environment? Yes.
• Can it support multiple upstream networks? Yes. It does not solve address configuration or source selection issues, but those are not routing problems per se.
• Does it work if prefix delegation is not hierarchical? Yes. Each prefix has its own Prefix Information Option, each with its own Distance.
• Can another path be found in case of failure? Yes, within a couple of RA intervals.
• Does it prevent loops? Yes.
• Does it allow for stable prefixes through reboots? Yes, though paths will have to be rediscovered, through the period configured for Router Advertisement transmissions.
• Is it lightweight/cheap? Yes. A simple addition to the PIO, which already exists. Some additional routing decision-tree logic is required for comparing best paths, tie-breaking among equal paths, etc.
• Can it handle multiple-dwelling units, or other potentially dense networks? Each upstream router will increment Distance, so each router should choose the shortest upstream path. However, a host with no router could end up choosing a neighbor's router instead of their ISP. The solution is no chattier than existing RAs.
• Can it stand up to wireless networks, and networks with wired and wireless segments? Yes, with consideration for multiple-dwelling units.
• Can it stand up to unintentional connections of networks? Yes. Although the Distance would seem to limit the diameter of the network to 255 segments, when each router is given a subnet prefix, it resets the Distance to 0 for its prefix. Thus, the Diameter is a wide as prefix topology allows.

7. Additional Work Required

This option essentially overloads the PIO to be a lightweight distance-vector routing protocol of sorts. As such, it needs to avoid the problems of distance-vector protocols, such as the count-to-infinity problem. Several possibilities exist to mitigate this problem:

• Use a smaller possible infinity (i.e., change the Distance field to be a 4-bit field)
• Shorten the RA transmission intervals
• Split horizon (do not advertise a prefix out the interface it was learned) with poison reverse (when a neighbor is lost, send an RA with Distance=255) could be used

8. Alternatives

An extension of rfc4191, Default Router Preferences and More-Specific Routes, with its definition of a Route Information Option, might be a closer approximation to the distance-vector protocol described here.

A link-state protocol would solve standard problems with distance-vector protocols. However, most link-state protocols are much heavier implementations.

9. Security Considerations

By using unsecured Router Advertisements, attacks that compromise RAs would have an extended effect. Use of SeND should mitigate these attacks.

10. IANA Considerations

There are no IANA considerations or implications that arise from this document.

11. References

11.1. Normative References

11.2. Informative References

Author's Address