idnits 2.17.1 draft-yang-alto-topology-06.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == The document doesn't use any RFC 2119 keywords, yet seems to have RFC 2119 boilerplate text. -- The document date (March 9, 2015) is 3329 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Unused Reference: 'I-D.amante-i2rs-topology-use-cases' is defined on line 411, but no explicit reference was found in the text == Unused Reference: 'I-D.clemm-i2rs-yang-network-topo' is defined on line 416, but no explicit reference was found in the text == Unused Reference: 'I-D.lee-alto-app-net-info-exchange' is defined on line 422, but no explicit reference was found in the text == Unused Reference: 'RFC5693' is defined on line 429, but no explicit reference was found in the text == Outdated reference: A later version (-04) exists of draft-clemm-i2rs-yang-network-topo-01 == Outdated reference: A later version (-04) exists of draft-lee-alto-app-net-info-exchange-02 Summary: 0 errors (**), 0 flaws (~~), 8 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 ALTO WG G. Bernstein 3 Internet-Draft Grotto Networking 4 Intended status: Standards Track Y. Lee 5 Expires: September 10, 2015 Huawei 6 W. Roome 7 M. Scharf 8 Alcatel-Lucent 9 Y. Yang 10 Yale University 11 March 9, 2015 13 ALTO Topology Extensions: Node-Link Graphs 14 draft-yang-alto-topology-06.txt 16 Abstract 18 The Application-Layer Traffic Optimization (ALTO) Service has defined 19 network and cost maps to provide basic network information. In this 20 document, we discuss designs to provide abstracted (node-link) graph 21 representations of network topology. 23 Requirements Language 25 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 26 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 27 document are to be interpreted as described in RFC 2119 [RFC2119]. 29 Status of This Memo 31 This Internet-Draft is submitted in full conformance with the 32 provisions of BCP 78 and BCP 79. 34 Internet-Drafts are working documents of the Internet Engineering 35 Task Force (IETF). Note that other groups may also distribute 36 working documents as Internet-Drafts. The list of current Internet- 37 Drafts is at http://datatracker.ietf.org/drafts/current/. 39 Internet-Drafts are draft documents valid for a maximum of six months 40 and may be updated, replaced, or obsoleted by other documents at any 41 time. It is inappropriate to use Internet-Drafts as reference 42 material or to cite them other than as "work in progress." 44 This Internet-Draft will expire on September 10, 2015. 46 Copyright Notice 48 Copyright (c) 2015 IETF Trust and the persons identified as the 49 document authors. All rights reserved. 51 This document is subject to BCP 78 and the IETF Trust's Legal 52 Provisions Relating to IETF Documents 53 (http://trustee.ietf.org/license-info) in effect on the date of 54 publication of this document. Please review these documents 55 carefully, as they describe your rights and restrictions with respect 56 to this document. Code Components extracted from this document must 57 include Simplified BSD License text as described in Section 4.e of 58 the Trust Legal Provisions and are provided without warranty as 59 described in the Simplified BSD License. 61 Table of Contents 63 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 64 2. Review: the Base Single-Node Representation . . . . . . . . . 3 65 3. Topology using a Graph (Node-Link) Representation . . . . . . 4 66 3.1. Use Cases . . . . . . . . . . . . . . . . . . . . . . . . 4 67 3.2. A Node-Link Schema . . . . . . . . . . . . . . . . . . . 5 68 3.3. Discussions . . . . . . . . . . . . . . . . . . . . . . . 9 69 4. Security Considerations . . . . . . . . . . . . . . . . . . . 9 70 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10 71 6. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 10 72 7. References . . . . . . . . . . . . . . . . . . . . . . . . . 10 73 7.1. Normative References . . . . . . . . . . . . . . . . . . 10 74 7.2. Informative References . . . . . . . . . . . . . . . . . 10 75 Appendix A. Graph Transformations and Operations to Build 76 Topology Representation for Applications . . . . . . 11 77 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 12 79 1. Introduction 81 Topology is a basic information component that a network can provide 82 to network management tools and applications. Example tools and 83 applications that can utilize network topology include traffic 84 engineering, network services (e.g., VPN) provisioning, PCE, 85 application overlays, among others [RFC5693,I-D.amante-i2rs-topology- 86 use-cases, I-D.lee-alto-app-net-info-exchange]. 88 A basic challenge in exposing network topology is that there can be 89 multiple representations of the topology of the same network 90 infrastructure, and each representation may be better suited for its 91 own set of deployment scenarios. For example, the current ALTO base 92 protocol [RFC7285] is designed for a setting of exposing network 93 topology using the extreme "my-Internet-view" representation, which 94 abstracts a whole network as a single node that has a set of access 95 ports, with each port connects to a set of endhosts called endpoints. 96 The base protocol refers to each access port as a PID. This "single- 97 node" abstraction achieves simplicity and provides flexibility. A 98 problem of this abstraction, however, is that the base protocol as 99 currently defined does not provide sufficient information for use 100 cases such as the multi-flow scheduling use case (see [draft-yang- 101 alto-path-vector]). 103 An opposite of the single-node representation is the complete raw 104 topology, spanning across multiple layers, to include all details of 105 network states such as endhosts attachment, physical links, physical 106 switch equipment, and logical structures (e.g., LSPs) already built 107 on top of the physical infrastructural devices. A problem of the raw 108 topology representation, however, is that its exposure may violate 109 privacy constraints. Also, a large raw topology may be overwhelming 110 and unnecessary for specific applications. Since the target of ALTO 111 is general applications which do not want or need to understand 112 detailed routing protocols or raw topology collected in routing 113 information bases (RIB), raw topology does not appear to be a good 114 fit for ALTO. 116 A main objective of this document is to specify a new type of ALTO 117 Information Resources, which provide abstracted graph (node-link) 118 representations of a network to provide only enough information for 119 applications. We call such Information Resources ALTO topology maps, 120 or topology maps for short. Different from the base single-node 121 abstraction, a topology map includes multiple network nodes. 122 Different from the raw topology representation that uses real network 123 nodes, a topology map may use abstract nodes, although they will be 124 constructed from the real, raw topology, in order to provide grounded 125 information. The design of this document is based on the ALTO WG 126 discussions at IETF 89, with summary slides at 127 http://tools.ietf.org/agenda/89/slides/slides-89-alto-2.pdf. 129 The organization of this document is organized as follows. We first 130 review the ALTO base protocol in Section 2. In Section 3, we give a 131 node-link representation. 133 2. Review: the Base Single-Node Representation 135 We distinguish between endhosts and the network infrastructure of a 136 network. Endhosts are sources and destinations of data that the 137 network infrastructure carries. The network itself is neither the 138 source nor the destination of data. 140 For a given network, it provides "access ports" (interfaces, or 141 access points) where data signal from endhosts enter and leave the 142 network infrastructure. One should understand "access ports" in a 143 generic sense. For example, an access port can be a physical 144 Ethernet port connecting to a specific endhost, or it can be a port 145 connecting to a CE which connects to a large number of endhosts. Let 146 AP be the set of access ports (AP) that the network provides. 148 A high-level abstraction of a network topology is only the set AP, 149 and one can visualize, as Figure 1, the network as a single, abstract 150 node with the set AP of access ports attached. At each ap in AP, a 151 set of endhosts are attached to send or receive information from the 152 network. Let attach(ap) denote the set of endhosts attached to ap. 154 +----------------------+ 155 ap_1 | | 156 +------+ +------+ 157 | | 158 | | 159 +------+ +------+ 160 | | 162 | | 163 +------+ +------+ 164 | | 165 | | 166 +------+ +------+ 167 | | ap_n 168 +----------------------+ 170 Figure 1: Base Single-Node Topology Abstraction. 172 There can be multiple ways to partition the set AP. Each partition 173 is called a network map. Given a complete partition of AP, the ALTO 174 base protocol introduces PID to represent each partition subset. The 175 ALTO base protocol then conveys the pair-wise connection properties 176 between one PID and another PID through the "single-node". This is 177 the cost map. 179 3. Topology using a Graph (Node-Link) Representation 181 3.1. Use Cases 183 [draft-yang-alto-path-vector] proposes path vectors to extend the 184 preceding topology to expose network elements. A potential problem 185 of the path vector representation, however, is its lacking of 186 compactness. For example, suppose a network has N PIDs, then it will 187 need to represent N * (N-1) paths, if each source-destination pair 188 has one path computed using a shortest-path algorithm. On the other 189 hand, the underlying graph may have only O(F * N) elements, where F 190 is the average degree of the topology, and hence can be a much 191 smaller value than N. For such settings, in particular, when privacy 192 protection is not an issue (e.g., in the same-trust domain setting), 193 a node-link representation can be more compact. 195 Another setting where a node-link graph approach is beneficial is 196 application guided path selection. With a topology graph, an 197 application can compute maximum flows to discover the desired paths 198 and signal (out the scope of this document) to the network to set up 199 the paths. The computation can be done by the application itself, or 200 through a third entity such as a PCE server. The recent development 201 of SDN makes this use case more possible. A requirement of realizing 202 this use case is that the path computed by the application is 203 realizable, in particular, when the topology is an abstract topology. 204 By realizable, we mean that a path computed on the abstract topology 205 can be converted to configurations on network devices to achieve the 206 properties in the abstract topology. 208 3.2. A Node-Link Schema 210 A schema for the graph (node-link) representation, based on the types 211 already defined in the base ALTO protocol, is the following: 213 object { 214 TopologyMapData topology-map; 215 } InfoResourceTopologyMap : ResponseEntityBase; 217 object { 218 NodeMapData nodes; 219 LinkMapData links; 220 } TopologyMapData; 222 object-map { 223 JSONString -> NodeProperties; // node name to properties 224 } NodeMapData; 226 object { 227 JSONString type; 228 ... 229 } NodeProperties; 231 object-map { 232 JSONString -> LinkProperties; // link name to properties 233 } LinkMapData; 235 object { 236 JSONString src; 237 JSONString dst; 238 JSONString type; 239 CostValue costs<0,*>; 240 } LinkProperties; 242 object { 243 CostMetric metric; 244 JSONValue value; // value type depends on metric type 245 } CostValue; 247 In particular, the schema distinguishes two types of links: edge- 248 attach, and core, where the former is for a link between a network 249 element and a group of endhosts (PID), and the later is between two 250 network elements. 252 An example using the schema is: 254 GET /topologymap HTTP/1.1 255 Host: alto.example.com 256 Accept: application/alto-topologymap+json,application/alto-error+json 258 HTTP/1.1 200 OK 259 Content-Length: TBD 260 Content-Type: application/alto-topologymap+json 262 { 263 "meta" : { 264 "dependent-vtags" : [ 265 { "resource-id": "my-default-network-map", 266 "tag": "3ee2cb7e8d63d9fab71b9b34cbf764436315542e" 267 } 268 ], 269 "vtag": { 270 "resource-id": "my-topology-map", 271 "tag": "da65eca2eb7a10ce8b059740b0b2e3f8eb1d4785" 272 } 273 }, 274 "topology-map" : { 275 "nodes" : { 276 "sw1" : {"type" : "switch"}, 277 "sw2" : {"type" : "switch"}, 278 "sw3" : {"type" : "switch"}, 279 "sw4" : {"type" : "switch"}, 280 "sw5" : {"type" : "switch"}, 281 "sw6" : {"type" : "switch"}, 282 "sw7" : {"type" : "switch"} 283 }, 284 "links" : { 285 "e1" : {"src" : "PID1", 286 "dst" : "sw1", 287 "type": "edge-attach", 288 "costs" : [ 289 {"cost-metric" : "availbw", "value" : 100 290 }, 291 {"cost-metric" : "srlg", value : [1, 3]} 293 ] 294 }, 295 "e2" : {"src" : "PID2", 296 "dst" : "sw2", 297 "type": "edge-attach", 298 ... 299 }, 300 "e3" : {"src" : "PID3", 301 "dst" : "sw3", 302 ... 303 }, 304 "e4" : {"src" : "PID4", 305 "dst" : "sw4", 306 "type": "edge-attach", 307 ... 308 }, 309 "e15" : {"src" : "sw1", 310 "dst" : "sw5", 311 "type": "core", 312 ... 313 }, 314 "e35" : {"src" : "sw3", 315 "dst" : "sw5", 316 "type": "core", 317 ... 318 }, 319 "e27" : {"src" : "sw2", 320 "dst" : "sw7", 321 "type": "core", 322 ... 323 }, 324 "e47" : {"src" : "sw4", 325 "dst" : "sw7", 326 "type": "core", 327 ... 328 }, 329 "e57" : {"src" : "sw5", 330 "dst" : "sw7", 331 "type": "core", 332 ... 333 }, 334 "e56" : {"src" : "sw5", 335 "dst" : "sw6", 336 "type": "core", 337 ... 338 }, 339 "e67" : {"src" : "sw6", 340 "dst" : "sw7", 341 "type": "core", 342 ... 343 } 344 } 345 } 347 } 349 3.3. Discussions 351 The node-link schema specified in the preceding section is still a 352 standard graph representation of a network (graph). An alternative 353 design, which may provide substantial benefit, is using a property 354 graph design. In particular, in a property graph based design, it is 355 unnecessary that a node in the property graph represents a network 356 node, a link in the property graph represents a network link. 357 Instead, network nodes, network links and network paths can all be 358 represented as nodes in a property graph, and links represent their 359 relationship. This design can be flexible in modeling settings such 360 as topology abstraction (e.g., to denote, in the same graph, that a 361 network link is composed of a path, through a aggregation label). 362 Property-graph frameworks such as Gremlin can provide powerful and 363 compact querying languages for application's usage. 365 Using either the standard node-link graph in the preceding section or 366 the property graph abstraction, one may not use a rigid hierarchical 367 design. Consider a model that uses a strict hierarchy, and a higher 368 layer node can specify a set of nodes in the lower layer as 369 supporting nodes; a higher layer link can specify a set of links in 370 the lower layer as supporting links [draft-clemm-i2rs-yang-network- 371 topo-01]. To test the problem of that model, consider a simple 372 topology. Assume that the network consists of 3 data centers (dc1, 373 dc2, and dc3). dc1 has two routers dc11 and dc12; dc2 has dc21 and 374 dc22; and dc3 has dc31 and dc32. The connections are that (1) two 375 routers in the same data center are connected; (2) dc11, dc21 and 376 dc31 are mutually connected; same for dc12, dc22, and dc32. 378 The network can provide different abstract topologies: for tenants in 379 dc1, they see dc11, dc12, and dc2, dc3; same for tenants in dc2, and 380 dc3. In other words, each tenant in a DC sees the detailed topology 381 of its DC and the other data centers are abstracted to be single 382 nodes. 384 This case turns out to be not doable for their pure hierarchical 385 layer approach, where a top layer node/link has supporting nodes/ 386 links. Specifically, thee model cannot have cross-layer links such 387 as dc11 -> dc2. 389 4. Security Considerations 391 This document has not conducted its security analysis. 393 5. IANA Considerations 395 This document does not specified its IANA considerations, yet. 397 6. Acknowledgments 399 The author thanks discussions with Xiao Shi, Xin Wang, Erran Li, 400 Tianyuan Liu, Andreas Voellmy, Haibin Song, and Yan Luo. 402 7. References 404 7.1. Normative References 406 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 407 Requirement Levels", BCP 14, RFC 2119, March 1997. 409 7.2. Informative References 411 [I-D.amante-i2rs-topology-use-cases] 412 Medved, J., Previdi, S., Lopez, V., and S. Amante, 413 "Topology API Use Cases", draft-amante-i2rs-topology-use- 414 cases-01 (work in progress), October 2013. 416 [I-D.clemm-i2rs-yang-network-topo] 417 Clemm, A., Medved, J., Tkacik, T., Varga, R., Bahadur, N., 418 and H. Ananthakrishnan, "A YANG Data Model for Network 419 Topologies", draft-clemm-i2rs-yang-network-topo-01 (work 420 in progress), October 2014. 422 [I-D.lee-alto-app-net-info-exchange] 423 Lee, Y., Bernstein, G., Choi, T., and D. Dhody, "ALTO 424 Extensions to Support Application and Network Resource 425 Information Exchange for High Bandwidth Applications", 426 draft-lee-alto-app-net-info-exchange-02 (work in 427 progress), July 2013. 429 [RFC5693] Seedorf, J. and E. Burger, "Application-Layer Traffic 430 Optimization (ALTO) Problem Statement", RFC 5693, October 431 2009. 433 [RFC7285] Alimi, R., Penno, R., Yang, Y., Kiesel, S., Previdi, S., 434 Roome, W., Shalunov, S., and R. Woundy, "Application-Layer 435 Traffic Optimization (ALTO) Protocol", RFC 7285, September 436 2014. 438 Appendix A. Graph Transformations and Operations to Build Topology 439 Representation for Applications 441 In this appendix, we give a graph transformation framework to build 442 the schema from a raw topology G(0). The network conducts 443 transformations on G(0) to obtain other topologies, with the 444 following objectives: 446 1. Simplification: G(0) may have too many details that are 447 unnecessary for the receiving app (assume intradomain); and 449 2. Preservation of privacy: there are details that the receiving app 450 should not be allowed to see; and 452 3. Conveying of logical structure (e.g., MPLS paths already 453 computed); and 455 4. Conveying of capability constraints (the network can have 456 limitations, e.g., it uses only shortest path routing); and 458 5. Allow modular composition: path from one point to another point 459 is delegated to another app. 461 The transformation of G(0) is to achieve/encode the preceding. For 462 conceptual clarity, we assume that the network uses a given set of 463 operators. Hence, given a sequence of operations and starting from 464 G(0), the network builds G(1), to G(2), ... 466 Below is a list of basic operators that the network may use to 467 transform from G(n-1) to G(n): 469 o O1: Deletion of a switch/port/link from G(n-1); 471 o O2: Switch aggregation: a set Vs of switches are merged as one new 472 (logical) switch, links/ports connected to switches in Vs are now 473 connected to the new logical switch, and then all switches in Vs 474 are deleted; 476 o O3: Path representation: For a given extra path from A to R1 to R2 477 ... to B in G(n-1), a new (logical) link A -> B is added; if the 478 constraint is that A -> must use the path, it will be put into the 479 Overlay; 481 o O4: Switch split: A switch s in G(n-1) becomes two (logical) 482 switches s1 and s2. The links connected to s1 is a subset of the 483 original links connected to s; so is s2. 485 Authors' Addresses 487 Greg Bernstein 488 Grotto Networking 489 Fremont, CA 490 USA 492 Email: gregb@grotto-networking.com 494 Young Lee 495 Huawei 496 TX 497 USA 499 Email: leeyoung@huawei.com 501 Wendy Roome 502 Alcatel-Lucent Technologies/Bell Labs 503 600 Mountain Ave, Rm 3B-324 504 Murray Hill, NJ 07974 505 USA 507 Phone: +1-908-582-7974 508 Email: w.roome@alcatel-lucent.com 510 Michael Scharf 511 Alcatel-Lucent Technologies 512 Germany 514 Email: michael.scharf@alcatel-lucent.com 516 Y. Richard Yang 517 Yale University 518 51 Prospect St 519 New Haven CT 520 USA 522 Email: yry@cs.yale.edu