Paperman for Nimrod Isidro Castineyra November 15, 1993 1 Introduction This is an attempt to come up with the most basic---read primitive---version of Nimrod I can think of. I wanted to have something we can criticize and use as initial point of reference. It is most certainly full of holes and bad ideas. I am explicitly not claiming that the design decisions taken here would be part of any instantiation of Nimrod. That is, this is not supposed to be a minimal design, only a simple one. I have numbered the stuff below so you can refer easily to whatever irks you. Please start shooting. 2 Basic Principles 1. There are two kinds of basic objects: endpoints and entities. 2. An endpoint is a fate-sharing region---e.g., a process. 3. Each endpoint has an endpoint-ID (eid). Eids are globally unique 4. There are two kind of entities: interfaces and arcs. 5. An interface corresponds to a physical interface. 6. An arc is a configured entity. It can consist of several physical links. 3 Clusters 1. A cluster is defined by its contents and its structure. 2. The contents of a cluster is the set of all entities enveloped by the cluster. 3. Between any two entities in the contents of a cluster there should be a path that connects them, such that this path is entirely within the cluster. 4. A cluster is organized in sub-clusters. The sub-clusters split among themselves the contents of the parent cluster. That is, the union of the contents of the sub-clusters is the contents of the parent cluster; also, the contents of the sub-clusters are non-overlapping. Each sub-cluster has also its own structure. 5. A cluster can be organized in many different ways. Each structure has a name. The different structures of a cluster are numbered. The number of bits necessary to number the structures of a cluster will probably be small---certainly, no more than eight. 6. There exists a top-level universal cluster U. U is unique. One cannot build clusters above or at the same level of it. 7. Other than the universal cluster U, all clusters belong to another cluster. A cluster belongs only to one other cluster: its owner. 8. Given an structure, the set of clusters that are owned by a given cluster are referred to as the members of that cluster. 9. Not every cluster makes practical sense, though. For example, a cluster that uses internally vanilla IP for its routing should not be separated into different clusters because there is no way to enforce nimrod-style routing. Specifically, if A is such a cluster, see figure 1, once a packet has entered A, one cannot actually enforce routing directives that request that a path enter cluster A at the entry point marked and also not touch elements in A2. 4 Naming 1. Clusters have names that are not necessarily globally unique. In a given structure of a cluster, two different clusters owned by the same parent cluster cannot have the same name. In this paper, Here, cluster names are ascii strings. 2. A cluster's locator is given by a dot separated series of pairs (cluster name, structure number). This series starts with the universal cluster U and satisfies that every cluster is a member of the preceding one in the given structure. In figure 2, cluster C is owned by cluster B, which is owned by cluster A, which is owned by U, nobody owns U. A ****************************************************** * A1 * * ******************** A2 * * * * ******************** * * * X destination* * * * ......entry>* * * * * * * * * * * * * ******************** * * * * ******************** * * ^ Boundaries not enforceable* * * ******************************************************* Figure 1: Example of Bad Clustering 3. An end-point can have more than one locator. The number of locators depends on how the enclosing clusters are organized. DNS:TNG provides a mapping service between endpoints and their locators. U,2 / \ / \ / ? A,1 / \ B,1 ? / \ C,1 ? Figure 2: Example of Hierarchy 5A Maps 1. With every structure of a cluster there is associated an internal map. The internal map of a cluster is given by the identities of the clusters that belong to it, and by the connections (arcs) between these. 2. Arcs are uni-directional. A bi-directional connection is represented by two uni-directional arcs, one in each direction. 3. Arcs are identified by giving locators ot its the source and destination clusters. When there are more than one arc between two given clusters, they are distinguished by assigning to them different numbers. 4. Every element of a map---arc or cluster---can have associated with it multiple attributes. This attributes correspond to things like policy constraints, resource availability, available transit qos parameters, etc. 5. When giving the internal map of a cluster, each arc that connects this cluster to another should be shown as terminating in one of the top-level component clusters. 5B Physical Realization 1. The physical realization of an advertised arc can vary from arc to arc. For example, while an advertised arc can consist of a single point-to-point link, it also can represent multiple parallel physical links. Similarly, a single physical transmission link can be represented as multiple arcs. 2. A cluster can represent any physical structure that is deemed useful. There is no undecomposable physical structure---i.e., there is no minimum cluster. A consequence of this, is that interfaces do not appear in maps, or are mentioned by the architecture. Examples of clustering are, (a) A cluster can represent a corporate network. (b) A cluster can represent a 1993 workstation. This cluster can have an internal map. That is, there can be clusters inside a cluster that represents a workstation---for example, a set of processes within the workstation can be enveloped by a cluster boundary This architecture is agonostic about the usefulness of a given clustering of a physical network. 6 Forwarding 1. Forwarding enforcement is done by routers. A requirement is that the forwarding database that these routers have be in agreement with the maps used to generate the packet headers---i.e., if the header of a packet was generated using an out-of-date map, the routers will not be able to implement that header. These databases must also be consistente with the distributed databases of the DNS:TNG. More on this in the section on reconfiguration, see section 9. 2. If a cluster is organized in more than one way, the routers in the cluster will keep a forwarding database for each structure. 3. A packet contains in its header a loose source route. This route could be as loose as including only a locator for the destination eid, or as tight as defining every nimrod entity through which the packet is required to pass. 4. A packet can also include a flow-id which maps into state that has been previously set-up in routers along the way. Packet forwarding when there is a flow-id established is relatively simple: follow the instructions in the routers state. 5. The loose source route in a packet is the only way to indicate policy within a packet. For example, when the loose source route includes only the destination eid, this means the the source does not care how the packet gets there. 6. The path of a packet that contains a loose source route that partially says, say, ...arc1:clusterA.org#:arc2... is restricted to remain inside cluster A.org# while going from arc1 to arc2. Similarly, the path of a packet whose header ends in arc1:clusterA.org#:eid1 is restricted to remain within A when going from arc1 to the entity assigned eid1. 7. A cluster that does not divulge its internal map can work internally any way it pleases as long as it satisfies its external characterization as given in its nimrod map advertisements. This means that the EGP/IGP split effectively is left in place, sort of. 7 Map Distribution 1. A cluster can request the map of any other cluster/structure. This request may or may not be granted. 2. Internal topologies for a cluster are always given in their entirety. There is no way to obtain only part of the map of a cluster. If desired, the internal map of a component cluster can be requested---recursively, ad follia. A given cluster can always refuse to give its internal structure. 3. Maps have an expiration time. It is assumed that all nimrod routing entities have a common accurate clock---for example, by using NTP. This clock is used to determine the validity of maps. 4. A cluster can also ``subscribe'' to the map of a second cluster. This means that the second cluster will send to it topology updates periodically. The update could be as brief as indicating that the time-out of the last full topology received should be extended until an indicated time. 8 Routing 1. Routing generates the right packet header, or the right instructions to set-up state in intermediate routers, given an origin, a destination and a set of policies and qos requirements. 2. A cluster has a top level map of the cluster it is a member of. It also has a map of the top level of every cluster it is a descendent of. For example, a cluster D with locator U,1.A,1.B,1.C,1.D,1, has top level maps of clusters C.1, B,1, A,1, and U,1. Notice that this implies that there is no information hiding ``downwards,'' that is, a cluster cannot hide its top level map from any of its descendants. It also implies that two clusters that are owned by the same cluster have a consistent view of the network ``upwards.'' 3. A cluster might have other maps according to the availability of the information and its requirements. 4. When a packet header contains only a locator for the destination, we have what we know today as hop-by-hop routing. Routing loops are avoided by forwarding the packet in a direction that minimizes the number of hops to the destination. This is called ``vanilla datagram'' forwarding. Consistency of the maps is required for this to work. 9 Reconfiguring The multiple-structure mechanism is used when a cluster needs to reconfigure. Suppose a cluster U,1.A,1.B,1 has become too large and we want to split it. This can be done by creating a new structure for A. In this new structure, U,1.A,2, there are two clusters U,1.A,2.B,1 and U,1.A,2.C,2. The entities previously associated with U,1.A,1.B,1 are split between the two new clusters.