idnits 2.17.1 draft-chiappa-routing-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Cannot find the required boilerplate sections (Copyright, IPR, etc.) in this document. Expected boilerplate is as follows today (2024-04-26) according to https://trustee.ietf.org/license-info : IETF Trust Legal Provisions of 28-dec-2009, Section 6.a: This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 2: Copyright (c) 2024 IETF Trust and the persons identified as the document authors. All rights reserved. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 3: This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://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. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing document type: Expected "INTERNET-DRAFT" in the upper left hand corner of the first page ** Missing expiration date. The document expiration date should appear on the first and last page. ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity. ** The document seems to lack a 1id_guidelines paragraph about the list of current Internet-Drafts. ** The document seems to lack a 1id_guidelines paragraph about the list of Shadow Directories. ** Expected the document's filename to be given on the first page, but didn't find any ** The document is more than 15 pages and seems to lack a Table of Contents. == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 1 longer page, the longest (page 1) being 1477 lines Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an Abstract section. ** The document seems to lack a Security Considerations section. ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack an Authors' Addresses Section. ** There are 649 instances of too long lines in the document, the longest one being 6 characters in excess of 72. ** There are 202 instances of lines with control characters in the document. Miscellaneous warnings: ---------------------------------------------------------------------------- == Couldn't figure out when the document was first submitted -- there may comments or warnings related to the use of a disclaimer for pre-RFC5378 work that could not be issued because of this. Please check the Legal Provisions document at https://trustee.ietf.org/license-info to determine if you need the pre-RFC5378 disclaimer. -- Couldn't find a document date in the document -- date freshness check skipped. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Missing reference section? 'Little' on line 1426 looks like a reference -- Missing reference section? 'Chiappa91' on line 1405 looks like a reference -- Missing reference section? 'Dijkstra' on line 1416 looks like a reference -- Missing reference section? 'McQuillan' on line 1422 looks like a reference -- Missing reference section? 'Chiappa84' on line 1403 looks like a reference -- Missing reference section? 'Shoch' on line 1438 looks like a reference -- Missing reference section? 'Saltzer82' on line 1435 looks like a reference -- Missing reference section? 'Corbato' on line 1413 looks like a reference -- Missing reference section? 'SalzterSR' on line 798 looks like a reference -- Missing reference section? 'Moy' on line 1429 looks like a reference -- Missing reference section? 'BBN' on line 1400 looks like a reference -- Missing reference section? 'Reed' on line 1431 looks like a reference -- Missing reference section? 'Estrin' on line 1419 looks like a reference -- Missing reference section? 'Clark' on line 1408 looks like a reference -- Missing reference section? 'Thompson' on line 1441 looks like a reference -- Missing reference section? 'Cohen' on line 1410 looks like a reference -- Missing reference section? 'SaltzerSR' on line 1433 looks like a reference Summary: 15 errors (**), 0 flaws (~~), 3 warnings (==), 18 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 A New IP Routing and Addressing Architecture 3 J. Noel Chiappa 5 [ Author's note: This document is not yet fully complete, but it is being 6 distributed in this rough form since there appears to be a considerable 7 appetite in the network community for discussion on this topic. It is hoped 8 that this note, even in its present form, will facilitate useful debate about 9 the issue. ] 11 Status of the Memo 13 This document is an Internet Draft. Internet Drafts are working 14 documents of the Internet Engineering Task Force (IETF), its Areas, 15 and its Working Groups. Note that other groups may also distribute 16 working documents as Internet Drafts. 18 Internet Drafts are draft documents valid for a maximum of six 19 months. Internet Drafts may be updated, replaced, or obsoleted 20 by other documents at any time. It is not appropriate to use 21 Internet Drafts as reference material or to cite them other than 22 as a "working draft" or "work in progress." 24 Please check the I-D abstract listing contained in each Internet 25 Draft directory to learn the current status of this or any 26 other Internet Draft. 28 1 Introduction 30 This document presents one possible new IP routing and adressing 31 architecture. By routing and addressing it is meant that part of the overall 32 IP architecture which is responsible for identifying computing nodes, 33 where they are in the Internet, and how to get traffic from one to another. It 34 represents one person's view of a good overall system answer to this question, 35 and is not to be taken as anything more than that. 36 While this document will be of most interest to those with some degree 37 of familiarity with routing concepts, it is aimed at the general network 38 community, which will have to agree with the general direction taken in 39 evolving this aspect of the IP architecture. While the subject is a complex 40 one, the document has been written to be accessible to a general audience. As 41 such, it contains much material which will be familiar to those who are versed 42 in routing work, which has unavoidably lengthened the document. 44 The goals of the new architecture are more or less those outlined in 45 RFC1126 [Little], particularly Appendix A, but modified somewhat to include 46 what I feel are real constraints, such as more complex external policy 47 concerns. To review them briefly, they are to allow a system substantially 48 larger than the current one (if possible of essentially unlimited size), to 49 address the policy concerns which are of increasing importance, to allow 50 topologies of a much more complex nature, and to retain the flexibility of the 51 current system. A concise outline of the goals believed necessary are given in 52 the section below. 53 These design goals are a very agressive set of requirements. They 54 exceed considerably the existing capabilities of other large communication 55 systems, such as the telephone system. Two aspects in particular represent a 56 major leap. The first such aspect is the attempt to create a ubiquitous 57 communication system (and route traffic through it) out of a very large number 58 of cooperating autonomous units (although in some senses the road network does 59 currently accomplish this goal). The second is the assumption that the system 60 will be extremely dynamic; i.e. respond in real time, without human 61 intervention, to changes in the topology and other configuration aspects of 62 the system. 64 To meet these goals requires a substantial modification to the basic 65 philosophy and mechanism of the existing IP packet layer architecture. Since 66 the system is now widely deployed, a change of this sort - an in-place 67 modification to a large, operating, system - presents a substantial challenge. 68 To meet it it is first necessary to solve the problem of routing, and 69 only then turn to addressing. As will be seen, routing (and especially the 70 abstraction of data which will be necessary to handle a very large system) is 71 a sufficiently difficult problem that any way of making the problem easier is 72 desperately needed. Addressing needs to be completely sublimated to the needs 73 of the routing architecture; the form of addresses should be whatever is most 74 useful to the routing. Dividing the address up in such a way as to ease 75 administrative tasks is not correct, although a separate mechanism to handle 76 such administrative concerns is possible. 78 It should be noted that this document is not an engineering design 79 document. No detailed mechanisms have been laid out, and undoubtly many 80 pitfalls remain along the path to a complete system. Little attempt has been 81 made to consider optimizations for common cases and other engineering 82 practises; no study has been made of traffic patterns, and of course the cost 83 of the actual mechanisms is unknown since the design has not been done; both 84 are necessary to guide the cost/benefit choices inherent in good engineering. 85 Rather, this document contains a study which attempts to clarify what are 86 the fundamentals of the problem, and then identifies what seems to be the 87 best path available to solve that problem. 88 Also, it was felt that rather than proceed forward along a visible 89 path from where we are now, the best method (when considering the long term 90 health of the the network) was to act as if a blank piece of paper were 91 available. When the best possible design was created, it would at that point 92 be appropriate to see whether it was feasible to reach that design from the 93 current system. Proceeding from the optimal end point backward seems more 94 likely to result in the best long term results than proceeding forward from 95 the current state of affairs in an incremental fashion. 96 Thus, what this document is an attempt to decide on a general plan of 97 attack on the problem; a broad-brush architecture based on a long study of the 98 fundamental issues and problems in routing and addressing in a very large 99 network. 101 2 Design Goals 103 The list of goals for the new architecture are of three types. The 104 first are those capabilities that the existing architecture already has, which 105 are still needed. The second are things that it cannot do, and which are 106 proving to be major hindrances in actual operation. The third are those 107 necessities which will be required in the future, and which may not be obvious 108 now. 109 There are also certain longstanding goals of the IP architecture, 110 such as the ability to support mobile hosts, which have previously been 111 difficult. It proves possible to support these in the new architecture, as 112 will be seen. 114 2.1 Current Capabilities 116 First and foremost, the new architecture must be incrementally 117 deployable with respect to the existing system. The capital investment in 118 existing software and plant, and the day-to-day operational dependence of many 119 people, is so large that to start from scratch would be phenomenally 120 expensive, and utterly impractical. If there were no way to do it without a 121 fresh start, perhaps it would be practical, but since it seems to not be 122 necessary, incremental deployabilty is a must. This does not preclude eventual 123 replacement of the existing architecture, obviously; to retain it indefinitely 124 would unduly cramp the system. 125 In specific terms, a new system should not require any changes to 126 hosts to become fully operational (although eventual changes to hosts are 127 allowable to take full power from the new scheme); too many unmodifiable 128 existing hosts exist, and support for them must be maintained for some time in 129 the architecture. 130 Second, changes to routers (which are almost certainly unavoidable if 131 anything concrete is to be attained) need to be interoperable (for a period, 132 at least) with the existing system, although it is reasonable in the case of 133 routers to insist that basically all be converted before the new architecture 134 can be fully operational. Some feel that even changing all the routers is too 135 ambitious, and unnecessary, but it appears that this goal is unneeded, and 136 conflicts with the general principle of providing the best possible system 137 for the long term. 139 Next, the current system allows minimal firewalls between AS's; errors 140 in routing data from outside the AS cannot (in a properly designed AS) 141 interfere with communication inside the AS. While the concept of an AS is 142 perhaps outdated, this property is desireable, although it needs to be 143 strengthened and made more flexible. As things stand, a single misbehaving AS 144 can cause almost limitless problems in the inter-AS routing. A systematic way 145 of minimizing such problems needs to be included. 146 Finally, it must be vendor-independant; that is, specified in enough 147 detail that an implementation by a new vendor, operating solely from the 148 specifications, will interoperate correctly with other existing 149 implementations. 151 2.2 Current Limitations 153 The things about the current system that are most limiting are the 154 limit on the total size of the system, the lack of support for policy routing, 155 and the inability to support arbitrary topologies (although this last 156 restriction is being lifted by the deployment of BGP). 158 The size restriction has two phases. First, a key existing routing 159 protocol (EGP) has a small limit on the total number of networks, but, as 160 with the problems of topology, as BGP is deployed as a replacement, this 161 limit will fade. 162 The second set (which consist of three far more fundamental problems) 163 is that the system is running out of network numbers, the ability to route 164 them, and eventually, out of address space completely. This topic is not 165 treated here in detail [Chiappa91], but briefly, the first problem involves 166 the accelerating use of the limited number of network numbers, the second 167 concerns the difficulty of routing in a flat address space which is growing 168 (very quickly, to boot), and the third recognizes the eventual limits of the 169 32 bit address. 171 Policy routing is the phrase used to describe external, administrative 172 input to the data routing process. Currently, the system provides little to no 173 support for this. The ad hoc mechanisms being used are so complex as to 174 confuse all but the most skilled, and contain substantial potential for 175 errors. The main problem is that the existing mechanisms are fairly unrelated 176 to the desired goals, and the use of these mechanisms to produce the desired 177 goals is thus complex and often impossible; they simply do not address 178 existing policy requirements. 179 Policy requirements can be divided into three areas, which can be 180 called a) 'access control', control over which external users are allowed to 181 use a given resource; b) the 'trust model', control over which external 182 resources a given user is willing to use; and c) 'information hiding', 183 control over which external users are allowed knowledge of a resource. 184 While these divisions are not necessarily the theoretical minimum, they do 185 appear to accurately follow the needs of the majority of users; providing 186 these will make configuration of the system to provide the desired policies 187 far simpler by virtue of the close match between what is desired and the tools 188 available to do it. 189 BGP will do little to radically increase capabilities in this area. 190 About the only additional capability provided by BGP will be that since 191 complete path information to the destination is available, a limited amount of 192 additional 'trust model' control will be available, as will some 'access 193 control'. However, as the actual controls are still basically those currently 194 available, the ills of the existing system remain. 195 One thing to note is that while enough policy requirements have been 196 verbalized to build a general model, no complete list of what will be required 197 is by any means possible at this point. This means that whatever policy system 198 is created will have to be able to add new policies as time goes on. 199 This latter requirement will be discussed in more detail later. Note 200 also that the second policy class (trust model) implies control by the source 201 of the route through the network. This also has substantial implications. 203 The current restriction on interconnection, which prohibits cycles, 204 is untenable on reliability grounds (since alternate paths are eliminated) as 205 well as difficult to enforce. As noted, this restriction is based on the 206 technical limitations of the EGP protocol, and as BGP is deployed as a 207 replacement, this limit will fade. 209 Finally, another problem noted with the current system is the use of 210 toll networks. This includes not only the cost of running the routing 211 protocols over such networks, but also distributing the information that 212 certain paths cost money, and allowing traffic the choice of whether or not to 213 use such networks. In some sense this latter requirement is a variant of 214 policy routing, but in another it is yet another requirement, often labelled 215 'type of service routing', by which it is meant that different types of 216 traffic needs links of different characteristics. For instance, remote login 217 traffic needs low delay links, while bulk data transfer needs high bandwidth. 218 In the cases of both type of service, and access control, it is also 219 necessary to allow for future expansion of the types of each supported, since 220 it is unlikely that the complete set can be specified at this time. 222 2.3 Future Requirements 224 In the category of requirements that are not yet restrictive, but 225 of which we are becoming aware, one very important one is to provide a 226 system that is more immune to problems, of both accidental and deliberate 227 cause. The fact that this system will connect effectively everything means 228 that great reliance will be placed on it, and equally great confusion will 229 be caused should it fail. Engineering failures need to be prevented by 230 thorough simulation as well as use of large scale testbeds. Deliberate 231 attack needs to be prevented by the inclusion of provisions for security; 232 these must provide for the use of one of a (extendable) variety of optional 233 security mechanisms, to allow the cost and level of security to be 234 optimized depending on the needs and cost of failure. 236 Another important need is to minimize the amount of configuration 237 needed, to minimize the possibility of having conflicting configuration 238 information, and to prevent such conflicting information from causing a 239 problem. The existing routing architecture suffers from being overly complex 240 to configure. While this may not be obvious to technically sophisticated 241 people with long association with the network world, many new users find the 242 existing architecture confusing and difficult to set up. While they perhaps 243 expect too much, since you cannot set up a complex system with little or no 244 study and engineering, improvements can be made. In addition, conflicting 245 configuration information currently can cause severe problems; this another 246 reason why such information needs to be minimized. Finally, the architecture 247 must be robust in response the inevitable errors in configuration. 249 3 Routing and Addressing Fundamentals 251 After some consideration of the problem, it became obvious that the 252 most difficult of the requirements is the size of the system. While some 253 approaches make light of this problem, they do so at the cost of restrictions 254 which make other stated requirements difficult to meet. The new routing 255 architecture had not only to provide capabilities unheard of in the older 256 system, but also do so in a very large system. Providing the new capabilities 257 proved to be not so difficult, but the size problem was less tractable. It is 258 not practical to always provide complete information about every detail of 259 the connectivity and routing of the entire to everyone; some way of reducing 260 the data was necessary. 261 At this stage it is useful to introduce some technical terms. 262 'Compression' is taken to mean reducing one set of routing information to 263 another which, while more compact, is effectively the same; i.e. would 264 produce the same routing decisions in all cases. 'Thinning' is taken to mean 265 discarding some of the data to reduce it to a manageable size. In this case, 266 routing decisions taken using the thinned data are possibly non-optimal, 267 since some necessary information is unavailable. 'Abstraction' is a term 268 including either of these two possible ways of reducing the volume of data. 269 'Attenuation' means that information becomes less complete the further you 270 are from the source of the information. 271 However, before we examine this part of the problem in detail, it is 272 necessary to review some fundamentals of routing and addressing. 274 3.1 Routing Algorithms 276 The family of routing algorithms with the most promise is the 277 'link-state' (LS) group. They are so named because the information that is 278 distributed among the nodes running the routing protocol is about the 279 existence and state of the connecting links in the system (i.e. a topology map 280 of the system) rather than distances to destinations, as in the 281 'distance-vector'(DV) algorithms. 283 3.1.1 Distance-Vector Algorithms 285 In a DV algorithm, each node sends to all of its neighbours a 286 complete table of its distance (measured in some agreed upon metric(s)) to 287 all the destinations in the system (hence the name). For destinations it can 288 reach directly, it advertises some low metric; for destinations it reaches 289 through some neighbour, it lists what that neighbour told it plus some 290 increment. Each recipient node then compares the advertised distance to the 291 one it currently has for that destination; if what it just heard was better, 292 it records it and routes traffic to that destination to the neighbour node 293 that sent it the update. 294 There are many variants, which have been designed to add capabilities 295 or fix problems with the algorithm, the most common of which are that DV 296 algorithms tend to form temporary routing loops when the topology changes, 297 before things stabilize, and that they are unable to detect that a destination 298 becomes unreachable until the distance to it passes some arbitrary 'infinity'. 300 3.1.2 Link-State Algorithms 302 In the simplest form, LS algorithms distribute a complete topology 303 map to each switching node in the system. This is done quite simply; each 304 node generates a message describing the state of the links attached to it, 305 and this message is then quickly flooded through all the nodes in the system 306 using a reliable flooding protocol. A toplogy map can easily be constructed 307 from the messages from all the nodes in the system. 308 These nodes may then run in parallel an algorithm which generates 309 from this topology map a routing table which can be used to forward packets 310 to various destinations. The MILNet is currently using a LS algorithm where 311 the algorithm which computes the routing table is one due to Dijksta called 312 the 'Shortest Path First'. [Dijkstra] 313 However, it should be noticed that the second step, creation of a 314 routing table from the topology map, is purely an engineering decision. It is 315 not necessary to precompute the entire routing table in an LS algorithm, 316 whereas it is in a DV algorithm, since this precomputed routing table is the 317 data that is passed on to the neighbour nodes. In an LS algorithm, it is 318 perfectly plausible to compute routes on demand, from the topology map, and 319 store them in a cache. This reduces the computational burden substantially, 320 and, as we shall see, is a key element in the solution. 321 Also, in the classic LS routing scheme, the one essential is that all 322 the nodes run the same route generating algorithm from a consistent map 323 database, otherwise it is possible to form routing loops when two nodes 324 disagree about the best 'next hop'. However, if traffic is not routed using 325 the 'hop-by-hop' method, both of these requirements can be relaxed; this is 326 critical, as will be seen. 328 3.2 Routing Algorithm Choice 330 Several advantages were noted about the LS class of algorithm that 331 recommended it to the ARPANet implementors [McQuillan]. Most of these are 332 traceable to the fact that since the baseic DV algorithm is a distributed 333 algorithm for calculating routes, it is in many senses less robust and 334 characterizable (in a response time sense, not an ultimate stability after a 335 single change) than the LS algorithm, which runs in parallel locally on all 336 machines. 337 First, it stabilized quicker after a topology change. This was 338 important; since the ARPANet used load-based routing, the metrics on links 339 changed fairly frequently. The speed was due to the fact that when a link 340 changed state, that fact became know almost instantly everywhere (due to the 341 fast flooding), after which the nodes all quickly recomputed their routing 342 tables in parallel, at which point the routing had stabilized in the new 343 pattern. This is in contrast with DV algorithms, where the effects of a change 344 in the topology had to pass through computations in each node on its way 345 across the network; additionally, the process might have to be repeated 346 several times before the new stable pattern was achieved. 347 Second, it detected destinations which had become unreachable more 348 quickly; this enabled the switches (which offered a reliable transmission 349 service) to discard packets for the dead destination more quickly, avoiding 350 buffer congestion from undeliverable and undiscardable traffic in the network. 351 Third, it was less likely to form loops (formation of which had been a severe 352 problem under the old DV routing algorithm, due to certain ill-advised 353 modifications in the algorithm which had promised other gains), and quickly 354 broke those which did form. 355 These advantages were not particularly useful to this application. 356 Since the system was so large, it was felt that practical load-based routing 357 was not possible. In such a large system there would be frequent topology 358 changes in any case; there were concerns that with the added changes of load 359 based routing that the routing would be less stable. The stability is 360 certainly useful, but not as crucial when the metrics are essentially static. 361 Likewise, the other two advantages, while noteable, can be met with 362 modifications to the basic DV algorithms. 364 The DV algorithms do appear have one advantage, which is that they 365 are apparently more suitable to routing in large nets. Since data is 366 processed through the routing table before being passed on, they very easily 367 can be modified to provide attenutation as a way of abstracting data. 368 (The algorithm is quite simple; as soon as the routes to all the subelements 369 of a routing element have the same next hop, it is no longer necessary to 370 send out routing tables listing each subelement individually; a single 371 entry for the element will suffice.) 372 However, this advantage is overwhelmed by a disadvantage, which is 373 that they cannot easily be enriched to handle the problems of both policy 374 based and type of service routing (which are technically very similar) without 375 exponential explosion in the amount of data which must be computed and 376 transferred. Since route calculation in DV algorithms depends on continuous 377 calculation of all possible routes in a distributed computation, handling 378 policy considerations means that routes to all destinations under all 379 conceivably desirable combinations (or allowed combinations, depending on the 380 system design) of policy requirement must be maintained. This is the only way 381 to have a route available for a given destination/policy combination when 382 traffic for that combination appears (or within any reasonable time of such 383 traffic appearing, as explained below). 384 (A possible fix for this problem involves only computing a routing 385 table entry for given destination/policy combination when traffic for that 386 particular combination arrives. Before that traffic could be forwarded, 387 however, the distributed algorithm would have to run, probably to 388 stabilization (discovering when that happens would be a good trick in and of 389 itself), to calculate the next hop at the first hop. This almost certainly 390 presents an unacceptably long delay before the traffic can be forwarded.) 391 In any case, the distributed nature of the DV algorithm requires far 392 more line bandwidth and computational power than the LS algorithm when 393 policies are included; in a large network these alone will present substantial 394 difficulties. Use of a DV algorithm in a world with policy routing 395 requirements is simple infeasible. 397 A key component of handling the requirements is the realization that 398 LS algorithms can handle this problem quite easily. [Chiappa84] Since each 399 node has a complete map of the system, inclusing all the links, it is quite 400 easy to indicate on each link what 'attributes', of either policy constraints 401 or service type, that link possesses. Since the LS algorithms can compute 402 routes on demand, it is only necessary to create a route for a particular 403 combination of reqirements when it is needed. It is easy, and costs little, 404 to tag each link with its attributes before the link information is flooded 405 through the system. 406 It is this characteristic of LS algorithms, that the actual route 407 calculation is separate from the distribution of the data, and can be delayed, 408 that is the key one. The fact that the calculation can be delayed (which makes 409 handling complex policy routing possible) is a fundamental difference between 410 LS and DV algorithms, and a key reason that DV algorithms are fundamentally 411 unsuited for use in the new IP routing architecture. 413 The problem with LS algorithms is that they do require a complete map 414 of the toplogy. As explained above, this is impractical, due to the size of 415 the target system. However, it is possible to modify LS algorithms to use 416 abstraction, so this is the approach chosen. This decision brings other 417 problems, though. 418 It turns out that compression alone is not an adequate means of 419 attack on the problem. There are too many topologies that simply cannot be 420 represented by a simpler but equivalent topology. Since the data must be 421 reduced to make the problem manageable, it is necessary to discard some, and 422 use thinning. The ramification of this step is that when routing data is 423 thinned, the lost information means that in many cases the system will fail 424 to detect possible routes with the required characteristics. This can lead to 425 the creation of non-optimal routes, or in the worst case, failure to find any 426 route at all, even though one does in fact exist. 427 The hardest problem thus becomes managing the discarding of 428 information, based on cost-benfit tradeoffs which the protocol cannot possibly 429 comprehend. Simply put, data must be discarded to make the cost of running the 430 protocol reasonable. However, taking this step has a cost elsewhere, in 431 non-optimal traffic routing; the problem is a classic cost-benfit tradeoff. 432 Thus, thinning involves value judgements, and is thus a matter of policy as 433 well as a technical problem. 434 The ramifications of these issues will be addressed later. 436 3.3 Addressing Fundamentals 438 Before moving on to review the proposed architecture, the final piece 439 of background that is necessary is to briefly review the fundamental network 440 concepts of addresses, routes, etc. 441 Although a number of papers have been written on the subject of 442 addresses and routes [Shoch] [Saltzer82], a considerable lack of understanding 443 of the basic aspects of these fundamental concepts still remains. Readers need 444 to be clear in their minds the difference between fundamental concepts (and 445 the objects which are the concrete instantiations of these fundamentals), and 446 the different kinds of names (and the reasons for and uses of these names) 447 which we may give these objects. 449 3.3.1 Object Spaces and Names 451 There has been confusion as to exactly what the fundamental object 452 spaces of networking are; most previous architectures have tried to make do 453 with too few. Previous work has also pointed out that common practise in 454 networking has been to too tightly bind the forms of names for these objects 455 to the objects themselves. 456 Two key object spaces used in this architecture are i) the node 457 identifier, which indicates one particular computing node to which packets 458 may be delivered, and ii) the network address, which specifies an attachment 459 point to the network; a network interface to which traffic may be routed. (In 460 fact, the term "address" is usually taken to refer to a particular kind of 461 name for a network attachment point.) Multicast concepts are not considered 462 here, since multicast can be built as a layer on top of this, and is thus less 463 fundamental. 465 Each of these object types may have one or more kinds of names. The 466 names may or may not haves structure. Names with structure are invariably 467 adopted to make some mechanism (often a mapping from that name to something 468 else) easier to implement. For instance, a attachment point may be identified 469 either by a unique, fixed length binary flat identifier (e.g. an Ethernet 470 interface number in a bridged network), or, as is more usual, a structured 471 heirarchical form (e.g. a typical IP address). In addition, there are mappings 472 between names and objects, and between different object classes. 473 As was mentioned, problems in thinking about the issues of routing and 474 addressing can occur when these object spaces are not clearly differentiated, 475 or when the form of the name for an object is not separated from the concept 476 of the object. An example of the former is the lack of distinction in the IP 477 architecture between attachment points and node identifiers; this has left us 478 with great difficulties in handling multi-homed hosts and mobile hosts. An 479 example of the latter is that a network address is usually taken to be a 480 structured heirarchical item, but this is in fact just one possible way of 481 naming attachment points; a very useful name, to be sure, but not the only 482 one. 484 Whenever one has different classes of objects, and names for them, 485 several questions immediately arise. The first is "do we have the right 486 classes", second "what is the mapping between the classes of objects", third 487 is "how many names, and of what form, do we have for each class of object", 488 and fourth "what is the mapping between the names and objects". 489 The mappings form the heart of the power, and the problems. Two 490 aphorisms of computer science illustrate this: the first (due to B. Lampson) 491 is "All problems in Computer Science can be solved by adding another level of 492 indirection"; the second (due to D. Clark) is "The function of an operating 493 system is to establish many different names for the same object, so that it 494 may busy itself keeping track of the mappings between the various names." 495 Do we have the right fundamental objects? Exactly which names and 496 mappings are useful in this instance? 498 3.3.2 Names and Mappings 500 It is clear that the two object classes named are highly useful. Are 501 there any remaining problems, the solution to which requires yet another 502 object class (and associated mappings)? Only one appears possible; the problem 503 of heirarchical addresses implying heirarchical routes. This topic cannot be 504 treated in full at this point in the document; the architecture as given 505 solves this problem, but perhaps not in an efficient enough way. It may be 506 necessary to add an extra object class to deal with it. For the moment, 507 however, the answer appears to be that the two mentioned are enough. 508 As to the mappings among the classes, this also appears simple enough. 509 Just as in the real world, a single node may have several network interfaces, 510 a single node identifier may map to more than one attachment point. Also, just 511 as hosts may move, the mapping from a node identifier to a network attachment 512 point may change. 514 The only namespace for nodes which appears to be useful is a 515 relatively short, fixed length, pseudo-flat binary identifier. This name is 516 intended for solely for globally unique identifaction of nodes, and for 517 efficient processing by automatons; this dictates the form of the name. (Since 518 the space will probably be split up to various number assignment authorities 519 for each of administration, it only appears to be flat.) Since it appears (for 520 reasons to appear below) that the most useful form of the network address is 521 long and complex, having at least one name for the destination in the packet 522 which is easy to manipulate is desireable. There does not appear to be a use 523 for a different kind of node identifier at the moment, but it could be added 524 if need be. 525 This is obviously in addition to the existing domain names, which are 526 heirarchical character string names for hosts. These names are obviously 527 intended to be useful to humans, and the structure in them is intended to make 528 interpretation by a distributed database (the Domain Name System) easier. It 529 is entirely feasible that domain names which represent, for example, services 530 could map to more than one node identifier, but that is a different issue. 532 The names of network attachment points, the address, present a more 533 interesting problem. An address usually does two things. First, it uniquely 534 identifies a connection point to the network. Second, it does so in a 535 structured manner, which allows something useful to be done with it. Exactly 536 what that structure is depends on what other uses it is put to; most often the 537 structure of the address is used in routing. 538 Normally, groups of attachment points which are topologically related 539 are given related addresses. Usually, this allows the number of different 540 destinations which must be tracked in the various routing devices througout 541 the network to be reduced (in its simplest form, this allows routing tables to 542 be smaller). That is, rather than keep knowledge of all the individual network 543 attachment points, a routing device can keep information on collections of 544 network attachment points, at a considerable savings. 545 It may have other benefits; in this architecture, it also does several 546 other very important things. First, the structured address allows the point on 547 the topology graph which the address names to be found easily, without mapping 548 through any additional object class, or other attachment point name. Second, 549 it helps provides a representation by which topology information can be 550 distributed. Third, the structure of the address space provides a framework 551 for the abstraction process by which simplified graphs of the topology are 552 created. 553 Finally, in the current version of this architecture, the address 554 (which is heirarchical) in involved in creating those routes which take the 555 least amount of effort to compute (sometimes called "no-brainer" routes), 556 that route being basically heirarchical. (It is this latter function which may 557 prove inefficient to overload onto the address of a network attachment point, 558 necessitating the creation of a different object class or naming space for 559 network attachment points.) 561 Note that all these functions are usually performed by a single 562 kind of name, a structured address. However, other possibilities have been 563 suugested. 564 One proposal is that each network attachment point be given a unique 565 binary flat identifier; this would allow the creation of multiple, 566 independant, structured namespaces (i.e. address spaces), each of which have a 567 separate mapping into the first namespace which identifies all attachment 568 points. The claimed advantages are that it would be possible to experiment 569 with new addressing schemes, or introduce a new one, or even operate with 570 several different ones in use at the same time. 571 This possibility has been discarded in this architecture, however. The 572 whole point of an addressing system is to allow traffic to flow between all 573 the myriad parts of the Internet. To do that, it is necessary to pass around 574 routing information, and the form in which this is passed around is inevitably 575 that of addresses. A new address scheme, resulting in an address form which 576 the old routing architecture did not understand, would inevitably interrupt 577 this flow. 578 Moreover, should it be necessary to supersede the addressing scheme in 579 this architecture (if adopted), it would be just as easy to create a new 580 mapping from node identifiers to attachment points as it would to create a new 581 mapping from attachment point names to attachment points. Alternatively, 582 mappings could be created from old attachment point names to new ones 583 directly. No good reason can be seen for the flat namespace for attachment 584 points, so incurring the cost of it should clearly be avoided. 586 4 Routing and Addressing Architecture 588 It is necessary to consider some ramifications of some of the 589 requirements in detail, and the steps taken to meet them, before the entire 590 architecture can be outlined. 592 4.1 Requirement Ramifications 594 The two major ones have to do with the trust model requirement, and 595 the ability to expand the attribute list. 596 Briefly stated, the trust model problems is that some users may have 597 policies on which links they will and will not use that cannot be described 598 in anything less than a general purpose computational notation. Moreover, in 599 the most extreme cases, some users may not trust outside agents to pick a 600 route for their data, even given a complete statement of their requirements. 601 This means that computations in intermediate nodes cannot be used to route 602 traffic. This flies in the face of the current architecture, which assumes 603 traffic is routed on a hop-by-hop basis; i.e. each switching node makes an 604 independant decision on what to do with the traffic. 605 The attribute list problem is a more general consequence of the 606 specific observation above, in the discussion of the requirements, that it is 607 probably not possible to completely specify what policy attributes will be 608 needed at the moment. If the new system is to last, it must be able to change 609 and expand its capabilities. To do this, it is necessary to be able to invent 610 new types of attributes for links, and phase them in incrementally (since 611 such changes cannot be coordinated instantaeously across a large system). 612 This presents a problem, since this seems to violate the restriction given 613 about in the discussion of LS algorithms, namely, that all the nodes run the 614 same route generating algorithm. If one node is taking certain attributes on 615 links (and requests to use them in packets) into consideration when 616 generating routes, and another is not, this can potentially form routing 617 loops. 618 These two problems appear substantial, yet both can be solved by the 619 same mechanism. In addition, that mechanism allows yet more problems to be 620 solved, as detailed below. 622 4.2 Architectural outline 624 The general outline of the architecture is as follows (each element 625 will be discussed in more detail below). 626 The routing architecture will be a multi-level area (i.e. 627 heirarchical) LS system; in the topology graph representation of the network, 628 links and nodes have attributes. The exact algorithm for generating routes, 629 given the topology map, is not specified as part of the protocol (but a 630 default algorithm can be provided as an appendix). Abstraction of data will be 631 determined primarily by external mechanisms (although a simple default will be 632 provided either as part of the protocol or as an appendix), and in any case 633 clients are not bound to accept any abstraction unconditionally. Routes will 634 be completely determined by the initiator of the traffic; i.e. all packets 635 will be source routed. Packets will belong to ephemeral associations called 636 'flows'. (There may be other forces acting on the architecture which make 637 flows desirable; if so, several things can be done with this new mechanism.) 638 A new kind of address will be created, for use in making routing 639 decisions. The existing IP address field will be retained as well (exactly as 640 is in the short term), but the contents will be put to slightly different use 641 as a node identifier. 642 In the short term, hosts will continue to operate with no changes at 643 all, and use the existing packet formats for their interactions with routers, 644 although there will be certain optional optimizations that speed things up, 645 but are not necessary. In the long term, a transition to a longer version of 646 the node identifier (the old IP address) will be necessary. A number of 647 factors will probably eventually combine to cause the definition of a new IP 648 packet format, but most of those forces are outside the scope of this 649 document; however, phasing this longer version in will probably occur as part 650 of that transition. 652 A key thing to notice about this architecture is what is not part of 653 the architecture and protocol. Neither the algorithm to create routes from 654 the topology database, nor the exact method by which abstraction occurs are 655 part of the architecture. These are also the two hardest problems, and the 656 two in which future work is most likely to bring improvements. It is a key 657 feature of this proposed architecture that these two areas can be left 658 outside the scope of the protocol; future improvements can be easily phased 659 in incrementally. 660 Route generation in this architecture will need routing algorithms 661 which have a different goal from most existing work, such as the Dijkstra 662 algorithm. Most known routing algorithms create an entire routing table of 663 optimal routes to all destinations; since this has been what was needed in the 664 past, this is the area in which most research has occurred. The problem of 665 finding the optimal (or a good approximation thereof, within limits) route 666 between two points in a graph, ignoring other destinations, has not been 667 a topic of much work. This only increases the need to leave flexibility in 668 this area; improvements in algorithms and heuristics tend to be slow to 669 appear. 671 The things which are part of the routing architecture and protocol are 672 a way of representing and characterizing the network topology, a way to 673 distribute this information, and a way to set up traffic flows. Everything 674 else can be left and specified later; a key to the power and flexibility, as 675 well as the ability to last (gracefully), of this architecture. 676 Upon some reflection this seems likely to be a theoretical minimum 677 for performing those tasks. It is not clear whether the fact that the two 678 hardest problems are left outside is fortuitous or a reflection of some 679 deeper correctness. In any case, the minimal design does limit the amount of 680 work to be done, as well as limit the possibility that something will be done 681 wrong or in an inflexible way. 682 "Perfection has been attained, not when there is nothing left to add, 683 but when there is nothing left to take away." [Corbato] 685 4.2.1 Multi-level LS Algorithm 687 The LS class of algorithm is chosen, basically for the reasons listed 688 above in the discussion of these algorithms. It is really the only practical 689 way to handle a system with complex acccess restrictions on links which form 690 a key part of policy considerations. The expandable attibute list allows 691 future growth. 692 The algorithm has to be multi-level to handle the very large amount of 693 link state in the system. Even if the system were restricted to distributing 694 information about AS's, the general consensus is that a single level will not 695 be able to handle the number of AS's we expect to be deployed in the 696 reasonable future. 698 However, it is also felt that the time and need for AS's, and the 699 strict division of routing in inter- and intra-AS, is past. AS's are a limited 700 and simplistic mechanism that was created long ago to fulfill certain limited 701 goals, primarily that of providing routing firewalls; since the new 702 architecture can do all these, and better than the AS concept, it is now 703 entirely appropriate to discard AS's. (This does not mean that the concept of 704 policy groupings would be discarded; far from it. What it does mean is that 705 there will not be a particular layer which is called out for special 706 treatment.) 707 The primary reason for the introduction of AS's was to provide some 708 routing firewalls in the system. Since the new architecture will problem more 709 flexible and robust firewalls, retaining the archaic AS mechanism is 710 pointless. An additional advantage of AS's (and the division of the task of 711 routing between IGP's and EGP's) was to allow different routing technologies 712 to be used. The extreme power and flexibility of the new architecture makes 713 this less useful, and in any case, the fact that the process by which the 714 representation of an area is constructed (the abstraction process) is not in 715 the scope of the protocol means it would still be possible to use other 716 routing technology within an area, and pass the results of that process up as 717 the representation of the topology of the area. 718 The new system would be responsible for all routing in the IP 719 architecture; it would be able to depict, at its lowest level, the physical 720 transmission assets of the system. This unification of routing would not only 721 reduce the complexity (and likelihood of problems, implementation and 722 configuration cost, etc), but bring the full power and flexibility of the 723 new architecture to bear at all levels. A number of problems exist today 724 because of the split between inter and intra-AS routing; removal of this 725 artificial barrier allows greater flexibility. 727 The use of a link-state architecture does bring with it the attendant 728 difficulties of how to abstract link-state data. The use of thinning, 729 necessary for useful abstraction, brings with it the difficult task of chosing 730 which data to discard, and the problems caused by loss of the discarded 731 information. As noted above, this cannot be solved by purely technical means; 732 value judgements must be made about which information to discard. It will be 733 usually be necessary for the administrators of any given area to help decide 734 what the representation of that area will be when the internal details are 735 hidden. 736 Since this is now a problem of entering configuration information, it 737 is desireable to do this in a way that allows no chance for inconsistent data. 738 A default algorithm will also be provided, for those who do not care what the 739 representation of their area is, or are unsophisticated and cannot participate 740 in chosing the representation of their area. The fact that there is no 741 specified algorithm for doing this also allows improved default algorithms to 742 be incrementally deployed as they are conceived. 743 However, the problem of non-optimal or unfound routes remains. The 744 solution to this part of the puzzle requires the next key component. 746 4.2.2 Source Routing 748 The source routing is a necessary consequence of both the trust model 749 part of policy considerations, and the expandable attribute list, as outlined 750 above. Having the source set the route avoids both of these difficulties. As 751 mentioned, it also allows the incremental deployment of better algorithms for 752 creating routes as ongoing research provides them, and also provides a means 753 to attack the non-optimal route problem, as noted immediately above. 755 Note that the route (nor indeed, the new style address) is not 756 necessarily carried in each and every packet; this is an engineering decision 757 to be made on the basis of the costs and benefits of doing so. The costs are 758 primarily the increased overheard of carrying around the extra data. There is 759 another issue in that the existing IP packet format will probably not allow 760 'on the fly' modification to hold the source route, since the latter will 761 probably be too large to fit into the IP header. Depending on the length of 762 the addresses, these could be a problem as well. This could be solved by 763 'wrapping' the packets, but at considerable cost in complexity and switching 764 speed (and some in line utilization). 765 The benfits of carrying the source route and/or address in each packet 766 are that the routers may remain more stateless. It is anticipated that routes 767 will not be carried in packets, and there will be a 'route set-up', as part of 768 the 'flow set-up', which happens invisbly to the client of the packet layer. 769 This flow will not be critical state, like a connection, but rather a hint. (A 770 'hint' is data which allows processing to be optimized, but which is does not 771 have to be present to allow correct operation.) This may be recreated by the 772 routers without reference to the source of the flow setup should any 773 intervening node fail. 775 Obviously, since the source (or an agent close to it) choses the 776 entire route, it is trivial for the source to enforce whatever constraints it 777 wishes on the path that its traffic takes (even constraints which are not 778 stateable in anything less than a general purpose computational language). 779 Alternatively, if the agent computes routes using links with attributes it 780 understands, but which the intervening switching nodes do not, the traffic 781 will be routing correctly, their lack of comprehension notwithstanding. 782 Also, if in computing a route, the agent generating the route comes 783 across an attribute it does not understand (either because it was recently 784 introduced, and the agent does not yet know how to deal with it, or because 785 it is a private attribute which the agent will never understand), the 786 agent will still be able to compute a route. If all attributes carry some 787 limited information about whether they are restrictive (certain types of 788 traffic will not be allowed across) or informational (giving information 789 about the link) it would be possible for a route to use links which have 790 attributes the agent does not understand. 792 Since the entire route is calculated by one agent, it clearly does 793 not matter if different agents use different algorithms for generating 794 routes. Deployment of new algorithms, or a choice between several existing 795 ones (for example, one which is fast but which does not produce good routes 796 would be useful for one-shot traffic, whereas more complex and expensive 797 ones would be appropriate for long-lived flows sending a lot of data) 798 thus becomes trivial. [SalzterSR] 800 4.2.3 Local Abstraction Control 802 As for the non-optimal route problem, it was noted above that the use 803 of hop-by-hop routing required both a consistent algorithm and a consistent 804 database. Discarding hop-by-hop routing allows relaxation of the latter 805 requirement as well. This allows a powerful (and previously unconsidered) 806 adaption of the typical operation of an LS algorithm. Canonical LS algorithms 807 require everyone to have an equivalent map. 808 ("Equivalent" is used instead of "identical" since in existing 809 multi-level protocols such as OSPF, agents in different areas will each have 810 (identical) top level maps, as well as maps of their own area, but of course 811 these latter maps are different. All routers within a single area, however, 812 will (and must) have identical maps.) 814 However, there is no requirement in this architecture that this be so. 815 Neighbouring routers at the same level may have wildly different maps. One 816 might have only a default representation of a neighbouring area; another, 817 which is sending a lot of traffic into that area, might have detail on the 818 internal connectivity of that area, to allow it to pick the optimal entry 819 router into that area for the traffic it is handling. Any node may call for 820 more detailed topology information about any part of the system it wants, 821 provided that that information is accessible to it, and the cost of providing 822 that information are borne somehow. 823 However, the implications of lifting this restriction are 824 considerable. As noted above, the thinning problem is essentially a 825 cost-benfit tradeoff; making this tradeoff at the area which is being 826 described imposes the area's idea of the correct cost-benefit tradeoff on 827 everyone. However, allowing each route generator to make its own decision on 828 how much detail to keep in its maps allows this cost-benfit tradeoff to be 829 made at the client, i.e. with far greater flexibility. 830 It will be necessary for the costs of keeping maps with more detail 831 to be shifted to those agents which wish to keep them; this will require 832 attention at the time that accounting and resource usage algorithms are 833 brought to the network. 834 The default abstraction algorithm is thus seen as that which will 835 provide the theoretical minimum of data necessary to route traffic through the 836 system. The actual routes taken by traffic under this algorithm will thus be 837 strictly heirarchical. Looked at another way, local abstraction control thus 838 allows a way to do non-heirarchical routing. 840 5 Details of the Architecture 842 Many of the components necessary to this routing architure and 843 protocol can be 'borrowed' from the work being done on the Open Routing 844 system, and similar LS systems such as the ARPANet algorithm, OSPF [Moy], etc. 845 These include the mechanisms to do reliable database distribution and flow 846 setup. According, description of these solved problems will be skipped in this 847 document. 848 This section includes more detail on certain key parts of the 849 architecture, along with calling attention to those parts in which engineering 850 questions remain. 852 5.1 Multi-Level Topological Representation 854 The first step is to consider the maps (graphs, actually) which 855 represent the actual detailed topology. It is worth noting that in the graph 856 representation of typical networks, there are usually two kinds of nodes; 857 'network' nodes and 'router' nodes. The arcs then represent network 858 interfaces. It is possible to have only a single kind of node (either 859 networks or routers), but this is artificial, loses valuable information, and 860 is more difficult to work with in practice than the more complex version. 861 This architecture will almost certainly use this type of model. 862 In the maps, it will be possible to take an contiguous section of the 863 graph (i.e. some number of nodes and their connecting arcs), and reduce it to 864 a simpler representation. Such a reduced section is called an 'area'. Areas 865 may be nested, and areas have as an attribute a level; an area which contains 866 another area has a level one higher than the contained area. 867 It is unclear whether an area will need to be represented as a section 868 of graph, or just a node. In either case, a new type of node for an area is 869 probably needed. The issue probably hangs on whether the rules for 870 constructing topologies demand router nodes between area nodes or not. In the 871 former case, the minimum representation of an area would be the collection of 872 border routers plus a pseudo-node for all the rest of the topology of the 873 area, to which the border routers are connected. If the area has complex 874 transit policies which vary depending on which pairwise set of border routers 875 are picked, a more complex representation allowing this to be expressed would 876 of course be necessary. 878 It is not clear whether it is best to allow only 'strict' reduction, 879 in which an area of level k would be allowed to contain only obects of level 880 k-1, or whether 'loose' reduction, in which objects of varying levels less 881 than k could be contained, is preferable. The latter is clearly more flexible, 882 but might make the engineering more complex. This decision can probably be put 883 off until the detail design happens. What is important is to realize that the 884 division into areas provides the framework for the default abstraction 885 algorithm; agents outside an area will not in general have detailed 886 information on the internal topology of the area. 888 On the subject of border routers, it seems wisest to set the rule 889 that all routers belong to a single area. This is a good match to reality, 890 where most of the physical assets have an owner; the half-router model has 891 proven to be less useful in practise. 892 One aspect of representation that needs to be addressed is the 893 question of configuration errors; this is the most likely place for such 894 errors. One technique that appears useful is to simply indicate to each router 895 whether or not it is a boundary router for a k level area, not which k level 896 area it belongs to [BBN]. Thus, misconfiguration of a router simply joins two 897 k-level areas togther, but has no other ill effects on the routing. Similar 898 approaches must be taken throughout this aspect to minimize configuration 899 and prevent configuration errors from being a major problem. 901 In any case, it is clear that some decisions about open questions 902 need to be taken about the multi-level topology representation before any 903 other parts of the design can be worked on in detail. Obviously, these 904 decisions may need to be revisited if work elsewhere reveals that a poor 905 choice has made the design of some other part more complex than need be. 907 5.2 Multi-Level Addresses 909 The address format chosen will need to map closely onto the 910 representation of network topology, which in turn is chose to make the job of 911 the routing simple. Remember, the address is simply a way of naming an 912 attachment point to the network, in other words, specifying a place in the 913 graph, and it is essential that given an address, it must be easy to correlate 914 that address with its location in the topology graph easily. (It might be 915 argued that the 'address' need not have that property, but it might map to 916 something else which does. All that is saying is that terminology has been 917 confused, and the wrong name for a network attachment point has been called 918 the address. The final concept will inevitably have to be one which is easy to 919 locate.) 920 In essence, what is proposed is a multi-level heirarchy, with a 921 variable number of levels, each of variable length. This may seem like 922 overkill, but remember that these addresses are only needed to create flows, 923 and since the cost is minimal it is better to have too much flexibility than 924 too little. The mapping from addresses to the map is fairly simple; the first 925 element of the address identifies which top level area an address is in, the 926 next element which of the next level areas within that top level area, and so 927 on. 929 In any event, the bottom level will be the level representing real 930 physical assets, and numbering will proceed up from there. The advantage of 931 this is that two different systems with differing address spaces, each 932 allocated without reference to the other, can be joined by the simple 933 expedient of creating a new level above the top of each existing system and 934 making each system appear as a simple object in that level. [Reed] 935 Alternatively, a small independantly numbered system could be joined onto a 936 large existing system as a branch at the appropriate level. 937 This will also avoid useless arguments about whether or not something 938 deserves to be a 'top-level' area or not. Since there is no such thing as a 939 top-level area, pointless fights over status should mostly be avoidable. Note 940 that good functioning of the resulting system demands proper engineering of 941 the topology, and of the areas; since the area definitions provide the 942 framework for the abstraction process, which in turn affects the default 943 heirarchical routing, a poor choice of area boundaries will cause the default 944 abstraction process, and the default heirarchical routing, to work less well, 945 although it will continue to function. 947 The analogue in the adressing area to the question of only allowing 948 'strict' areas is whether or not networks (and presumably hosts and routers 949 as well) can have numbers at any but the lowest level. If a k level area is 950 allowed to contain physical assets, presumably they can be addressed with 951 k-1 level addresses, without going all the way down to the bottom level. 952 The question of exactly what form the addresses of networks and 953 routers (if any) take is open. In the current architecture, no real provision 954 was made for numbering networks, although the convention of a zero 'rest' 955 field has come to mean the network. Routers are currently indistinguisable 956 from hosts (which is good and bad). In the new systems, hosts will not have 957 addresses per se; the lowest level item which can be addressed is a network 958 interface, and presumably typical hosts will have one each. 960 Once again, choices have to be made, but with the understanding that 961 they may have to be revisited in light of work elsewhere on the architecture. 963 5.3 Topology Information Flooding and Route Generation 965 It is next necessary to consider the question of which devices perform 966 these functions. It seems most plausible that the first function is co-located 967 in the routers themselves, for reasons of fate-sharing; connectivity 968 information is flooded through the very connection elements that are being 969 described. This also removes dependency loops where topology flooding agents 970 which are not routers are required to make contact with neighbour topology 971 flooding agents through routers. 972 Route generation could, however, quite easily be performed in separate 973 devices, which communicate with routers (both local, and distant if they wish 974 to have detailed information about distant areas). It might be useful to build 975 this function into routers, but this is an implementation decision. Certainly, 976 clients with complex policy requirements will probably desire to generate 977 their own routes. 979 5.4 The Default Abstraction Algorithm and Local Abstraction Control 981 Given the discussion above, the default abstraction algorithm is very 982 simple. As stated above, the division into areas provides the framework for 983 the default abstraction algorithm. The routers which are border routers for an 984 area are responsible for doing the abstraction on the area topology when it is 985 advertised outside the area. 986 Two possibilities exist for a simple algorithm to provide a default 987 representation of an area. One, the N^2 model, maps the area as a complete set 988 of connections between all the border routers. This model can fairly 989 accurately represent the true characteristics of the connection between any 990 two pairs of routers. (Of course, how to do so in the presence of policies 991 and types of service, where a multitude of possibile connections are possible, 992 will require a bit of work; probably the least policy-limited path should be 993 advertized.) In the other, the pseudo-node model, all the border routers are 994 connected to a single node in the center. This cannot accurately represent the 995 metrics between any two border routers, but an averaging system will give a 996 good guess. 997 The option is always available to go to a representation with human 998 input, or to a representation prepared by some other algorithm. Some control 999 needs to be created to prevent areas from flooding the system with 1000 unnecessarily complex representations of themselves. 1001 Of course, if an area is represented solely by a single pseudo-node, 1002 none of these problems arise, which is the attraction of this possible way of 1003 representing an area. The disadvantage is that then areas must have transit 1004 attributes which mirror the attributes (both policy and type of service) on 1005 the actual transmission links which connect the border routers. 1007 The working of the local abstraction control (somewhat inelegantly 1008 named the "Blister Model") is simple to understand in this context. Generally, 1009 any routing agent outside an area is given, as a default, whatever 1010 representation that area has decided to purvey. However, should a routing 1011 agent wish a more detail of a non-local part of the map, nothing is to stop it 1012 (other than information-hiding access control, of course) getting the 1013 information and upgrading its map. 1015 5.5 Virtual Links and Flow Repair 1017 One concept which will probably appear as part of the representation 1018 of an area is that of a virtual link. Where it is desired to describe the 1019 connection between two border routers, without providing detail on the 1020 constituent links which actually connect the two, a virtual link (with 1021 the attributes of the complete path between the two) could be advertised. 1022 One key aspect of this idea is the ability to do local repair on flows 1023 when topology changes happen. If a virtual link at level k, which was 1024 advertised to a source route generator and which is used in creating a flow, 1025 suffers a component failure, two outcomes are possible. First, the virtual 1026 link may be reconstituted with the same attributes using other lower level 1027 assets. In this case, the repair would be local, with no necessity for 1028 intervention on the part of the source route creator. As an option it might be 1029 notified if some attribute, such as delay, increased more than an allowable 1030 amount on some component it used in setting up a flow. Second, if such a 1031 reconstitution cannot be made, the k+1 level virtual link of which the k level 1032 link is a constituent is notified, and the algorithm is then run recursively 1033 at a higher level. Only if some asset which the source route creator fails 1034 would it be necessary for the creator to select a new path for the flow. 1036 5.6 Partitioned Areas 1038 Handling of partitioned areas needs to be addressed. A number of 1039 methods are possible. One obvious method is to reconnect the two parts of the 1040 partitioned area by going through another area. 1041 Another elegant method gives each level 1 area a globally unique 1042 identifier. A k level area is given the identifier (at k level) of the lowest 1043 (or highest, or some unique algorithm) numbered k-1 level area within it. 1044 Then, if a k level area partitions, it automatically creates a new k level 1045 area, which is automatically numbered from its constituent k-1 level areas. 1046 The disadvantage of this is that the address of everything within the new k 1047 level area has changed, which is probably a substantial disadvantage (although 1048 not insuperable). 1050 5.7 The Node ID 1052 The node identifier (what used to be the IP address) is a key part of 1053 the system; not only does it provide new capabilities, but it makes the new 1054 system incrementally deployable. Instead of being a number with structure, as 1055 it is currently (which is causing inefficient use of the number space), it is 1056 simply a unique 32-bit (initially) number. That way, we put off the day when 1057 that address space runs out, since we can use it efficiently instead of 1058 wasting large gaps, as we do now. 1059 A number of outstanding issues, particularly mobile hosts and 1060 multi-homed hosts, can be solved with this, with no change to the upper 1061 levels. An open TCP connection to a given node identifier will stay open even 1062 if the node moves and gets a new address. (The flow may need to be rehomed, 1063 but this will be invisible to the TCP, and perhaps to the host entirely.) If 1064 an explicit mapping exists from a node identifier to multiple addresses, many 1065 issues having to do with multi-homed hosts (both for reliability as well as 1066 bandwidth) become much simpler. 1067 The source and destination of packets in the network will continue to 1068 be identified by these identifiers. If we chose not to include the new 1069 addresses in each packet (as seems likely), a packet arriving at a router is 1070 assigned to a particular flow by inspecting these numbers. This process will 1071 be at least as quick as current routing, and if the addresses are not included 1072 in the packets, there will be no extra line overhead either. 1074 5.8 Mapping to the Address, from the Name and from the Node ID 1076 Obviously, a system for providing the new addresses, and mapping 1077 between them and other identifiers, such as host names and identifiers, needs 1078 to be available. It clearly ought to be distributed and replicated. We already 1079 have a distributed replicated system for containing mappings; the DNS. It 1080 would probably be simple to add this mapping as well. 1081 When going from the string name, the obvious thing is to return the 1082 new address as well. For clients which need to map from node identifiers to 1083 addresses, some analogue of IN-ADDR will have to be provided. 1084 One thing to be careful of is that in the process no dependency loops 1085 are formed. For instance, error reporting might need to get an address if all 1086 that is on hand is a packet with the node identifier. The actual process of 1087 getting routing information around would have to be examined carefully to make 1088 sure it does not rely on the existence of this mapping system, otherwise 1089 dependency loops will certainly form. 1091 5.9 A Sample Route Generation Algorithm 1093 One simple way of generating a route in a complex policy environment 1094 is to run over the map, dropping all links which are unusable for policy 1095 reasons or because they do not match the type of service desired. It would 1096 then be possible to run the Dijkstra algorithm to create a routing tree, and 1097 thus a route, for a given metric which is it desired to minimize (probably 1098 delay or cost). To optimize several metrics at once, a formula for weighing 1099 the metrics together to create a composite metric needs to be provided; as 1100 each link is examined in the Dijkstra, the composite metric will be calculated 1101 from the exact metrics of the link, and the composite metric will be what the 1102 Dijksta minimizes. 1103 Metrics such as bandwidth, or MTU, where minimization over a path is 1104 inappropriate, would be handled by dropping inappropriate links in the first 1105 phase; if no route can be found, the actual requirement on this metric could 1106 be lowered and the process repeated to see if a route appears when a less 1107 optimal value is allowed. 1109 5.10 Authentication and Robustness 1111 Making the system robust against attack is vitally necessary. One 1112 approach would be to tag all data with a private key system; this guarantees 1113 that topology information could not be modified as it is flooded through 1114 the system. The same approach could be used in flow setup; acknowledgements 1115 tagged with the private key would prevent the flow from being hijacked to 1116 a different destination by a corrupted switch (although it could be copied). 1117 Protection against denial of service attacks are more difficult. In 1118 the above example, the corrupted switch could prevent the flow from being 1119 set up, although it cannot make it appear that the flow has been correctly 1120 set up when it cannot. Of course, if the switch refuses to set up the flow, 1121 an alternate path could be picked which avoids that switch. 1122 Another difficult problem is bogus connectivity information. Some 1123 checks can be made, such as ensuring that both ends of a link agree that it 1124 exists, but this will still not catch collusion. Once again, it can be 1125 detected that this is happening if the flow does not set up correctly, and the 1126 errant switches avoided. However, if the switches claim a direct connection, 1127 which causes traffic to flow to them, and then route the traffic through, 1128 it will be difficult to detect except by measuring the service provided. 1130 6 Possible Optimizations 1132 Although this document is not an engineering design, there are a 1133 number of possible optimizations which are worth discussing here. Many other 1134 such optimizations are possible. They have not been considered in detail here, 1135 since they are generally low level engineering and depend on the exact details 1136 of the structure chosen. The key focus in this document is to discern the hard 1137 problems, and pick a broad line of attack on them. 1139 6.1 Default Routing Tables 1141 One useful optimization which might be included is to provide a 1142 facility for handling traffic without the overhead of calculating a route 1143 and setting up a flow. [Estrin] Needless to say, this could only be done 1144 for a limited number of classes of traffic, but it is possible. Basically, 1145 a way would exist to indicate that traffic was not part of any flow, and 1146 one (or a small number) of default routing tables for such traffic would be 1147 precomputed, in all routers, as is the current practise. 1148 This would not be unreasonably expensive. For example, assume that 1149 the system contains 5 levels, and the fan-out at each level is on the order 1150 of 200. Thus, the system could handle up to 200^5 networks, or 3x10^10 1151 networks; this should be large enough for the reasonable future. Such a 1152 system would only mean that the average router with a minimal map would 1153 need a map with 5*200*(3+1), or 4000, nodes (assuming that routers outnumber 1154 networks/areas by a 3:1 ratio, which seems about right from the current 1155 system; this gives triple connectivity to each network, or fairly redundant 1156 connectivity). Assuming each router is connected to 3 networks, then the 1157 map would contain 5*200*(3*3), or 9000, arcs. Such a map would be fairly 1158 easily handlable by even the current generation of router hardware. 1160 The problem with this idea (within this architecture) is that a 1161 mapping must still be created from the destination node identifier to the 1162 address. How does this mapping happen? One possibility is to have to have 1163 first hop router (or the host) add it to the packet. Alternatively, each 1164 router along the path would have to do the mapping. Clearly, the mapping in 1165 each intermediate router could be installed via a setup, but this would just 1166 get us exactly what we are trying to avoid! 1167 Also, it is not clear if this optimizations will be useful in the 1168 future. It remains to be see whether if, in a system in which policy 1169 configuration and access controls are much easier, and thus more common, much 1170 traffic is sent out in the default class, and if the free, general access 1171 model of network use we have enjoyed continues. If not, the concept of default 1172 routing tables is probably not a useful one, since almost all traffic would 1173 need a flow set up to handle it. 1175 6.2 Map Discarding in Stub Areas 1177 One additional idea, if default routing tables are included, is to 1178 support stub areas. The complaint might be raised that even supporting a 1179 map with 4000 nodes (from the example above) is pointless if an area is 1180 only singly connected to the outside world, or neither wants to support 1181 transit traffic nor pick optimal area exit routers. In these cases having 1182 the topology map for the rest of the system outside the area is 1183 unnecessary; the traffic is simply sent to any border router, and is routed 1184 from there. 1185 (The former simplification is obvious; doing either of the latter 1186 two means that traffic must be able to differentiate as to which border 1187 router is the best one to head toward; i.e. traffic inside the system must 1188 have access to a full outside map to know which border router is the best 1189 exit router, if routing loops are to be prevented.) 1191 6.3 Flexible "No-brainer" Routes 1193 One major potential issue with the current architecture is the fact 1194 that the simplistic "no-brainer" route is that which is computed with the 1195 minimal map, and that minimal map implies strict heirarchical routing. 1196 The problem with that is that a K level area, such as a campus, which 1197 in actual physical terms has connections to several long-haul networks, each 1198 of which is probably a separate K+1 level area, has an insufferable choice to 1199 make. Depending on which K+1 level area they associate themselves with, any 1200 traffic using the simple "no-brainer" routing will get to that K level area by 1201 means of the long-haul network with which the K level area is associated in 1202 its global address. This is the problem referred to some while above, where it 1203 was indicated that perhaps using the address to generate the "no-brainer" 1204 route is an overload of that name which finally breaks down. 1206 One solution to this problem involves the use of what are called 1207 "route suffixes" [Clark]. When the host-name to address translation is 1208 performed, the address which comes back comes with several incomplete source 1209 routes, which represent potential useful paths, terminating at the 1210 destination, through the nearby topology. If the most detailed (last) item in 1211 the route suffix is not know to the source, it backs up and tries the previous 1212 (less detailed) item, and so on. Given several route suffixes, probably one 1213 for each major long-haul network which an area is attached to, the source can 1214 easily make a determination as to which long-haul network it prefers to 1215 use to get to the destination. 1216 The major advantage of this scheme is that is it fairly efficient; a 1217 small amount of extra data is passed back at the time of the address lookup 1218 which allows a choice to be easily made. What mechanisms are available in this 1219 architecture to do this? 1221 One rough equivalent in this architecture can easily be found by 1222 allowing each network attachment point to have multiple addresses; this would 1223 indicate that a destination could be reached via multiple long-haul networks. 1224 (This is equivalent to allowing K-level areas to overlap.) This solution is 1225 not preferred since it conflicts with a previous goal of the address, which is 1226 to provide a way of concisely describing the topology. If any network 1227 attachment point can have many names (addresses), this will be more difficult. 1228 In effect, this approach overloads yet one more function onto the 1229 address, which is to optimize picking a slightly more optimal route; the 1230 address is not really suited to having to support this one further function, 1231 however. There are a number of ways to do this which do fit well within the 1232 architecture, though. 1234 The first is a slightly more general variant of the original scheme, 1235 which is to use the local abstraction control mechanism to discover some 1236 details of the topology around the destination. This is seems to be less 1237 efficient than the "route suffix" mechanism, but has the same effect; the 1238 source is given more information which allows it to make a choice. 1239 The second, in some senses a variant of the first, is to remove from 1240 the map all areas which do not allow transit traffic; i.e. "stub" areas. This 1241 would greatly diminish the number of nodes in the map, and allow more detail 1242 to be kept. Whenever a source needed to send traffic to a destination in that 1243 stub area, it could pick up topology information about that area and enter 1244 it into the map. 1246 Both of these represent a slightly more formal way of doing 1247 essentially what the route suffix does, which is provide more routing 1248 information specific to the destination. The difference is that the 1249 information in the route suffix is picked by the destination, as opposed to 1250 the source being given general information about the topology near the 1251 destination. 1252 One final option is to provide essentially exactly the route suffix 1253 mechanism. As alluded to above in the discussion of fundamental object 1254 classes, it might be necessary, if this optimization is deemed important, to 1255 provide a new object class, that of route suffix. Rather than overload this 1256 function onto any of the existing object classes (and the names for those 1257 objects), it is perhaps best to simply bit the bullet and create the new 1258 object class. 1260 7 Deployment 1262 A great advantage of this architecture is that it can be deployed in 1263 an incremental fashion, and furthermore that it does not require any changes 1264 in hosts for fairly full operation (although minor changes would improve 1265 things somewhat). 1266 The following section is a first crack at defining how the deployment 1267 would work. 1269 7.1 Incremental Deployment in the Routers 1271 The system can fairly obviously be interoperated with the existing 1272 architecture provided host identifiers continue to be allocated along the 1273 existing lines of network numbers. This will allow the system to be deployed 1274 and brought up incrementally in the routers. 1275 In an old-style router, it will still be given lists of network 1276 numbers, and the metric to each. In new-style routers, areas of the network 1277 which are being serviced by old-style routers will be masked by 'transitional' 1278 routers which provide a mapping from the old routing protocol to the new 1279 system. 1280 Of course, as the number of networks mounts, the existing routing 1281 will break down, and render the old-style routers non-functional. By that 1282 time, basically all the main routers should have been converted to use the 1283 new system, and the old routing mechanisms can be turned off. Stub routers 1284 which use default only can continue to operate as before, obviously. Once the 1285 old-style routing mechanisms are turned off, allocation of host identifiers 1286 can proceed in a more flexible and space efficient form. 1287 Obviously, old-style routing could continue to be used once this 1288 happens, but hosts served by old-style routers would probably not be 1289 able to get access to the new hosts, since the new host identifiers would 1290 not contain any topology information the old-style routers could use to 1291 route the traffic. One possible way around this is to have all traffic 1292 to what looks like new network numbers send to a new router which would 1293 perform the mapping in a similar way to the way hosts are supported. 1295 7.2 Incremental Deployment in the Hosts 1297 For the first stage, no changes would be absolutely necessary in the 1298 hosts at all. The host would translate from the name to the host identifier, 1299 and send out an existing packet to the first hop router. 1300 The first hop router would then do the flow setup, using some default 1301 policy attributes. The destination network address would either be looked up 1302 separately, with attendant overhead, or, if the router overheard the name 1303 lookup, it might have cached it. 1305 The issue of network masks and node identifiers needs to be thought 1306 about to make sure that getting from hosts to neighbouring hosts, as well as 1307 first hop routers, continues to work. 1308 Clearly, if node identifiers are assigned without respect to topology, 1309 then the mask and match process can no longer be used to determine whether or 1310 not a given destination is on the local wire. Doing anything else means that 1311 the address space will not be allocated inefficiently, bringing us back to 1312 where we were! However, given the practical difficulties involved in true 1313 random allocation of node identifiers, it may be necessary to allocate in 1314 blocks. 1315 One issue is involved in the translation of node identifiers to local 1316 hardware addresses. Some possibilities exist involving use of ARP, but these 1317 are nasty. For networks which depend on direct mapping from the node 1318 identifier to the network address, it is obviously unavoidable to allocate 1319 chunks of the node identifier space. 1320 Another problem involves making sure that each host understands how to 1321 get to its first hop router for off-network traffic. If hosts exactly follow 1322 the Host Requirement RFC, and are set up with an all ones subnet mask, then 1323 any attempt to send traffic to another host will perforce go to a router. The 1324 default router table will have been filled in via the Router Discovery ICMP 1325 mechanism, and the router's local network address will be resolved as 1326 discussed above. This is inefficient for traffic on the local network, 1327 however; if the all ones mask approach is used, routers will also have to stop 1328 sending Redirects! 1329 If a proposed document on routing in the host is worked on (or 1330 alternatively a revision to the Host Requirement RFC is put in hand), this 1331 topic should be carefully considered to make sure the proposed mechanism will 1332 integrate well into this new approach. 1334 Eventually, the process could be optimized by slight changes in the 1335 host. It would ask for and remember the new type address when it contacted the 1336 name server; if it had special policy requirements (or charge authorizations, 1337 or whatever) it would include these in the packet it sends out, either in the 1338 initial connection packet or in a special communication to the first hop 1339 router, or whichever box is doing the flow setup. 1341 7.3 Upgrading to a Long Node ID 1343 A 32-bit system wide node identifier is clearly unsuitable in the 1344 long run. One possibility for the latter is to make the UID's locally 1345 (perhaps pairwise locally) significant only; however, this is complex, and 1346 loses some of the advantages of having a node idenfitier. 1347 The other main possibility is a new IP packet format with 64 bit 1348 UID's. A new packet format might be desirable anyway, for other reasons. If 1349 the 64 bit UID path is chosen, and the phaseover started before the 32 bit 1350 space is used (so that the UID of any node in the new 64 bit space is simply 1351 the zero extension of its UID in the 32 bit space), there will not be any 1352 cases of new and old style hosts which cannot communicate due to the inabilty 1353 of the old address space to name hosts in the new space, which is the usual 1354 cause of problems in conversions. Once basically all hosts have been 1355 converted to the new format, use of the rest of the identifier space can 1356 proceed. This is probably the preferable path. 1358 A number of ways of interoperating old and new style hosts exist. 1359 The first hop router might automatically convert old-style packets to new 1360 style. The advantage of this is that hosts can throw out the old code; the 1361 disadvantages are the cost of the conversion to and fro when two old-style 1362 hosts are conversing. Another possibility is that hosts might continue to 1363 understand both old and new. 1364 In any case, there are four cases to be considered; old-old, old-new, 1365 new-old, and new-new (the first being the source and the second the 1366 destination of the packets). The tricky one is the new-old, since in any 1367 system something must convert the format; either the source host needs to 1368 find out that the host does not understand new-style (perhaps by trying 1369 a new-style first and seeing if it gets a response) and send an old-style, 1370 or the last-hop router, which needs to know which of its hosts are new and 1371 which are old, needs to do the conversion. A messy problem however it is 1372 sliced! One useful trick is to use spare bits in the headers to record 1373 packets which were sourced in the other format, or hosts which can generate 1374 and understand new format packets, etc. 1376 8 Conclusion 1378 The system proposed above consists of many elements, with the utility 1379 of each created and increased by the interaction with others. The way in which 1380 they were put together was not as straightforward as it now appears. A long 1381 process of revisiting of requirements and tinkering with the design has 1382 resulted in the complete structure now laid out, with each piece dependant on 1383 others and part of a deeply integrated whole. 1384 The system also contains a number of old ideas, put together in a 1385 novel way, together with the addition of some new ideas. In both of these 1386 aspects (the extreme interdependence of a limited set of ideas, developed over 1387 time, together with the resuse of existing good ideas with some augmentation) 1388 it resembles the process which created Unix. [Thompson] 1390 It is believed that the proposed architecture detailed above meets all 1391 the goals outlined in the requirements, and in particular the size, making 1392 possible a extremely long (essentially indefinite) use of the IP architecture. 1393 Finally, it is worth noting again the many instances here in which 1394 the power and flexibility of the architecture are improved by leaving 1395 something out (route generation, data abstraction, etc), rather than by 1396 adding something. 1398 References (Incomplete) 1400 [BBN] ???; "Adding Areas to the ARPANet Routing Algorithm??"; 1401 1982??. 1403 [Chiappa84] J. Noel Chiappa; "??"; 'dev-cgw' mailing list; 1984?. 1405 [Chiappa91] J. Noel Chiappa; "The IP Addressing Issue"; Internet-Draft 1406 Yyyyyy 1991. 1408 [Clark] 1410 [Cohen] Danny Cohen; "On Names, Addresses and Routings"; IEN 23; 1411 January 1978. 1413 [Corbato] Fernado Corbato and Jerome H. Saltzer; "Multics: The 1414 First Seven Years?"; ?? 1416 [Dijkstra] Edgar W. Dijkstra; "A Note on Two Problems in Connection with 1417 Graphs"; Numer. Math, Vol. 1, pp. 269-271; 1959. 1419 [Estrin] Deborah Estrin, Yakov rekhter and Steve Hotz, "A Unified 1420 Approach to Inter-Domain Routing"; In preparation. 1422 [McQuillan] John M. McQuillan, Isaac Richer and Eric C. Rosen; "ARPANet 1423 Routing Algorithm Improvments"; Bolt, Beranek and Newman Report No. 3803; 1424 April 1978. 1426 [Little] M. Little; "Goals and Functional Requirements for Inter- 1427 Autonomous System Routing"; RFC1126; October 1989. 1429 [Moy] John Moy; "The OSPF Protocol"; RFCXXXX; Yyy 1991 1431 [Reed] David Reed; "??"; CSR Group Talk; 1979?? 1433 [SaltzerSR] Jerome H. Saltzer; "Source Routing?"; ?? 1435 [Saltzer82] Jerome H. Saltzer; "On the Naming and Binding of Network 1436 Destinations"; Local Computer Networks, North-Holland Publishing; 1982. 1438 [Shoch] John F. Shoch; "Inter-Network Naming, Addressing and Routing"; 1439 IEN 19; January 1978. 1441 [Thompson] Dennis M. Ritchie and Ken Thompson; "The UNIX Timesharing 1442 System"; CACM, Vol. 17, No. 7, pp. 365-375; July 1974.