Path-Vector and Node-Edge Topology Maps in ALTO
draft-scharf-alto-topology-00

Abstract

The Application-Layer Traffic Optimization (ALTO) service defines network and cost maps to provide basic network information. This document motivates an optional extension of ALTO for the definition of additional topology properties. The ALTO extension supports both path-vector and node-edge topology maps.

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 January 3, 2015.

Copyright Notice

Copyright (c) 2014 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.

Table of Contents

• 1. Introduction
• 2. Terminology
• 3. Endpoint-Centric Network Topology Models
• 3.1. Use Cases
• 3.2. Topology Models
• 4. Topology Encoding Formats for ALTO
• 4.1. Map Service Extension
• 4.2. Path-Vector Format
• 4.3. Node-Edge Format
• 5. IANA Considerations
• 6. Security Considerations
• 7. Conclusion
• 8. References
• 8.1. Normative References
• 8.2. Informative References
• Appendix A. Contributors
• Author's Address

1. Introduction

The Application-Layer Traffic Optimization (ALTO) service [I-D.ietf-alto-protocol] provides network information (e.g., basic network location structure and preferences of network paths) with the goal of modifying network resource consumption patterns while maintaining or improving application performance. The basic information of ALTO is based on abstract maps of a network. These maps provide a simplified view, yet enough information about a network for applications to effectively utilize them.

Applications using an ALTO service typically consist of instances running at endpoints. This is why ALTO maps provide abstract cost and/or ranking information between network endpoints. Yet, for selected use cases of ALTO, it is desirable to have a more detailed representation of the network. For instance, in settings with multiple application source-destination pairs with multiple links, such a representation could help avoid bottleneck or failed links.

Topology models for ALTO are also discussed in other related documents. A full solution to extend ALTO is defined in [I-D.yang-alto-topology]. An earlier survey of use-cases for extended network topology information can also be found in [I-D.bernstein-alto-topo]. Further related work has been published in [I-D.lee-alto-app-net-info-exchange] and [I-D.bernstein-alto-large-bandwidth-cases].

This document specifies two graph representation formats that can be used in ALTO. Both formats are optional, and it is up to the operator of an ALTO service to decide whether to offer this data in addition to the standard network and cost maps of an ALTO service. The graph representation defined in this document is based on existing ALTO abstraction (e.g., PIDs) and complements the existing path-based ALTO cost map representation. Together, they provide a more complete but still abstract representation of networks for informed traffic optimization among endpoints.

This document does not intend to model topology internals not affecting endpoints, such as routing protocol internals. A data model for network topologies with routing protocol externals can for instance be found in [I-D.clemm-i2rs-yang-network-topo].

2. Terminology

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 [RFC2119].

3. Endpoint-Centric Network Topology Models

3.1. Use Cases

This document focuses on exposure of network topology properties that matter to endpoints. Usually, applications instances at network endpoints (hosts) only have to care about end-to-end network properties of the paths between those endpoints. The basic ALTO services, i.e., either the Network and Cost Map service or the Endpoint Cost service, can be used to express end-to-end characteristics of paths between endpoints, as explained e.g. in [I-D.ietf-alto-deployments] and [I-D.wu-alto-te-metrics].

However, there are a number of use cases in which it is difficult to expose topological properties to applications using only the mechanisms in the base ALTO protocol [I-D.ietf-alto-protocol]. These uses cases are typically characterized by multiple application source-destination pairs:

• Shared bottleneck detection: As explained for instance in [I-D.ietf-alto-deployments], ALTO can be used to avoid excessive use of bottleneck links by recommending communication with endpoints not using that bottleneck. However, if multiple application transfers shall be scheduled, e.g., by a bandwidth calendaring application, it can be difficult to determine whether the resulting communication would hit a common bottleneck unless the applications are aware of links that would be used by multiple transfers. This would benefit from an ALTO extension that can return shared parts of paths used by transfers between different endpoints (e.g., given by IP addresses).
• Resilience improvement: Applications requiring high reliability can be interested in understanding if there is a risk of simultaneous failures on multiple path between application instances. For instance, transport networks can provide certain shared risk link group (SRLG) information that provides insight which links are at risk of simultaneous failures due to fate sharing. Applications requiring high reliability may then prefer the use of endpoints with disjoint paths.
• Multi-homing and multi-pathing: If endpoints are multi-homed, i.e., if hosts have more than one IP address, it can be useful to know if there are multiple paths between these endpoints. For instance, applications could leverage such information to decide whether to explictly enable Multipath TCP [RFC6824].

