Internet Draft Isidro Castineyra Nimrod January 1995 ?draft-ietf-nimrod-database-00.txt? Expires July 1995 The Nimrod Routing Database Status of this Memo This document is an Internet-Draft. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet- Drafts as reference material or to cite them other than as "work in progress." To learn the current status of any Internet-Draft, please check the "1id-abstracts.txt" listing contained in the Internet- Drafts Shadow Directories on ds.internic.net (US East Coast), nic.nordu.net (Europe), ftp.isi.edu (US West Coast), or munnari.oz.au (Pacific Rim). Abstract This document presents a high level description of Nimrod's Routing database. Internet Draft Nimrod Routing Database January 1995 Contents 1 Introduction 1 2 XDR: External Data Representation Standard 1 3 Database Structure 2 4 Queries 6 5 Security Considerations 7 6 Authors' Addresses 7 i Internet Draft Nimrod Routing Database January 1995 1 Introduction Nimrod is a scalable routing architecture designed to accommodate a continually expanding and diversifying internetwork. First suggested by Chiappa in [1], the Nimrod architecture has undergone revision and refinement through the efforts of the Nimrod working group of the IETF. The architecture is documented in [2]. This document describes Nimrod's routing database. The Nimrod routing database contains the information in which path generation is based. In principle, this information need not be understood by any other module. Each node can be queried to obtain elements of its database. This document specifies the structure of the database and its external representation. It also defines a format for database queries. Section 2 gives a brief introduction to XDR, the language used to define the database. Section 3 describes the structure of the database. Section 4 briefly describes a query format. 2 XDR: External Data Representation Standard We use the formalism of RFC 1014 (see ??) to specify the database and the format of queries and the responses to those queries. XDR is a language to define data formats. It fits into the ISO presentation layer. While XDR itself uses implicit typing, we use it to define a mixed explicit/implicit typing representation. That is, some items are implicitly typed and some are explicitly typed. The explicitly types items include a type coded and a length field. These two fields, type and length, are used to enable the gradual introduction of new kinds of connectivity and policy specifications. In XDR, the representation of all items requires a multiple of four bytes---padding might be necessary to ensure this. The basic types are: 32 bit, two's complement signed integers; 32 bit binary numbers; enumeration types; boolean; hyper integer and unsigned hyper integer (64 bits); IEEE floating-point data; double precission floating point; fixed-length opaque data; variable length opaque data; and strings. The derived types are: fixed-length arrays of elements of the same type; variable-length arrays of elements of the same type; structures; discriminated unions; and void. It is also possible to declare constants. It is also possible to define new identifies for declaring data (typedef). There is also "optional-data" type that is special syntax to declare a kind of union used to declare recursive data types. 1 Internet Draft Nimrod Routing Database January 1995 3 Database Structure The external representation of the database defined here should make possible to interoperate implementations that do not understand the same set of service and policy specifications. An implementation should be able to recognize what elements are understood, and in case that a given element is not understood should handle it in a reasonable manner: for example, it should be able to tell if this element should be forwarded or dropped. This section specifies the format for the basic routing entities: maps, nodes, arcs, and connectivity specifications. /* the elements appear top-down */ /* Nodes */ struct node { locator id; /* the locator of the node */ arc outgoingArcs<>; /* a variable sized array of the outgoing arcs */ ConSpec transitConSpecs<>; /* this item and the next two items are variable size array of connectivity specifications */ ConSpec incomingConSpecs<>; ConSpec outgoingConSpecs<>; map internalMaps<>; /* a variable sized array of maps */ } /* Maps */ struct map { Node nodes<>; /* a variable length array of nodes */ } /* Arcs */ struct arc { int number; /* identifes the arc within the node */ locator head; /* locator of the node at the other end of the arc */ 2 Internet Draft Nimrod Routing Database January 1995 } /* Connectivity Specifications */ struct conSpec { locator id; /* locator of the connectivity specification */ locator inputPrefixes<>; /* variable sized array of locators each of these locators corresponds to a source neighbor */ locator outputPrefixes<>; /* variable sized array of locators each of these locators corresponds to a destination neighbor */ performanceSpec performance<>; /* variable sized array of performance specifications */ policySpec policy<>; /* variable sized array of policy specifications */ } /* Performance Specifications */ /* The format for performance and policy specifications is designed to enable graceful evolution by facilitating the gradual introduction of new types of performance and policy specifications. This is done by giving to performance and policy specifications a common initial portion consisting of two fields: a handling code and a length. The handling code advises about what to do with specifications that an implementation does not yet understand. The length field is required to find the extend of unknown specifications. */ /* The example below assumes an implementation that knows of three different kinds of performance specifications and two different kinds of policy specifications */ /* Performance Specifications */ /* An enumeration type to name the known performance specifications */ enum perfSpecKind { BESTEFFORT = 1, DELAY = 2, BANDWIDTH = 3 3 Internet Draft Nimrod Routing Database January 1995 }; union performanceSpec switch (perfSpecKind kind) { case BESTEFFORT: bestEffortSpec spec; case DELAY: delaySpec spec; case BANDWIDTH: bandwidthSpec; default: unknownPerformance performance; } struct bestEffortSpec { handlingCode code; int length; void; /* no extra information */ } struct delaySpec { handlingCode code; int length; int delay; /* delay measured in ms. */ } struct bandwidthSpec { handlingCode code; int length; int bandwidth; /* bandwidth in kb/s */ } struct unknownPerformance { handlingCode code; opaque contents<>; /* notice that this contains a length field */ } /* Policy Specifications */ /* An enumeration type to name the known policy specifications */ enum policySpecKind 4 Internet Draft Nimrod Routing Database January 1995 { UNRESTRICTED = 1, RESEARCH = 2 }; union policySpec switch (policySpecKind kind) { case UNRESTRICTED: unrestrictedPol policy; case RESEARCH: researchPol policy; default: unknownPolicy policy; } struct unrestrictedPol { handlingCode code; int length; void; /* no further information */ } struct researchPol { handlingCode code; int length; void; /* no further information */ } struct unknownPolicy { handlingCode code; opaque contents<>; } /* Basic Elements */ typedef opaque locator<>; /* the representation of locators if TBD */ typedef opaque handlingCode[4]; /* the representation of the handling codes is TBD */ 5 Internet Draft Nimrod Routing Database January 1995 4 Queries Queries are used to obtain information from node representatives. The query format defined below identify specific data items, and combinations or subsets of data items. Queries are specified by given an XDR declaration of the query itself and of the associated reply. The queries defined below cannot express requests that depend on the values of the elements. For example, request of the style "send all connectivity specifications with property foo" are not supported. enum queryKind { SKELETON = 1, MAP = 2, TOPOLOGY = 3; } union query switch(queryKind kind) { case SKELETON: void; /* no further information required */ case MAP: integer mapNumber; case TOPOLOGY: integer mapNumber; } /* for each query the following is a specification of the expected answer */ union reply switch(queryKind kind) { case SKELETON: nodeSkeleton thisSkeleton; case MAP: map thisMap; case TOPOLOGY: topology thisTopology; } struct partialNode { locator id; arc outgoingArcs<>; 6 Internet Draft Nimrod Routing Database January 1995 } struct topology { PartialNode pNodes<>; } struct nodeSkeleton { arc outgoingArcs<>; ConSpec transitConSpecs<>; ConSpec incomingConSpecs<>; ConSpec outgoingConSpecs<>; int numberMaps; } 5 Security Considerations Security Considerations are not addressed in this document. 6 Authors' Addresses Isidro Castineyra BBN Systems and Technologies 10 Moulton Street Cambridge, MA 02138 Phone: (617) 873-6233 Email: isidro@bbn.com References [1] J. N. Chiappa, "A New IP Routing and Addressing Architecture," IETF Internet Draft, 1991. [2] I. Castineyra, J. N. Chiappa, and M. Steenstrup, "The Nimrod Routing Architecture," Internet Draft, January 1995. 7