None of these use cases requires an application to understand routing protocol internals, such as the entries in Routing Information Base (RIB) of routers in the network. While it may be possible to derive such information from corresponding models, such as [I-D.clemm-i2rs-yang-network-topo], ALTO targets general-purpose applications that typically have no understanding of RIB data, different routing protocols, etc. Therefore, ALTO requires a more abstract solution to express topology details. An optional ALTO graph representation solution allows disclosure of such information to ALTO clients.

3.2. Topology Models

This document specifies two optional, abstract graph representation format for ALTO, which can reveal for instance coupling of links on a path. This section introduces the topology model. The formal specification follows in the next section.

There are two different graph representation formats that could be used to generalize the existing ALTO network and cost maps and reveal path coupling:

• Path-vector format: This format describes the topology between given endpoints by an enumeration of the path traversed between the source and destination. The advantage of this format is that it can consider the outcome of network-internal routing policies (e.g., preferring paths other than the shortest path given by routing metrics). However, for a large network with many paths there is a large representation overhead.
• Node-edge format: A graph encoding with nodes and edges can be very compact, depending on the average node degree, and it can also be much smaller than the full mesh of costs between endpoints that is used by ALTO cost maps. Yet, a downside is that a single graph may not convey network routing policies.

Since both formats have advantages and drawbacks, this document allows the use of both formats, and it is up to the ALTO service to decide whether to support it.

Both formats can reuse the PID concept that is used in ALTO to abstract topology details, as explained in [I-D.ietf-alto-protocol] and [I-D.ietf-alto-deployments].

4. Topology Encoding Formats for ALTO

This section defines an OPTIONAL extension of ALTO for topology encoding in JSON format [RFC4627]. An ALTO service announces the support of these formats in the Information Resource Directory (IRD) [I-D.ietf-alto-protocol].

TODO: Currently, the formats are illustrated by examples only. The full formal specification is TBD.

4.1. Map Service Extension

The graph encoding uses the existing PID concept and ALTO map service [I-D.ietf-alto-protocol]. Basically, both in the path-vector and in the node-edge encoding, a PID is generalized as a node in the topology. If an ALTO server server uses either format, it MAY return PIDs without an IPv4 or IPv6 address mapping.

For instance, consider the following network topology. For the sake of simplicity, "H1", "H2", ... as well as "R1", "R2", ... are also used as PID names in the following examples.

10.0.1.1/24                                    10.0.3.1/24
  +----+                              +----+      +----+
  | H1 |----.                    .----| R3 |------| H3 |
  +----+     \+----+      +----+/     +----+      +----+
              | R1 |======| R2 |
  +----+     /+----+      +----+\     +----+      +----+
  | H2 |----'                    '----| R4 |------| H4 |
  +----+                              +----+      +----+
10.0.2.1/24                                    10.0.4.1/24

R1, R2, ... are transit nodes in the topology. The objective of topology encoding formats is to represent their relations. Yet, the addresses of those routers (e.g., interface or system IP addresses) may not matter to applications. Therefore, PIDs representing those nodes may not have a valid IP address mapping. In ALTO, it is up to an ALTO server to define what a PID represents. A PID can both refer to a single node (such as a router), a subnet, a whole network, etc.

A corresponding ALTO network map query according to [I-D.ietf-alto-protocol] would be:

GET /networkmap HTTP/1.1
Host: alto.example.com
Accept: application/alto-networkmap+json,
        application/alto-error+json

For the given example, this would return:

HTTP/1.1 200 OK
Content-Length: TBD
Content-Type: application/alto-networkmap+json

{
  "meta": {
    ...
  },
  "network-map": {
    "H1": { "ipv4": [ "10.0.1.0/24" ] },
    "H2": { "ipv4": [ "10.0.2.0/24" ] },
    "H3": { "ipv4": [ "10.0.3.0/24" ] },
    "H4": { "ipv4": [ "10.0.4.0/24" ] },
    "R1": { }, "R2": { }, "R3": { }, "R4": { },
    "Default": {
      "ipv4": [ "0.0.0.0/0" ], "ipv6": [ "::/0" ]
    }
  }
}

R1, R2, R3, and R4 are transient PIDs on the path between endsystems. If their IP addresses do not matter, they can be omitted. If an identification of such nodes was required, one could introduce other identifiers. This is left for further study.

4.2. Path-Vector Format

This extension uses a new media type "application/alto-pathvector+json". An ALTO service MAY use the path-vector format as optional extension. In the path-vector format, an ALTO cost map consists of an ordered sequence of PIDs. Using the same query mechanisms like the base ALTO protocol [I-D.ietf-alto-protocol], an ALTO query for path-vector information would be:

GET /costmap/pathvector HTTP/1.1
Host: alto.example.com
Accept: application/alto-pathvector+json,
        application/alto-error+json

The corresponding response of an ALTO server would be:

HTTP/1.1 200 OK
Content-Length: TBA
Content-Type: application/alto-pathvector+json

{
  "meta": {
    ...
    "cost-type": {"cost-mode": "pathvector"}
  },
  "cost-map" : {
    "H1": {
      "H2": [ "R1" ],
      "H3": [ "R1", "R2", "R3" ]
      "H4": [ "R1", "R2", "R4" ]
     },
    "H2": { ... },
    "H3": { ... },
    "H4": { ... },
    "Default": { ... }
  }
}

In the most simple form, a path vector consists of an ordered sequence of PIDs from a source to a destination. It is also possible to extend the path vector format by integrating cost metrics in the vector. A corresponding format is left for further study in this document.

In general, the cost values between any PIDs can always be determined using the standard cost map of ALTO [I-D.ietf-alto-protocol]. As an example, the following query is also possible for the path-vector cost mode:

GET /costmap/num/routingcost HTTP/1.1
Host: alto.example.com
Accept: application/alto-costmap+json,
        application/alto-error+json

A corresponding response of an ALTO server could be, fully using the syntax and semantics of [I-D.ietf-alto-protocol]:

HTTP/1.1 200 OK
Content-Length: TBD
Content-Type: application/alto-costmap+json

{
  "meta" : {
    ...
    "cost-type": {"cost-mode": "numerical",
                  "cost-metric": "routingcost"
    }
  },
  "cost-map": {
    "H1": { "R1": 1 },
    "H2": { "R1": 5 },
    "R1": { "H1": 1, "H2": 5, "R2": 9 },
    "R2": { "R1": 9, "R3": 4, "R4": 7 },
    ...
  }
}

In addition to the standard metric "routing cost", also other metrics for ALTO cost maps could be used, such as the ones described in [I-D.wu-alto-te-metrics].

4.3. Node-Edge Format

As an alternative representation, an ALTO service MAY also expose map data in a node-edge format. The node-edge format basically returns a list of edges between the PIDs given by the network map. The response SHOULD also include a list of the nodes, which is identical to the ALTO network map. Adding the list of nodes enables a client to process the full graph with a single query. This extension uses the new media type "application/alto-nodeedge+json". In the following a query for a node-edge map is shown:

GET /costmap/nodeedge HTTP/1.1
Host: alto.example.com
Accept: application/alto-nodeedge+json,
        application/alto-error+json

In the given example, the response in node-edge format would be as follows:

HTTP/1.1 200 OK
Content-Length: TBA
Content-Type: application/alto-nodeedge+json

{
  "meta": {
    ...
    "cost-type": {"cost-mode": "nodeedge"}
  },
  "nodes": {
    "H1": { "ipv4": [ "10.0.1.0/24" ] },
    "H2": { "ipv4": [ "10.0.2.0/24" ] },
    "H3": { "ipv4": [ "10.0.3.0/24" ] },
    "H4": { "ipv4": [ "10.0.4.0/24" ] },
    "R1": { }, "R2": { }, "R3": { }, "R4": { },
    "Default": {
      "ipv4": [ "0.0.0.0/0" ], "ipv6": [ "::/0" ]
    }
  }
  "edges": [
    "E1": { "src": "H1", "dst": "R1",
            "type": "directed",
            "cost": [ { "cost-metric": "delay",
                        "value": "3"
                      }, {
                        "cost-metric": "availbw",
                        "value": "50"
                      }, {
                        "cost-metric" : "risk-group",
                        "value" : ["SLRG3"]
                      } ]
          },
    "E2": { "src": "R1", "dst": "R2",
            "type": "directed",
            "cost": [ { "cost-metric": "delay",
                        "value": "3"
                      }, {
                        "cost-metric": "availbw",
                        "value": "50"
                      } ]
        },
    ...
  }
}

The node-edge format re-uses the PID as identifiers for nodes. It requires a new set of identifiers for the edges. For those identifies, the same syntax constraints like for PIDs are used. Within one response, each edge must be uniquely identified by an edge identifier.

Edges can be characterized by the same attributes like ALTO cost maps, including one or more cost metrics. For instance, the cost metrics defined in [I-D.wu-alto-te-metrics] can be used for edges. The specification of further edge properties is for further study.

5. IANA Considerations

TBD

6. Security Considerations

TBD

7. Conclusion

TBD

8. References

8.1. Normative References

8.2. Informative References

Appendix A. Contributors

This document is an outcome of very valuable discussions with Y. Richard Yang, Young Lee, and Greg M. Bernstein during IETF 89.

Author's Address