Received: from PIZZA.BBN.COM by BBN.COM id aa18848; 4 Jan 95 16:27 EST Received: from pizza by PIZZA.BBN.COM id aa13371; 4 Jan 95 16:08 EST Received: from KARIBA.BBN.COM by PIZZA.BBN.COM id aa13366; 4 Jan 95 16:03 EST To: nimrod-wg@BBN.COM Subject: In praise of arcs with attributes Date: Wed, 04 Jan 95 16:06:25 -0500 From: Isidro Castineyra An arc represents a connection between two nodes. Typically, an arc will map to an actual physical entity. Consider a provider that connects to some of its customers via T1 links and to some via 64 kbits links. In a nimrod map that includes the provider and its clients, I would expect that the provider and each of its clients would be represented by a node. Assume that the provider is internally capable to carry T1 traffic. In this scenario, some pairs of clients can communicate at T1 speeds while others can only communicate at 64 kbs. The nimrod map should be able to specify this. I see three alternatives: 1.- Arcs have attributes. In this case, the speed of the link could be attached as an attribute to the arc(s) between provider and client. The node representing the provider would be characterized by a uniform connectivity specification that says something like "can carry data at T1 rates." 2.- Arcs do not have attributes: Two ways of doing this 2.1 Submerge the properties of the link into the connectivity specification of the node representing the provider. This basically means turning a problem that in case 1 takes O(n) bits to represent (where n is the number of clients) into a problem that requires O(n^2) bits. That is, instead of n arc attributes and a uniform connectivity specification, we would have a specific connectivity specification that, in the worst case, has to specify n(n-1) bandwidths. 2.2 Create sub-nodes to represent the properties of the links. This approach takes takes about the same amount of data to represent the scenario as case 1. However, these subnodes are not visible at "top" level. They can be seen only after the nodes corresponding to provider and clients are opened. Unless the data is represented someway as in 2.1 the "top" level map is useless. I propose we keep attributes in arcs. Comments? Happy New Year, Isidro   Received: from PIZZA.BBN.COM by BBN.COM id aa22995; 4 Jan 95 17:23 EST Received: from pizza by PIZZA.BBN.COM id aa13685; 4 Jan 95 17:02 EST Received: from BBN.COM by PIZZA.BBN.COM id aa13681; 4 Jan 95 16:59 EST Received: from quern.epilogue.com by BBN.COM id aa21169; 4 Jan 95 16:55 EST From: Dave Bridgham Sender: dab@epilogue.com To: nimrod-wg@BBN.COM In-reply-to: Isidro Castineyra's message of Wed, 04 Jan 95 16:06:25 -0500 <9501041622.aa21636@quern.epilogue.com> Subject: In praise of arcs with attributes Date: Wed, 4 Jan 95 16:54:37 -0500 Message-ID: <9501041654.aa21924@quern.epilogue.com> Date: Wed, 04 Jan 95 16:06:25 -0500 From: Isidro Castineyra An arc represents a connection between two nodes. Typically, an arc will map to an actual physical entity. You start from a different point and you'll get a different answer. I don't think that arcs typically map to any physical entity. Some nodes map to physical entities, arcs with those nodes show how the physical entites are plugged together. Some of those physical entities are network links which have attributes like "bandwidth: 56000". I propose we keep attributes in arcs. Comments? The extra complexity of having two types of things with attributes yields no gain. I propose sticking with one thing in the map language, called a meta-node if you must, which has attributes. These meta-nodes have adjacencies which tell how they're plugged together in the real or virtual world. Dave   Received: from PIZZA.BBN.COM by BBN.COM id aa24479; 4 Jan 95 17:46 EST Received: from pizza by PIZZA.BBN.COM id aa13845; 4 Jan 95 17:29 EST Received: from KARIBA.BBN.COM by PIZZA.BBN.COM id aa13841; 4 Jan 95 17:25 EST To: Dave Bridgham cc: nimrod-wg@BBN.COM Subject: Re: In praise of arcs with attributes In-reply-to: Your message of Wed, 04 Jan 95 16:54:37 -0500. <9501041654.aa21924@quern.epilogue.com> Date: Wed, 04 Jan 95 17:27:46 -0500 From: Isidro Castineyra >> >> I propose we keep attributes in arcs. Comments? >> >>The extra complexity of having two types of things with attributes >>yields no gain. I propose sticking with one thing in the map >>language, called a meta-node if you must, which has attributes. These >>meta-nodes have adjacencies which tell how they're plugged together in >>the real or virtual world. >> >> Dave This still leaves you with the problem (from my point of view) that the node plus its arcs do not give you enough information. You have to "open up" the node (or get one of its maps) to be able to do something with it. I would rather be able to use the "top" level map. Isidro   Received: from PIZZA.BBN.COM by BBN.COM id aa25949; 4 Jan 95 18:15 EST Received: from pizza by PIZZA.BBN.COM id aa13957; 4 Jan 95 17:53 EST Received: from BBN.COM by PIZZA.BBN.COM id aa13953; 4 Jan 95 17:50 EST Received: from wd40.ftp.com by BBN.COM id aa24707; 4 Jan 95 17:51 EST Received: from ftp.com by ftp.com ; Wed, 4 Jan 1995 17:51:07 -0500 Received: from mailserv-D.ftp.com by ftp.com ; Wed, 4 Jan 1995 17:51:07 -0500 Received: by mailserv-D.ftp.com (5.0/SMI-SVR4) id AA12771; Wed, 4 Jan 95 17:50:08 EST Date: Wed, 4 Jan 95 17:50:08 EST Message-Id: <9501042250.AA12771@mailserv-D.ftp.com> To: isidro@BBN.COM Subject: Re: In praise of arcs with attributes From: Frank Kastenholz Reply-To: kasten@ftp.com Cc: dab@epilogue.com, nimrod-wg@BBN.COM Content-Length: 1158 > Date: Wed, 04 Jan 95 17:27:46 -0500 > >> I propose we keep attributes in arcs. Comments? > >> > >>The extra complexity of having two types of things with attributes > >>yields no gain. I propose sticking with one thing in the map > >>language, called a meta-node if you must, which has attributes. These > >>meta-nodes have adjacencies which tell how they're plugged together in > >>the real or virtual world. > >> > >> Dave > > This still leaves you with the problem (from my point of view) that > the node plus its arcs do not give you enough information. You have > to "open up" the node (or get one of its maps) to be able to do > something with it. I would rather be able to use the "top" level map. so the reason you want attributes on arcs is as an optimization? what if i don't care about the attribute of the arc? then you'd be passing me these attributes for nothing. -- Frank Kastenholz "The dogmas of the quiet past are inadequate to the stormy present... As our case is new, so we must think anew, and act anew" - A. Lincoln   Received: from PIZZA.BBN.COM by BBN.COM id aa26455; 4 Jan 95 18:25 EST Received: from pizza by PIZZA.BBN.COM id aa14044; 4 Jan 95 18:01 EST Received: from BBN.COM by PIZZA.BBN.COM id aa14040; 4 Jan 95 17:58 EST Received: from quern.epilogue.com by BBN.COM id aa25175; 4 Jan 95 17:59 EST From: Dave Bridgham Sender: dab@epilogue.com To: nimrod-wg@BBN.COM In-reply-to: Isidro Castineyra's message of Wed, 04 Jan 95 17:27:46 -0500 <9501041728.aa22189@quern.epilogue.com> Subject: In praise of arcs with attributes Date: Wed, 4 Jan 95 17:58:50 -0500 Message-ID: <9501041758.aa22362@quern.epilogue.com> Date: Wed, 04 Jan 95 17:27:46 -0500 From: Isidro Castineyra This still leaves you with the problem (from my point of view) that the node plus its arcs do not give you enough information. You have to "open up" the node (or get one of its maps) to be able to do something with it. I would rather be able to use the "top" level map. It seems you're comparing two different things. First you want to get a single node and its arcs and so get "all" information. But then at the end you talk about getting a "top" level map. I think of a map as possibly containing more than one node so I think if you're happy with a map then you're happy with my answer. If you want to get everything with only a single node then my approach won't do it. Dave   Received: from PIZZA.BBN.COM by BBN.COM id aa27111; 4 Jan 95 18:36 EST Received: from pizza by PIZZA.BBN.COM id aa14164; 4 Jan 95 18:18 EST Received: from BBN.COM by PIZZA.BBN.COM id aa14155; 4 Jan 95 18:15 EST Received: from venera.isi.edu by BBN.COM id aa26045; 4 Jan 95 18:17 EST Received: from zed.isi.edu by venera.isi.edu (5.65c/5.61+local-20) id ; Wed, 4 Jan 1995 15:17:43 -0800 From: bmanning@isi.edu Posted-Date: Wed, 4 Jan 1995 15:17:24 -0800 (PST) Message-Id: <199501042317.AA10620@zed.isi.edu> Received: by zed.isi.edu (5.65c/4.0.3-4) id ; Wed, 4 Jan 1995 15:17:24 -0800 Subject: Re: In praise of arcs with attributes To: kasten@ftp.com Date: Wed, 4 Jan 1995 15:17:24 -0800 (PST) Cc: isidro@BBN.COM, dab@epilogue.com, nimrod-wg@BBN.COM In-Reply-To: <9501042250.AA12771@mailserv-D.ftp.com> from "Frank Kastenholz" at Jan 4, 95 05:50:08 pm X-Mailer: ELM [version 2.4 PL24] Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Content-Length: 1227 > > >> I propose we keep attributes in arcs. Comments? > > >> > > >>The extra complexity of having two types of things with attributes > > >>yields no gain. I propose sticking with one thing in the map > > >>language, called a meta-node if you must, which has attributes. These > > >>meta-nodes have adjacencies which tell how they're plugged together in > > >>the real or virtual world. > > >> > > >> Dave > > > > This still leaves you with the problem (from my point of view) that > > the node plus its arcs do not give you enough information. You have > > to "open up" the node (or get one of its maps) to be able to do > > something with it. I would rather be able to use the "top" level map. > > so the reason you want attributes on arcs is as an optimization? > > what if i don't care about the attribute of the arc? then you'd be > passing me these attributes for nothing. > I was quietly in favor of attributes and still am. You may not care wrt attributes, but I may want them. In this case, can you let everyone know that you don't care so that we don't send them to you. Those that want them can then talk amongst ourselves.... :) -- --bill   Received: from PIZZA.BBN.COM by BBN.COM id aa15577; 5 Jan 95 10:11 EST Received: from pizza by PIZZA.BBN.COM id aa17845; 5 Jan 95 9:52 EST Received: from KARIBA.BBN.COM by PIZZA.BBN.COM id aa17841; 5 Jan 95 9:44 EST To: kasten@ftp.com cc: dab@epilogue.com, nimrod-wg@BBN.COM Subject: Re: In praise of arcs with attributes In-reply-to: Your message of Wed, 04 Jan 95 17:50:08 -0500. <9501042250.AA12771@mailserv-D.ftp.com> Date: Thu, 05 Jan 95 09:47:25 -0500 From: Isidro Castineyra >> > This still leaves you with the problem (from my point of view) that >> > the node plus its arcs do not give you enough information. You have >> > to "open up" the node (or get one of its maps) to be able to do >> > something with it. I would rather be able to use the "top" level map. >> >>so the reason you want attributes on arcs is as an optimization? >> >>what if i don't care about the attribute of the arc? then you'd be >>passing me these attributes for nothing. I imagine that that argument could be applied to all attributes: "what if I don't care about the attributes in a node, would you still be passing them to me?" Presumably, the attribute is in the arc because it is deemed important by the originator (bandwidth, etc.). If there is not a slot in the arc data structure, it is going to be put somewhere else (the connectivity specification of the node, for example). My belief is that it is much simpler to put it in the arc. I suppose that anything can be seen as an optimization, that is not the question. The question is whether this particular one gets us enough bang for the bits. Isidro   Received: from PIZZA.BBN.COM by BBN.COM id aa07857; 5 Jan 95 15:20 EST Received: from pizza by PIZZA.BBN.COM id aa19568; 5 Jan 95 14:58 EST Received: from TTL.BBN.COM by PIZZA.BBN.COM id aa19564; 5 Jan 95 14:53 EST To: Dave Bridgham cc: nimrod-wg@BBN.COM Subject: Re: In praise of arcs with attributes In-reply-to: Your message of Wed, 04 Jan 95 16:54:37 -0500. <9501041654.aa21924@quern.epilogue.com> Date: Thu, 05 Jan 95 14:52:48 -0500 From: Ram Ramanathan > From: Dave Bridgham > Sender: dab@epilogue.com > To: nimrod-wg@BBN.COM > In-reply-to: Isidro Castineyra's message of Wed, 04 Jan 95 16:06:25 -0500 <9501041622.aa21636@quern.epilogue.com> > Subject: In praise of arcs with attributes > Date: Wed, 4 Jan 95 16:54:37 -0500 > Message-ID: <9501041654.aa21924@quern.epilogue.com> > > I propose we keep attributes in arcs. Comments? > > The extra complexity of having two types of things with attributes > yields no gain. I propose sticking with one thing in the map > language, called a meta-node if you must, which has attributes. These > meta-nodes have adjacencies which tell how they're plugged together in > the real or virtual world. > > Dave The gain, in my opinion, comes in the following: 1) Clarity of representation (or its "naturalness" if you may). I believe that a representation should be as natural as possible. That is, one must be able to see a strong and obvious relation between the representation and actuality. This is especially important to network maintenance people who would probably not want to do complex conversions/mappings between meta or fake nodes and their realities. While the notion of "clarity" and "natural" is admittedly subjective, I will attempt to explain my reason for why I think attributes on arcs are more natural. We cluster real or abstract objects and call these clusters nodes. A node represents a bunch of stuff that are "related" in some way (e.g., have the same management authority). Now that we have all these nodes, we need to say something about which node can communicate with which other node. So we introduce a new representational atom - the Arc. Why do we introduce a new atom and not use something we have before, namely the node? Because it would be cumbersome. Because we want to represent a fundamentally different kind of relation, we sought a different atom. Okay, so we have arcs. But now, we want to not only say that you can get from node A to node B, but also that you can get there in this manner or that manner. Since it is the "getting from here to there" that we want to qualify, attributes on arcs seem natural. Having a fake node in place of a link (now a *node* represents the "getting from here to there") is to me an unnecessary deviation from natural-ness. Basically, what I am trying to say is: o Arcs represent the relation of getting from one node to another. o Attributes qualify this relation by giving additional information about getting from one node to another. o Therefore attributes on arcs are appropriate. o Overloading the representational semantics of a node to include representing the connectivity relation sacrifices conceptual clarity. Of course, arcs are appropriate on nodes too, but in a different context, namely, how to "get from here to there" *across* a node. Thus, we need attributes on both nodes and arcs. Sure we can get away with attributeless arcs, but then so could we without arcs at all ! (See Nimrod archive for note entitled "Kissing Amoebas"). 2) Flexibility. If representation A allows me to represent some information in more ways than represnetation B, I in general prefer A to B. Attributes on arcs subsume attributeless arcs. You can represent meta-nodes/ attributeless arcs using an attributes-on-arcs based representation but not vice-versa. The question of whether a more flexible representation compromises simplicity is important, but in this particular case (see below) I don't think it does. 3) Space complexity. If you absorb arc attributes into nodes, you pay O(n^2) in worstcase. If you create a node in the middle of an arc and plug all of the arcs attributes into this node, you pay one new node and one new arc extra for every old arc, which is again O(n^2) in the worst case. The latter however has a smaller "constant" factor, only vanilla nodes and arcs and therefore not significant in absolute terms. Regarding extra implementation complexity, I think it will be very minor, if at all. This is based on my experience with implementing IDPR, where we have a similar situation. I made this point in an earlier posting (dated 15 Dec 1994). Basically, I argued that if we changed the search method to adapt to the problem at hand instead of converting the problem at hand to a representation traditionally used for searching (such as chaining together connectivity specs as an explicit graph), things look much simpler. Cheers, -Ram.   Received: from PIZZA.BBN.COM by BBN.COM id aa14646; 6 Jan 95 16:42 EST Received: from pizza by PIZZA.BBN.COM id aa28327; 6 Jan 95 16:20 EST Received: from BBN.COM by PIZZA.BBN.COM id aa28323; 6 Jan 95 16:14 EST Received: from GAAK.BBN.COM by BBN.COM id aa12197; 6 Jan 95 16:10 EST Date: Fri, 6 Jan 1995 16:10:28 EST Message-ID: To: nimrod-wg@BBN.COM In-reply-to: message from Isidro Castineyra on Wed, 04 Jan 95 16:06:25 -0500 Subject: Re: In praise of arcs with attributes From: "Michael A. Patton" Reply-To: nimrod-wg@BBN.COM Date: Wed, 04 Jan 95 16:06:25 -0500 From: Isidro Castineyra As a real network operator, I saw several things in this message which struck me as non-typical of real network operations... An arc represents a connection between two nodes. Typically, an arc will map to an actual physical entity. Not the way I envision most operators thinking about their networks. Consider a provider that connects to some of its customers via T1 links and to some via 64 kbits links. In a nimrod map that includes the provider and its clients, I would expect that the provider and each of its clients would be represented by a node. As that provider I would expect to make the top level map have one node for the provider backbone and a node for each "customer", with arcs between them as you said. But, the way a provider thinks about this is that there is a speed associated with each _customer_, that makes the "customer" node the more natural place to record the information (to me as an operator). Thus, I wouldn't need or even use attributes on arcs. When compared to real world operations, I think your analogy is the wrong one. Which is what leads to your erroneous analysis later... On the other hand, I see this level of argument as irrelevant. What we need to decide now is what types of data structures to define and pass around INTERNAL to NIMROD. How users (including network operators) view this information is a user interface issue and can easily pick a different one of the paradigms than the one used for the actual routing. I happen to expect that the nodes with attributes, arcs without is the way most operators will want to view things, but see below for my argument about why the internal structure should be this way. I find it useful that I see things the same way at both levels, but I don't think that how the user interface views the world should have (much) affect on our choice of representation internal to the routing layer. 2.- Arcs do not have attributes: Two ways of doing this Actually three, the two you mention and the one I think is most natural. One node for the provider backbone with T1 connectivity, and one node for each "customer" with a speed as appropriate, and arcs between them with no attributes... I propose we keep attributes in arcs. Comments? The more I think about the attributes on arcs question, the more opposed I get to the idea of attributes on arcs IN THE BASIC MAP. I propose that the map representation internal to NIMROD have nodes with attributes (no connectivity specs), and one of those attributes is the arcs. No other component is necessary, and any added component adds uneeded complication. This simplicity of representation is why I feel so strongly about no attributes on arcs, Note that if different people want to view the world in different ways, that's quite possible and merely a GUI design issue. All of these schemes can be mapped to one another.. I want the routing to only have one basic thing to think about. And that thing is nodes with attributes, where one of the attributes is the list of arcs. As a network operator, my intuitive feel is for arcs to represent merely the existance of reachability, the nodes are the right place for all the baggage. In particular, as an operator, I may well want to extend the paradigm to layers below that at which the routing ever goes (which I can suitably hide, one of the great ideas of NIMROD) because it lets me track details of my network that the routing doesn't care about (modems, multiplexors, circuits, etc.) in the same paradigm and with the same tools I'm already using to manage the routing... -MAP   Received: from PIZZA.BBN.COM by BBN.COM id aa14962; 6 Jan 95 16:47 EST Received: from pizza by PIZZA.BBN.COM id aa28403; 6 Jan 95 16:26 EST Received: from BBN.COM by PIZZA.BBN.COM id aa28399; 6 Jan 95 16:23 EST Received: from GAAK.BBN.COM by BBN.COM id aa13085; 6 Jan 95 16:22 EST Date: Fri, 6 Jan 1995 16:22:16 EST Message-ID: To: nimrod-wg@BBN.COM In-reply-to: message from Ram Ramanathan on Thu, 05 Jan 95 14:52:48 -0500 Subject: Re: In praise of arcs with attributes From: "Michael A. Patton" Reply-To: nimrod-wg@BBN.COM Date: Thu, 05 Jan 95 14:52:48 -0500 From: Ram Ramanathan 1) Clarity of representation (or its "naturalness" if you may). I believe that a representation should be as natural as possible. That is, one must be able to see a strong and obvious relation between the representation and actuality. This is especially important to network maintenance people who would probably not want to do complex conversions/mappings between meta or fake nodes and their realities. I agree completely with that, and that's one of the reasons that contributes to my desire to have nodes with attributes and simple arcs (actually not represented separately at all, but rather as attributes of the node from which they spring). I feel this to be much more natural to today's network operators. ... Since it is the "getting from here to there" that we want to qualify, attributes on arcs seem natural. Having a fake node in place of a link (now a *node* represents the "getting from here to there") is to me an unnecessary deviation from natural-ness. I don't see that. There are two cases, a provider and its customers, in which case (see previous note) the provider thinks about the 64K customers and the T1 customers, and so their natural representation has these attributes on the "customer", which has to be a node (because it's expandable). The second case is internal to a given net, where you might think using arcs for circuits would be expected, but it's my experience that these are often thought of more as we think of nodes (in fact, there's one diagram we often use thinking about the DSI that has boxes for the circuits and lines (arcs) for the routers). Thus I don't see the attributes on arcs facility as aiding real network operations in any way, and, in fact, possibly confusing things more because they then have the added burden of an extra type to need to map from representation to reality. -MAP   Received: from PIZZA.BBN.COM by BBN.COM id aa25899; 6 Jan 95 20:13 EST Received: from pizza by PIZZA.BBN.COM id aa00331; 6 Jan 95 19:58 EST Received: from BBN.COM by PIZZA.BBN.COM id aa00327; 6 Jan 95 19:56 EST Received: from GAAK.BBN.COM by BBN.COM id aa24868; 6 Jan 95 19:52 EST Date: Fri, 6 Jan 1995 19:51:57 EST Message-ID: To: nimrod-wg@BBN.COM In-reply-to: message from Ram Ramanathan on Thu, 05 Jan 95 14:52:48 -0500 Subject: Re: In praise of arcs with attributes From: "Michael A. Patton" Reply-To: nimrod-wg@BBN.COM Date: Thu, 05 Jan 95 14:52:48 -0500 From: Ram Ramanathan Oops, I found something else in Ram's message that I'd like to object to, but in a different vein... 3) Space complexity. ... If you create a node in the middle of an arc and plug all of the arcs attributes into this node, you pay one new node and one new arc extra for every old arc, This is an invalid analysis, you are replacing one complex arc with a node of EXACTLY the same complexity, and eliminating all the complexity in the arcs where you didn't need it. I believe overall the nodes with attributes, one of which is the arcs, is overall a WIN in this regard, rather than a loss as you describe. Your analysis assumes no (or negligible) cost for arcs, but in fact your scheme has the same cost for arcs as for nodes, while the attribute-less arcs of the other scheme are the only lightweight objects I can see (and one of the reasons I like that paradigm). -MAP   Received: from PIZZA.BBN.COM by BBN.COM id aa00602; 7 Jan 95 4:01 EST Received: from pizza by PIZZA.BBN.COM id aa02349; 7 Jan 95 3:39 EST Received: from BBN.COM by PIZZA.BBN.COM id aa02345; 7 Jan 95 3:37 EST Received: from ginger.lcs.mit.edu by BBN.COM id aa25208; 7 Jan 95 3:38 EST Received: by ginger.lcs.mit.edu id AA26657; Sat, 7 Jan 95 03:38:17 -0500 Date: Sat, 7 Jan 95 03:38:17 -0500 From: Noel Chiappa Message-Id: <9501070838.AA26657@ginger.lcs.mit.edu> To: nimrod-wg@BBN.COM Subject: Re: In praise of arcs with attributes Cc: jnc@ginger.lcs.mit.edu This whole argument over whether to have arcs with attributes or not, reminds me of an argument as to whether an electron is a particle or a wave. The answer, of course, is that it's both, and you don't need to have the argument. Similarly here. If the fundamental components are i) metanodes with attributes, and ii) adjacencies among metanodes, we get to have all of: - nodes with attributes (including complex connectivity specs, if we want them, which is a separate debate) - arcs without attributes - arcs with attributes - multi-point arcs along with anything else I can think of. All are simply different ways of looking at metanodes with adjacencies. Thus, if you feel that a representation of a physical topology which uses arcs with attributes is best, go right ahead. If you feel instead that one which uses arcs without attributes (in which T1 links become nodes, etc) is best, you can just go on and do that instead. Moreover, there is *zero* overhead, in either space or computational cost, to "building" multi-point arcs, arcs with attributes, etc, out of metanodes and adjacencies. If you think about the underlying information, and how you would represent it in bits, etc, an arc with attributes turns out to take all the same bits as a metanode with attributes and adjacencies, and it's the same cost to process. This is very important, since it means that we can allow all the different ways of modeling physical topologies with zero cost advantage over picking one or the other, and making it our basic representation. (This indicates to me that we have found the best *possible* scheme, but let's not get into that.) Maybe I'm missing something, but I have a rock-solid feeling that there is simply no question at all that this is the way to go. Did I miss something? Noel   Received: from PIZZA.BBN.COM by BBN.COM id aa03886; 7 Jan 95 4:15 EST Received: from pizza by PIZZA.BBN.COM id aa02430; 7 Jan 95 3:54 EST Received: from BBN.COM by PIZZA.BBN.COM id aa02426; 7 Jan 95 3:52 EST Received: from ginger.lcs.mit.edu by BBN.COM id aa27817; 7 Jan 95 3:49 EST Received: by ginger.lcs.mit.edu id AA26710; Sat, 7 Jan 95 03:49:50 -0500 Date: Sat, 7 Jan 95 03:49:50 -0500 From: Noel Chiappa Message-Id: <9501070849.AA26710@ginger.lcs.mit.edu> To: nimrod-wg@BBN.COM Subject: Map desitgn philosophy Cc: jnc@ginger.lcs.mit.edu One thing I think we should keep in the front of our minds here is that the primary client of the map is going to be *path selection* (by many orders of magnitude). This means that we ought to make the most important factor in all design decisions with respect to the map be how to reduce the computational cost of using the map in the path selection process. Also, Martha has made a useful distinction between two meanings of the word "complexity", a distinction we ought to keep track of. The first is computational complexity, or resource usage in memory/processing/transmission, the usual O(NlogN) type stuff, i.e. fairly quantifiable. The second is the more abstract and hard to quantify one, which is how complicated the mechanisms are; she uses the term "complication" for this sense. Complication is bad, for many reasons I won't belabor here, not just the fact that it makes things harder to understand for the average person. Other hard-to-quantify, but important, things like flexibility, robustness, etc are subtly related to complication as well. Anway, complication is something I want to keep down as much as possible, so anyplace we see a chance to get rid of something, my bias is to do so. Noel   Received: from PIZZA.BBN.COM by BBN.COM id aa08821; 7 Jan 95 4:36 EST Received: from pizza by PIZZA.BBN.COM id aa02535; 7 Jan 95 4:16 EST Received: from BBN.COM by PIZZA.BBN.COM id aa02531; 7 Jan 95 4:15 EST Received: from ginger.lcs.mit.edu by BBN.COM id aa01889; 7 Jan 95 4:07 EST Received: by ginger.lcs.mit.edu id AA26731; Sat, 7 Jan 95 04:07:05 -0500 Date: Sat, 7 Jan 95 04:07:05 -0500 From: Noel Chiappa Message-Id: <9501070907.AA26731@ginger.lcs.mit.edu> To: nimrod-wg@BBN.COM Subject: Open map questions Cc: jnc@ginger.lcs.mit.edu In this message, I'm going to use the term "arc" to mean something that can have attributes, a locator (since you can have more than one arc with attributes between any two nodes), etc: i.e. a thing one would represent with a meta-nodes and some adjacencies. As far as I can see, there are really only three open questions. 1) Are all the properties of a node/arc (e.g. its adjacencies, locator, etc) attributes of a meta-node like any other attribute (albeit perhaps mandatory), or are some of the properties of a meta-node "built-in" to the meta-node? I.e., when you look at the actual data structure, is *every* piece of data associated with a node carried in some sort of tagged field, or are some carried in "fixed" fields with pre-defined semantics? This is not a big deal, since either way will work, but I think there is probably some slight efficiency to having some very basic properties (e.g. adjacencies, locator, etc) be built-in; that way, common operations (such as tracing down adjacencies) can be optimized. Since they are so basic, every piece of code will have to understand them anyway, so making them attributes really only produces some descriptive simplicity, at a potential cost in run- time efficiency. 2) Do we need to provide disjoint attributes sets on a given node? We could do this with replicated "parallel" nodes, one for each disjoint attribute set, but (unlike the case with metanodes and arcs with attributes), there *is* a space cost to doing this (since connectivity, and other shared attribute information, would have to be replicated). This does raise a question in that it might only provide for one level of "parenthesization": e.g. node 1 has attributes A and B and either (P and Q) or (X and Y). To allow for more complex nestings, e.g. A and B, and either (P, Q) or (P, R) or (X, Y), you'd need something more complex, e.g. (A, B, ((P, (Q | R)) | (X, Y))). (Of course, if we use S-expressions, this would be really easy!) In addition the separate nodes would have to have separate locators (although we'd need some way of distinguishing between the disjoint attribute sets anywqay, so maybe this isn't a big deal). This is a tough one: if we add it, it has to be a basic capability (i.e. it can't be one more kind of attribute), but it's not clear which way to jump. 3) Do we need to have complex connectivity specifications? This is too long to properly analyse here, but Martha has made a good case to me that we need to do these, that we need something intermediate between uniform connectivity nodes (i.e. any given attribute applies between all adjacency pairs), and abstract maps. Very briefly, you *can* provide a mapping from complex connectivity specs to equivalent abstact maps, but (unlike the case with metanodes and arcs with attributes), there *is* a space and computational cost to doing so for some common scenarios. Examples include services available on almost all adjacency pairs, except for a few; this is less expensive to represent as an exception list. If we do have complex connectivity specs, they could and should be optional attributes, so that if we decide down the road they aren't needed, it's not a big upheaval to drop them. This does mean that this question is probably less critical to get right than the first two. (They should also be able to nest other attributes, so you can give any other defined attribute complex availability; hmm, the more I think about it, the more S-expressions are the way to go for representing attributes! :-) Noel   Received: from PIZZA.BBN.COM by BBN.COM id aa12205; 7 Jan 95 4:51 EST Received: from pizza by PIZZA.BBN.COM id aa02620; 7 Jan 95 4:33 EST Received: from BBN.COM by PIZZA.BBN.COM id aa02616; 7 Jan 95 4:32 EST Received: from ginger.lcs.mit.edu by BBN.COM id aa07657; 7 Jan 95 4:31 EST Received: by ginger.lcs.mit.edu id AA26841; Sat, 7 Jan 95 04:31:28 -0500 Date: Sat, 7 Jan 95 04:31:28 -0500 From: Noel Chiappa Message-Id: <9501070931.AA26841@ginger.lcs.mit.edu> To: nimrod-wg@BBN.COM Subject: One place to simplify Cc: jnc@ginger.lcs.mit.edu The example that first brought this "complication" thing up is hop-by-hop reliable transmission of flow-setup requests. The end-end principle says you don't do anything on a local basis which you have to do on an end-end basis anyway, *unless* there's some efficiency or other optimization goal you're trying to meet. Since we currently don't reliably forward TCP SYN packets, but everything works fine, I see no reason to handle flow-setups reliably. For the client to resend a flow-setup if you don't get back an ack is the way to go anyway, since there are potential failure modes which mean you *have* to have an end-end retransmission *anyway*. (E.g. a node crashes after sending an ack, but before forwarding the setup on. Saying you have to send the request on before you can ack it doesn't help, since if you crash after that, and the request is lost, you're *still* screwed.) I know that we're probably going to have an RTP protocol lying around anyway, so it's not *much* extra complication to do it, and you might as well. I disagree; I still see this as unnecessary complication. At the very least, each node has to take the time to ensure the reliable transmission of the setup request. Sure, it has to tweak state anyway to set up the flow, so the extra state needed for the reliable setup is minor. However, a reliable setup means it also has to process an ack from its downstream neighbour (which would be in addition to the end-end ack back to the requestor that the flow has been completed on an end-end basis, since you can't return *that* until the setup has gotten all the way to the far end OK), in addition to sending one to its upstream neighbour, etc. Some links may have poor reliability, and need enhancement if they are to function well, but this applies to *all* packets, not just flow-setup packets. A TCP connection which has to deal with a high drop rate on one link it traverses is not going to work very well; the end-end round-trip delays inevitably mean poor response to lost packets. (I thought for a while that maybe we could include fields in the flow- setup which nodes could use locally, optionally, to do reliable setup on a hop-by-hop basis, but now I'm not even sure of that, since such a link probably needs to have reliabilty enhancement at a level below flow setup, for the reason mentioned immediately above.) The hop-by-hop acknowledgement of flow setups is extra complication that is, as far as I can tell, of no value. Unless someone can show a good use, I think we should drop it. Noel PS: We could get *really* radical, and not have reliable map database element transmission, since things will not break massively if an update is missed, but I think that may be a bit too radical! :-)   Received: from PIZZA.BBN.COM by BBN.COM id aa10581; 7 Jan 95 12:33 EST Received: from pizza by PIZZA.BBN.COM id aa04244; 7 Jan 95 12:16 EST Received: from TTL.BBN.COM by PIZZA.BBN.COM id aa04240; 7 Jan 95 12:14 EST To: nimrod-wg@BBN.COM Subject: Re: In praise of arcs with attributes In-reply-to: Your message of Fri, 06 Jan 95 16:22:16 -0500. Date: Sat, 07 Jan 95 12:16:57 -0500 From: Ram Ramanathan > From: "Michael A. Patton" > Reply-To: nimrod-wg@BBN.COM > > Date: Thu, 05 Jan 95 14:52:48 -0500 > From: Ram Ramanathan > > ... Since it is the "getting from here to there" that we > want to qualify, attributes on arcs seem natural. Having a fake node > in place of a link (now a *node* represents the "getting from here to > there") is to me an unnecessary deviation from natural-ness. > > I don't see that. There are two cases, a provider and its customers, > in which case (see previous note) the provider thinks about the 64K > customers and the T1 customers, and so their natural representation > has these attributes on the "customer", which has to be a node > (because it's expandable). The second case is internal to a given > net, where you might think using arcs for circuits would be expected, > but it's my experience that these are often thought of more as we > think of nodes (in fact, there's one diagram we often use thinking > about the DSI that has boxes for the circuits and lines (arcs) for the > routers). Thus I don't see the attributes on arcs facility as aiding > real network operations in any way, and, in fact, possibly confusing > things more because they then have the added burden of an extra type > to need to map from representation to reality. > > -MAP Sure, there are situations (such as the one you mention above) in which it makes more sense to use attributes on nodes. However, are all situations such that it would be unnatural to put attributes on arcs? Consider for instance a provider FarNet who has two customers Ada and Barney. Ada and Barney are interconnected in two ways - one a microwave link and another a T1, with attributes quite different for each. Then I would find it natural to make a node F for FarNet, put nodes A and B inside F and put two arcs between A and B, one for the microwave link with microwave-esque attributes, and one for the T1 with T1-esque attributes. To me this seems more natural than representing the links as nodes. I would argue that as long as there are a significant number of situations where attributes on arcs would be appropriate, we cannot and should not preclude that representational option. For, one can always NOT put attributes on arcs in a representation that allows attributes on arcs, but CANNOT put attributes on arcs when it is not allowed. In other words, allowing attributes on arcs permits you to do the things the way you want and also to do things the way I want; attributeless arcs permits you to do the things the way you want but not the way I want. As the Internet develops, connectivity increases and becomes more and more complex, who knows what kind of situations we might want to represent? Would it then be prudent to constrain ourselves with too few representational options? Cheers, -Ram.   Received: from PIZZA.BBN.COM by BBN.COM id aa11438; 7 Jan 95 13:10 EST Received: from pizza by PIZZA.BBN.COM id aa04402; 7 Jan 95 12:56 EST Received: from TTL.BBN.COM by PIZZA.BBN.COM id aa04398; 7 Jan 95 12:55 EST To: nimrod-wg@BBN.COM Subject: Re: In praise of arcs with attributes In-reply-to: Your message of Fri, 06 Jan 95 19:51:57 -0500. Date: Sat, 07 Jan 95 12:54:23 -0500 From: Ram Ramanathan > Subject: Re: In praise of arcs with attributes > From: "Michael A. Patton" > Reply-To: nimrod-wg@BBN.COM > > Date: Thu, 05 Jan 95 14:52:48 -0500 > From: Ram Ramanathan > > Oops, I found something else in Ram's message that I'd like to object > to, but in a different vein... > > 3) Space complexity. ... If you create a node in the middle of an > arc and plug all of the arcs attributes into this node, you pay > one new node and one new arc extra for every old arc, > > This is an invalid analysis, you are replacing one complex arc with a > node of EXACTLY the same complexity, and eliminating all the > complexity in the arcs where you didn't need it. I believe overall > the nodes with attributes, one of which is the arcs, is overall a WIN > in this regard, rather than a loss as you describe. Your analysis > assumes no (or negligible) cost for arcs, but in fact your scheme has > the same cost for arcs as for nodes, while the attribute-less arcs of > the other scheme are the only lightweight objects I can see (and one > of the reasons I like that paradigm). > > -MAP > Mike, Either you have misunderstood my statement in (3) or have been too hasty in proclaiming my analysis as invalid. In any case, I restate my rather straightforward point in some more detail below. With attributes on arcs, you have the following data-structural equivalent for an arbitrary arc : O------------------O (attrs on arc) With attributeless arcs, you have (item 2.2 of Isidro's original posting) the data-structural equivalent : O--------O---------O | V (attrs. on node) Thus, you replace every arc with two arcs and one node, which is one arc and one node extra. In the worst case, this is O(n^2) extra nodes and O(n^2) extra arcs, since in the worst case, number of arcs in a map is O(n^2) (n being the no. of nodes in the map). Note that I did not say O(n^2) extra *attributes*, only the raw nodes and arcs. Attributes aren't going to go away, they occupy the same amount of space in either representation. Also, as I said in my earlier message, this gain not much and therefore of academic interest only : "..If you create a node in the middle of an arc and plug all of the arcs attributes into this node, you pay one new node and one new arc extra for every old arc, which is again O(n^2) in the worst case. The latter however has a smaller "constant" factor, only vanilla nodes and arcs and therefore not significant in absolute terms." Now, you seem to be talking about having arcs itself as attributes of nodes. This is different from the scheme that involves placing nodes explicitly in the middle. Your scheme seems much closer to what I was thinking (adjacency is an implicit attribute of nodes in my mind) and will have the SAME space complexity as what I was thinking. Cheers, -Ram.   Received: from PIZZA.BBN.COM by BBN.COM id aa21601; 8 Jan 95 10:02 EST Received: from pizza by PIZZA.BBN.COM id aa09131; 8 Jan 95 9:48 EST Received: from BBN.COM by PIZZA.BBN.COM id aa09127; 8 Jan 95 9:45 EST Received: from ginger.lcs.mit.edu by BBN.COM id aa20979; 8 Jan 95 9:36 EST Received: by ginger.lcs.mit.edu id AA28681; Sun, 8 Jan 95 09:36:41 -0500 Date: Sun, 8 Jan 95 09:36:41 -0500 From: Noel Chiappa Message-Id: <9501081436.AA28681@ginger.lcs.mit.edu> To: nimrod-wg@BBN.COM Subject: Re: Map desitgn philosophy Cc: jnc@ginger.lcs.mit.edu From: jnc@ginger.lcs.mit.edu (Noel Chiappa) the primary client of the map is going to be *path selection* (by many orders of magnitude). This means that we ought to make the most important factor in all design decisions with respect to the map be how to reduce the computational cost of using the map in the path selection process. Now that I think about it, this isn't quite accurate. Someone said that this whole issue of what to put in the map is a process of balancing costs at the originator of the map, versus costs at the user of the map. So, if representation A is the most efficient for calculating routes, and representation B is what's natural for the sender to keep, it's better for the sender to do the transform *once*, and send out A, rather than have each receiver do it. It strikes me that a similar line of reasoning can be applied to the point above. Yes, the internal representation used by the entity which is doing path selections ought to be one which is optimized to the task of doing path selection. However, if the incoming representation isn't the one most suited to the task of path selection, it still makes sense to do the transform at the receiver, since the costs of doing so can be amortized over many path selections. Even if the cost is fairly high (which I somehow doubt), if we can get 10K path selections out of each map, the total cost of the transform is split 10K ways, into neglibility. So, if we don't get the transmitted representation we send around quite, it's not the end of the world. In fact, different path selection algorithms (and remember, we'll be coming up with new ones for a long time to come) might in fact come to prefer some other representation from what currently seems optimal. So perhaps there is no such thing as the "right" representation from the point of view of path selection, and it's futile to try and find the perfect one at this point. Also, viewing the overall system costs, perhaps it makes sense to optimize the transmitted representation for transmission and incoming parsing, realizing that that operation will be performed many times; the internal representation will thus be left up to the receiver, which can do what seems best for it's particular circumstances. I happen to believe that the underlying math is such that there probably is an optimal representation (as far as path selection goes, for reasons that have to do with the basic costs of examining objects in a graph to see if they match the attributes you need), and we ought to spend some time thinking about what it is, but I think I've shown that it's not the end of the world if we don't get it spot on. Noel   Received: from PIZZA.BBN.COM by BBN.COM id aa17401; 9 Jan 95 10:54 EST Received: from pizza by PIZZA.BBN.COM id aa15903; 9 Jan 95 10:28 EST Received: from TTL.BBN.COM by PIZZA.BBN.COM id aa15899; 9 Jan 95 10:25 EST To: nimrod-wg@BBN.COM Subject: Re: In praise of arcs with attributes In-reply-to: Your message of Sat, 07 Jan 95 03:38:17 -0500. <9501070838.AA26657@ginger.lcs.mit.edu> Date: Mon, 09 Jan 95 10:26:27 -0500 From: Ram Ramanathan > Date: Sat, 7 Jan 95 03:38:17 -0500 > From: Noel Chiappa > Message-Id: <9501070838.AA26657@ginger.lcs.mit.edu> > To: nimrod-wg@BBN.COM > Subject: Re: In praise of arcs with attributes > Cc: jnc@ginger.lcs.mit.edu > > This whole argument over whether to have arcs with attributes or not, > reminds me of an argument as to whether an electron is a particle or a wave. > The answer, of course, is that it's both, and you don't need to have the > argument. > Similarly here. If the fundamental components are i) metanodes with > attributes, and ii) adjacencies among metanodes, we get to have all of: > > - nodes with attributes (including complex connectivity specs, if we want > them, which is a separate debate) > - arcs without attributes > - arcs with attributes > - multi-point arcs An "adjacency" and an "arc" to me are the same things - both specify a relation, namely connectivity, between two nodes. I guess the question is whether we can have the facility to associate attributes with adjacencies or not. I believe that in most representations of a map, including this facility will have negligible or no complexity or complication overhead. A common data structure that is used in representing non-dense simple (no attributes at all) graphs is an adjacency list (see any basic algorithms book). I believe that extending this to include attributes will be simple, and would result in something like the following (sorry for getting down to C, but it is easiest to make a point this way) : struct _meta_node { struct _locator my_loc; struct _adjacencies *my_neighbors; < other fields eg. connectivity specs > } struct _adjacencies { struct _meta_node *neighboring_node; struct _attributes adj_attributes; /* attributes of this adjacency */ struct _adjacencies *next_adjacency; /* continuing the linked list of < other fields > adjacent nodes*/ } It seems to me that even if we didn't associate attributes with adjacencies, you would have, in an adjacency list based representation, something similar to above, minus the adj_attributes field. So all this reduces to the presence or absence of a field (could be null even if present) in a structure. I say let us have it in there. There may be alternative data structures for which the presence or absence of attributes on adjacencies is a pain in the neck, but I can't see it. > Maybe I'm missing something, but I have a rock-solid feeling that > there is simply no question at all that this is the way to go. Did I miss > something? > I gather from your statement above that your unified metanode-adjacency is basically the same as what I have detailed? Because, otherwise you cannot have attributes on arcs as you have said above (bullet no. 3). If so count me in as another rock-solid feeler! Cheers, -Ram.   Received: from PIZZA.BBN.COM by BBN.COM id aa00144; 9 Jan 95 13:43 EST Received: from pizza by PIZZA.BBN.COM id aa17137; 9 Jan 95 13:20 EST Received: from BBN.COM by PIZZA.BBN.COM id aa17133; 9 Jan 95 13:15 EST Received: from wd40.ftp.com by BBN.COM id aa20657; 9 Jan 95 11:32 EST Received: from ftp.com by ftp.com ; Mon, 9 Jan 1995 11:32:42 -0500 Received: from mailserv-D.ftp.com by ftp.com ; Mon, 9 Jan 1995 11:32:42 -0500 Received: by mailserv-D.ftp.com (5.0/SMI-SVR4) id AA22701; Mon, 9 Jan 95 11:31:37 EST Date: Mon, 9 Jan 95 11:31:37 EST Message-Id: <9501091631.AA22701@mailserv-D.ftp.com> To: jnc@ginger.lcs.mit.edu Subject: Re: In praise of arcs with attributes From: Frank Kastenholz Reply-To: kasten@ftp.com Cc: nimrod-wg@BBN.COM, jnc@ginger.lcs.mit.edu Content-Length: 797 > Similarly here. If the fundamental components are i) metanodes with > attributes, and ii) adjacencies among metanodes, we get to have all of... Noel, forgive me if I'm confused... We would build arcs, nodes, multi-point-arcs, etc, all out of metanodes and adjacencies, yes? The protocols, datastructures, etc, would, in the abstract, build and represent the nodes and arcs out of these two building blocks. If so, the nodes/arcs/attributes discussion would simply descend to 'should adjacencies have attributes or not?' It's really the same thing, just at a 'lower' level. -- Frank Kastenholz "The dogmas of the quiet past are inadequate to the stormy present... As our case is new, so we must think anew, and act anew" - A. Lincoln   Received: from PIZZA.BBN.COM by BBN.COM id aa00386; 9 Jan 95 13:46 EST Received: from pizza by PIZZA.BBN.COM id aa17148; 9 Jan 95 13:20 EST Received: from BBN.COM by PIZZA.BBN.COM id ab17133; 9 Jan 95 13:15 EST Received: from wd40.ftp.com by BBN.COM id aa20669; 9 Jan 95 11:32 EST Received: from ftp.com by ftp.com ; Mon, 9 Jan 1995 11:32:55 -0500 Received: from mailserv-D.ftp.com by ftp.com ; Mon, 9 Jan 1995 11:32:55 -0500 Received: by mailserv-D.ftp.com (5.0/SMI-SVR4) id AA22709; Mon, 9 Jan 95 11:31:51 EST Date: Mon, 9 Jan 95 11:31:51 EST Message-Id: <9501091631.AA22709@mailserv-D.ftp.com> To: jnc@ginger.lcs.mit.edu Subject: Re: Open map questions From: Frank Kastenholz Reply-To: kasten@ftp.com Cc: nimrod-wg@BBN.COM, jnc@ginger.lcs.mit.edu Content-Length: 1740 > > In this message, I'm going to use the term "arc" to mean something > that can have attributes, a locator (since you can have more than one arc with > attributes between any two nodes), etc: i.e. a thing one would represent with > a meta-nodes and some adjacencies. > As far as I can see, there are really only three open questions. > > 1) Are all the properties of a node/arc (e.g. its adjacencies, >locator, etc) attributes of a meta-node like any other attribute (albeit >perhaps mandatory), or are some of the properties of a meta-node "built-in" to >the meta-node? I.e., when you look at the actual data structure, is *every* >piece of data associated with a node carried in some sort of tagged field, or >are some carried in "fixed" fields with pre-defined semantics? If my terminology is right... Does a metanode that represents a node have adjacencies? Or does the metanode that represents an arc have adjacencies? It seems to me that 1 and only 1 can have adjacencies (I assume that you can not have: ). > 2) Do we need to provide disjoint attributes sets on a given node? We > could do this with replicated "parallel" nodes, one for each disjoint > attribute set, but (unlike the case with metanodes and arcs with attributes), > there *is* a space cost to doing this (since connectivity, and other shared > attribute information, would have to be replicated). There is also a cost in the time required to do path selection, no? -- Frank Kastenholz "The dogmas of the quiet past are inadequate to the stormy present... As our case is new, so we must think anew, and act anew" - A. Lincoln   Received: from PIZZA.BBN.COM by BBN.COM id aa00479; 9 Jan 95 13:47 EST Received: from pizza by PIZZA.BBN.COM id aa17143; 9 Jan 95 13:20 EST Received: from BBN.COM by PIZZA.BBN.COM id aa17139; 9 Jan 95 13:15 EST Received: from wd40.ftp.com by BBN.COM id aa20664; 9 Jan 95 11:32 EST Received: from ftp.com by ftp.com ; Mon, 9 Jan 1995 11:32:47 -0500 Received: from mailserv-D.ftp.com by ftp.com ; Mon, 9 Jan 1995 11:32:47 -0500 Received: by mailserv-D.ftp.com (5.0/SMI-SVR4) id AA22704; Mon, 9 Jan 95 11:31:41 EST Date: Mon, 9 Jan 95 11:31:41 EST Message-Id: <9501091631.AA22704@mailserv-D.ftp.com> To: jnc@ginger.lcs.mit.edu Subject: Re: One place to simplify From: Frank Kastenholz Reply-To: kasten@ftp.com Cc: nimrod-wg@BBN.COM, jnc@ginger.lcs.mit.edu Content-Length: 1876 > The hop-by-hop acknowledgement of flow setups is extra complication > that is, as far as I can tell, of no value. Unless someone can show a good > use, I think we should drop it. Is there an end-to-end ack? Or do I send the setup, start sending data, and hope it works? :-) Suppose that a source has determined the path to the destination to go through Nimrod-Nodes A-B-C-D-E. That is, the path looks like: Source->A->B->C->D->E->Destination Now I want to set up the flow so I send the flow-setup request. The request fails at NimrodNode D for some reasone (perhaps it is some transient condition that was not present when I calculated the path, but now is there...). After some amount of time, the Source will timeout the request and do some sort of recovery. If the source just resends the request, it may well fail again (infinite loop here...) Or the source can then recalculate the path, etc. However, if D can send a 'flow-request nak' then the recovery can proceed quicker (Source would know pretty much immediately that D can't honor the request any more -- rather than timeout, etc, etc etc) AND the source would know where to start looking for an alternate path. So, having an explicit NAK is probably a good overall system optimization. This way the source can differentiate between a rejected reservation and a lost reservation. >PS: We could get *really* radical, and not have reliable map database element >transmission, since things will not break massively if an update is missed, >but I think that may be a bit too radical! :-) Sounds a lot like the network video stuff I was working on. I don't think it's radical at all. -- Frank Kastenholz "The dogmas of the quiet past are inadequate to the stormy present... As our case is new, so we must think anew, and act anew" - A. Lincoln   Received: from PIZZA.BBN.COM by BBN.COM id aa02138; 9 Jan 95 14:10 EST Received: from pizza by PIZZA.BBN.COM id aa17423; 9 Jan 95 13:41 EST Received: from BBN.COM by PIZZA.BBN.COM id aa17419; 9 Jan 95 13:39 EST Received: from ginger.lcs.mit.edu by BBN.COM id aa24156; 9 Jan 95 12:23 EST Received: by ginger.lcs.mit.edu id AA00975; Mon, 9 Jan 95 12:23:45 -0500 Date: Mon, 9 Jan 95 12:23:45 -0500 From: Noel Chiappa Message-Id: <9501091723.AA00975@ginger.lcs.mit.edu> To: nimrod-wg@BBN.COM, ramanath@BBN.COM Subject: Re: In praise of arcs with attributes Cc: jnc@ginger.lcs.mit.edu From: Ram Ramanathan An "adjacency" and an "arc" to me are the same things - both specify a relation, namely connectivity, between two nodes. Martha started me using adjacency when she said that it was terminology for an arc that could not have attributes. (Let me be intellectually honest here for a second and admit that metanodes and adjacencies are exactly the same, really, as nodes and arcs without attributes. I only use the different terminology so that people find it easier to think of building a multi-point arc, or an arc with attributes, out of nodes.) I guess the question is whether we can have the facility to associate attributes with adjacencies or not. I believe that in most representations of a map, including this facility will have negligible or no complexity or complication overhead. What I'm saying is that an arc with attributes is really no different from a node with attributes, when you look at the bits you need to have to describe the object, so we might as well make them the same thing. sorry for getting down to C, but it is easiest to make a point this way No, I understand; my only hesitation is that I want to make sure people keep clear in their mind that this doesn't mean they have to use *this* particular representation *internally*; keeping clear in our minds that we can use something different internally from what the protocol uses is going to be key. I believe that extending this to include attributes will be simple, and would result in something like the following: [I'm going to change "adjacency" in these to "arc", and "metanode" to "node", to keep consistent with the terminology I'm using, where adjacancies do not have any attributes.] struct _node { struct _locator my_loc; struct _arcs *my_neighbors; < other fields eg. connectivity specs > } struct _arcs { struct _node *neighboring_node; struct _attributes arc_attributes; struct _arcs *next_arc; < other fields > } I think there are several bugs here. First, if we can have multiple arcs between a given pair of nodes (with different attributes), we need to be able to distinguish them. The easiest way to do this is to give them locators. So, arcs have to have locators too, just like nodes. Second, your assumption that the attributes are a single structure. I think we'll want the basically the same flexibility for the attributes of *arcs* which have attributes, as we do for *nodes* which have attributes. (There's no reason to have separate attribute languages, since many, especially policy terms, etc, will be shared.) So, that part of it will all be the same in both nodes and arcs too. So, we'd wind up with nodes, which are this structure which can have locators, complex attributes, etc, and a list of arcs, and arcs, which look the same, except they don't have a list of anything, just a pointer to a node. (I'm going to ignore the details of how you actually build the list of arcs, since I'd actually do it differently, for reasons I'll explain in a separate message, since it's very low level grup.) In other words, we'd have: struct _node { struct _locator my_loc; struct _attributes *my_attributes; struct _arcs **my_arcs; } struct _arcs { struct _locator my_loc; struct _attributes *my_attributes; struct _node *neighboring_node; } (Also, you can't have multi-point arcs this way, since you've only got a single node pointer per arc.) At this point, things start to look realllll similar, and I say, "bingo, what if I do this": struct mnode { struct locator *mn_loc; struct attributes *mn_attributes; struct mnode **mn_adjs; } (where the last thing is simply a pointer to an array of pointers to metanodes, for the low-level issues that don't matter here that I talked about), and out of *that* object I can build things that look like both your nodes and arcs above, *and* get multi-point arcs for free to boot. It seems to me that even if we didn't associate attributes with adjacencies, you would have, in an adjacency list based representation, something similar to above, minus the adj_attributes field. No, because I don't have *any* data *at all* *in* an adjacency, which allows me to get away with much simpler representation of adjacencies; i.e. an array of pointers. So all this reduces to the presence or absence of a field (could be null even if present) in a structure. I say let us have it in there. I look at your scheme and I see a *less* flexible scheme (no multi-point arcs), one which is more complex, and I just don't think it is better. Multi-point arcs are going to be important for efficiently expressing N^2 connectivity among a group of nodes, and although you can provide something that looks like multi-point arcs, by making a node out of the multi-point arc, you're basically doing what I did: ditch the arc object for that application, and take over the node object to do it. There may be alternative data structures for which the presence or absence of attributes on adjacencies is a pain in the neck, but I can't see it. There is. It's called an array. An array of pointers is a lot simpler than an array of structures. I gather from your statement above that your unified metanode-adjacency is basically the same as what I have detailed? Because, otherwise you cannot have attributes on arcs as you have said above (bullet no. 3). No, it's not the same: you've got two kinds of objects, I only have one. I provide something that looks, feels, walks and smells like attributes on arcs, but I do it with a metanode that I label an "arc". If you look at some actual examples, my representation is superior. Think about a nice, simple one: two nodes A and B connected with an bidirectional link X, with some attributes. In my scheme, each of A, B and X gets a metanode object : A points to X, B points to X, and X points to A and B. In your scheme, you need two node objects, but also two arc objects, since each of your arc objects can only point to one node (i.e. no bidirectional arcs). (You also may have to replicate your attributes, depending on how you store attributes). Can you find any example for which your representation is superior? I can't off hand think of one. Noel   Received: from PIZZA.BBN.COM by BBN.COM id aa02723; 9 Jan 95 14:16 EST Received: from pizza by PIZZA.BBN.COM id aa17561; 9 Jan 95 13:51 EST Received: from BBN.COM by PIZZA.BBN.COM id aa17554; 9 Jan 95 13:48 EST Received: from ginger.lcs.mit.edu by BBN.COM id aa26946; 9 Jan 95 13:00 EST Received: by ginger.lcs.mit.edu id AA01141; Mon, 9 Jan 95 13:00:17 -0500 Date: Mon, 9 Jan 95 13:00:17 -0500 From: Noel Chiappa Message-Id: <9501091800.AA01141@ginger.lcs.mit.edu> To: nimrod-wg@BBN.COM, ramanath@BBN.COM Subject: Re: In praise of arcs with attributes Cc: jnc@ginger.lcs.mit.edu From: Ram Ramanathan A common data structure that is used in representing non-dense simple (no attributes at all) graphs is an adjacency list Again, this is a *local* representational issue to some degree, but it's worth chatting about, since it will have some small bearing on the representation we use for shipping this stuff around. One way to store the list of adjacencies is as single variable length array of pointers to mnodes, which is pointed to by a field in the mnode object. I.e., in C, something like: struct mnode { locator *n_loc; int n_numadjs; mnode **n_adjs; } There's no reason to use a linked list of things, each one of which points to a single mnode, since you don't expect to modify the size of the array a lot; in the rare instances when you do have to modify it, you just free the old one and allocate a new one. (If the general heap allocator is too slow, then use a special allocator which keeps small arrays around.) Another possibility is simply appending the array of pointers directly to the fixed fields of the mnode object, like this: struct mnode { locator *n_loc; int n_numadjs; mnode *n_adjs[]; } but the problem now is that if you want to increase the number of adjacencies, you'd have to allocate a new mnode object, which means you'd have to update all the mnodes which point to this one (if we only have mnode pointers for adjacencies, more below), and to do that you either keep pointers to every mnode which points to this one (ugh), or sweep the database to find them. If you keep the adjacancies in the form of locators, not mnodes directly, then you can avoid this problem of allocating a new object for a mnode. The intelligent way to do this is keep the locators in the form of pointers to the objects representing the actual, variable length, locators (assuming a given locator is stored in only one place); the locator objects would include a pointer back to the actual mnode object. I.e., it would look like this: struct locator { mnode *l_mnode; int l_loclen; byte *l_locator; } struct mnode { locator *n_loc; int n_numadjs; locator *n_adjs[]; } To run down an adjacency, you pick up the locator pointer, and run down it to pick up the mnode pointer. Then, if you need to reallocate an mnode's object, you just bash the pointer in the locator object (which you always have a pointer to in the mnode object). This scheme would probably be very slightly more inefficient for using the map to find paths; you'd have to deference each adjacency twice, separately. In the scheme above, there are still two levels of reference, but you'd be able to retain the pointer of the first level (the pointer to the array) in a register. (Actaully, if you load the address of n_adjs field into a register, to deal with it as an array, you're up to three levels, i.e. an extra instruction/memory reference.) "All problems in computer science can be solved by another layer of abstraction" - Lampson :-). An additional question which comes to mind here has to do with the representation of maps in the protocol. If we allow adjacencies to be expressed in the form of pointers to mnodes (effectively; we'd probably use small integers or something like that in actuality - packet offsets wouldn't work since what do you do if a map won't fit into a single packet), we could have mnodes which did not have locators. It's not clear if this is useful. Actually, now that I think about it, those small integers, added to the locator of the area, *are* locators. Da-hup. So all mnodes do have locators. Noel   Received: from PIZZA.BBN.COM by BBN.COM id aa02858; 9 Jan 95 14:19 EST Received: from pizza by PIZZA.BBN.COM id aa17617; 9 Jan 95 13:53 EST Received: from BBN.COM by PIZZA.BBN.COM id aa17613; 9 Jan 95 13:50 EST Received: from ginger.lcs.mit.edu by BBN.COM id aa27363; 9 Jan 95 13:06 EST Received: by ginger.lcs.mit.edu id AA01190; Mon, 9 Jan 95 13:05:56 -0500 Date: Mon, 9 Jan 95 13:05:56 -0500 From: Noel Chiappa Message-Id: <9501091805.AA01190@ginger.lcs.mit.edu> To: kasten@ftp.com, nimrod-wg@BBN.COM Subject: Re: In praise of arcs with attributes Cc: jnc@ginger.lcs.mit.edu From: kasten@ftp.com (Frank Kastenholz) We would build arcs, nodes, multi-point-arcs, etc, all out of metanodes and adjacencies, yes? The protocols, datastructures, etc, would, in the abstract, build and represent the nodes and arcs out of these two building blocks. If so, the nodes/arcs/attributes discussion would simply descend to 'should adjacencies have attributes or not?' It's really the same thing, just at a 'lower' level. No, by definition, since adjacencies *do not* have attributes, locators, or *any other property*. They simply reflect unidirectional connectivity. I think my long note to Ram of this morning explains in detail the rather handwavy statement that I made some time before, that if you look at the actual details of i) nodes with attributes, and ii) arcs with attributes, they look pretty much the same. I.e. when you look at the actual bits you need to represent the information for those two things, you wind up with things that are so similar you might as well just have one thing. What I'm calling "adjacencies" Ram doesn't really have a name for; they just appear as pointers in his structures. Noel   Received: from PIZZA.BBN.COM by BBN.COM id aa04093; 9 Jan 95 14:35 EST Received: from pizza by PIZZA.BBN.COM id aa17768; 9 Jan 95 14:00 EST Received: from BBN.COM by PIZZA.BBN.COM id aa17764; 9 Jan 95 13:57 EST Received: from ginger.lcs.mit.edu by BBN.COM id aa28490; 9 Jan 95 13:22 EST Received: by ginger.lcs.mit.edu id AA01256; Mon, 9 Jan 95 13:22:32 -0500 Date: Mon, 9 Jan 95 13:22:32 -0500 From: Noel Chiappa Message-Id: <9501091822.AA01256@ginger.lcs.mit.edu> To: kasten@ftp.com, nimrod-wg@BBN.COM Subject: Re: One place to simplify Cc: jnc@ginger.lcs.mit.edu From: kasten@ftp.com (Frank Kastenholz) > The hop-by-hop acknowledgement of flow setups is extra complication Is there an end-to-end ack? Or do I send the setup, start sending data, and hope it works? :-) Hmm, my original note spoke of one, but now that you mention it, we don't really need it. I think an optional end-end ack on the flow setup (requested by the sender setting a bit in the flow setup request) may be a useful idea, but let me think about it. A mandatory ack is not necessary, and I think, in practise won't be used much (if it's optional). We can get by without it, but you do have to have a nack for setup failure, to let you know where the failure occurred, and why (e.g. no resources for requested resource reservation, or any one of a zillion other things) so you know how to try again with something which is more likely to succeed. Without an informative nack, you're fishing in the dark on failures. Anyway, if you don't hear a nack, try doing a transport connection setup, and see if you get an transport ack. Actually, we probably want to piggyback the transport connection setup on the flow setup, to avoid a round-trip time of delay on transport connection setup. That way, the transport ack *is* the flow setup ack. This is actually rather nice; we get rid of the overhead of sending back a separate flow setup ack (or the complication of trying to piggyback the transport setup ack on the flow setup ack), and in most cases it's info we don't need anyway. Good idea! However, if D can send a 'flow-request nak' then the recovery can proceed quicker (Source would know pretty much immediately that D can't honor the request any more -- rather than timeout, etc, etc etc) AND the source would know where to start looking for an alternate path. Yes, exackly. (Sorry, couldn't resist! :-) So, having an explicit NAK is probably a good overall system optimization. This way the source can differentiate between a rejected reservation and a lost reservation. It's more than an optimization, it's absolutely necessary. Lots of things I want to do in other internetwork layer subsystems (e.g. resource allocation, congestion control) just won't work without the information in that feedback path. > We could get *really* radical, and not have reliable map database element > transmission, since things will not break massively if an update is > missed, but I think that may be a bit too radical! Sounds a lot like the network video stuff I was working on. I don't think it's radical at all. Yeah, but video is a little different from maps for the routing. Still, let's all think about it for a while; it may not be too crazy after all. Noel   Received: from PIZZA.BBN.COM by BBN.COM id aa04098; 9 Jan 95 14:35 EST Received: from pizza by PIZZA.BBN.COM id aa17907; 9 Jan 95 14:11 EST Received: from BBN.COM by PIZZA.BBN.COM id aa17901; 9 Jan 95 14:08 EST Received: from ginger.lcs.mit.edu by BBN.COM id aa29499; 9 Jan 95 13:34 EST Received: by ginger.lcs.mit.edu id AA01307; Mon, 9 Jan 95 13:34:45 -0500 Date: Mon, 9 Jan 95 13:34:45 -0500 From: Noel Chiappa Message-Id: <9501091834.AA01307@ginger.lcs.mit.edu> To: kasten@ftp.com, nimrod-wg@BBN.COM Subject: Re: Open map questions Cc: jnc@ginger.lcs.mit.edu From: kasten@ftp.com (Frank Kastenholz) If my terminology is right... Does a metanode that represents a node have adjacencies? Or does the metanode that represents an arc have adjacencies? It seems to me that 1 and only 1 can have adjacencies Both can have adjacencies, but only to another metanode. Remeber, adjacencies only show unidirectional connectivity from one metanode, to another. Without an adjacency, there's no connectivity. (I assume .. you can not have: ). Right. You've also asked a *separate*, more interesting, question, which is whether we allow an mnode representing an "arc" to attach to another mnode representing an "arc". Since to me the whole thing is rather arbitrary semantic sugar to allow people to draw pictures they like, I don't really care whether this is legal or not. An associated question is whether we allow an mnode representing a router to be directly connected to an mnode representing another router (or, one representing a network to be directly connected to one representing another router). If you will recall, I said I'd like to have attributes which mark mnodes as either networks, routers, or areas (or perhaps "abstract object" is a better termo to use in some cases), and have rules which don't allow cases like these. This would be more for finding configuration and other errors as much as anything, though, not from some fundamental need. (These attributes would help in drawing maps directly from Nimrod databases, too. We could have all sorts of attributes like this: who to call for field service when a node is down, what kind of box it is, what its physical location is, etc. All the kind of stuff the O&M guys keep in a separate database now could all be centralized here, and you wouldn't have a problem with skew between the two databases.) > Do we need to provide disjoint attributes sets on a given node? We > could do this with replicated "parallel" nodes There is also a cost in the time required to do path selection, no? Shouldn't be, really. Again, when you think about the bits you'd need to represent that information, it's pretty much a wash in terms of the computational cost, unless I'm missing something. Noel   Received: from PIZZA.BBN.COM by BBN.COM id aa08053; 9 Jan 95 15:25 EST Received: from pizza by PIZZA.BBN.COM id aa18468; 9 Jan 95 15:00 EST Received: from BBN.COM by PIZZA.BBN.COM id aa18464; 9 Jan 95 14:57 EST Received: from wd40.ftp.com by BBN.COM id aa04787; 9 Jan 95 14:44 EST Received: from ftp.com by ftp.com ; Mon, 9 Jan 1995 14:44:19 -0500 Received: from mailserv-D.ftp.com by ftp.com ; Mon, 9 Jan 1995 14:44:19 -0500 Received: by mailserv-D.ftp.com (5.0/SMI-SVR4) id AA26624; Mon, 9 Jan 95 14:43:17 EST Date: Mon, 9 Jan 95 14:43:17 EST Message-Id: <9501091943.AA26624@mailserv-D.ftp.com> To: jnc@ginger.lcs.mit.edu Subject: Re: One place to simplify From: Frank Kastenholz Reply-To: kasten@ftp.com Cc: kasten@ftp.com, nimrod-wg@BBN.COM, jnc@ginger.lcs.mit.edu Content-Length: 2408 > From: kasten@ftp.com (Frank Kastenholz) > > > The hop-by-hop acknowledgement of flow setups is extra complication > > Is there an end-to-end ack? Or do I send the setup, start sending data, > and hope it works? :-) > >Hmm, my original note spoke of one, but now that you mention it, we don't >really need it. I think an optional end-end ack on the flow setup (requested >by the sender setting a bit in the flow setup request) may be a useful idea, >but let me think about it. A mandatory ack is not necessary, and I think, in >practise won't be used much (if it's optional). To me it seems that there are three possible outcomes of sending a flow setup 1. The request got lost in the network 2. The request can't be honored at some point in the network 3. Everything is just fine. I certainly want to be able to differentiate numbers 1 and 2 from number 3. If the request fails for some reason then I want to be able to detect it and re-do it (performing whatever failure processing is needed). And then results 1 and 2 indicate different problems in the network and have different recovery modes. As long as I can differentiate the two then recovery is vastly helped. If there are two outcomes that I can not differentiate between then I have to make a guess as to which the real outcome is, and that could lead to a worse overall system performance. >Anyway, if you don't hear a nack, try doing a transport connection setup, When? I'd rather get a positive e2e ack that it worked, then I can start sending data as soon as possible, which might be very important for any sort of real-time application _or_ if a flow costs me money just to for keeping the flow set up. Also, it might be that flow-setups are 2-step. The setup packet would be a provisional setup, with the flow not being truly 'committed' until the e2e ack comes back. >and >see if you get an transport ack. Actually, we probably want to piggyback the >transport connection setup on the flow setup, to avoid a round-trip time of >delay on transport connection setup. That way, the transport ack *is* the flow >setup ack. What happens for applications that use an ack-less transport -- such as RTP/video/audio? -- Frank Kastenholz "The dogmas of the quiet past are inadequate to the stormy present... As our case is new, so we must think anew, and act anew" - A. Lincoln   Received: from PIZZA.BBN.COM by BBN.COM id aa12580; 9 Jan 95 16:14 EST Received: from pizza by PIZZA.BBN.COM id aa18928; 9 Jan 95 15:53 EST Received: from TTL.BBN.COM by PIZZA.BBN.COM id aa18921; 9 Jan 95 15:51 EST To: Noel Chiappa cc: nimrod-wg@BBN.COM Subject: Re: In praise of arcs with attributes In-reply-to: Your message of Mon, 09 Jan 95 12:23:45 -0500. <9501091723.AA00975@ginger.lcs.mit.edu> Date: Mon, 09 Jan 95 15:46:51 -0500 From: Ram Ramanathan Noel, First of all, my intention in using a C structure was only to clarify a point and I did not mean for anyone to take it literally. Therefore, I only gave the barest minimum needed to make my point. In any case, I wonder whether a design decision should be made depending on whether or not we implementation considerations like by using pointers to pointer arrays or other such powerful constructs? Now that we have begun chatting anyway about C constructs, here is the way to extend simply the structure I gave to have multi-point arcs etc. > > [I'm going to change "adjacency" in these to "arc", and "metanode" to "node", > to keep consistent with the terminology I'm using, where adjacancies do not > have any attributes.] > > struct _node { struct _locator my_loc; > struct _arcs *my_neighbors; > < other fields eg. connectivity specs > > } > > struct _arcs { struct _node *neighboring_node; > struct _attributes arc_attributes; > struct _arcs *next_arc; > < other fields > > } > > I think there are several bugs here. First, if we can have multiple arcs > between a given pair of nodes (with different attributes), we need to be able > to distinguish them. The easiest way to do this is to give them locators. So, > arcs have to have locators too, just like nodes. Second, your assumption that Yes, arcs have locators too, that was one of the things covered in . > I look at your scheme and I see a *less* flexible scheme (no multi-point > arcs), one which is more complex, and I just don't think it is better. > The obvious simple extension is for an arc to point to more than one node. The first field in struct _arcs would be a linked list of neighboring node or an array if you wish as struct _node **neighboring_node. > If you look at some actual examples, my representation is superior. Think > about a nice, simple one: two nodes A and B connected with an bidirectional > link X, with some attributes. In my scheme, each of A, B and X gets a metanode > object : A points to X, B points to X, and X points to A and B. In your > scheme, you need two node objects, but also two arc objects, since each of > your arc objects can only point to one node (i.e. no bidirectional arcs). > (You also may have to replicate your attributes, depending on how you store > attributes). > The only reason your representation is "superior" (assuming superior == space complexity, which may not necessarily be true) is because in my structure before, I did not worry about optimization for arc symmetry. There are several ways of doing that - one is to keep a bit (1 = bidirected, 0 = unidirected). Then, I'd have only 3 node objects - 2 node objects and 1 bidirectional arc object with *one* set of attributes. Further, this representation explicitly precludes one from connecting arcs to arcs which would be allowed if everything were (meta)nodes. Implementations would be less error prone and errors much easier to trace. I am now convinced that the difference between the two schemes is too small to be of paramount importance - esp. in comparison to the importance of moving forward. Cheers, -Ram.   Received: from PIZZA.BBN.COM by BBN.COM id aa12945; 9 Jan 95 16:20 EST Received: from pizza by PIZZA.BBN.COM id aa19046; 9 Jan 95 16:02 EST Received: from BBN.COM by PIZZA.BBN.COM id aa19042; 9 Jan 95 16:00 EST Received: from bridge2.NSD.3Com.COM by BBN.COM id aa11163; 9 Jan 95 15:51 EST Received: from remmel.NSD.3Com.COM by bridge2.NSD.3Com.COM with SMTP id AA12639 (5.65c/IDA-1.4.4nsd for ); Mon, 9 Jan 1995 12:51:11 -0800 Received: from localhost.NSD.3Com.COM by remmel.NSD.3Com.COM with SMTP id AA24078 (5.65c/IDA-1.4.4-910725 for ); Mon, 9 Jan 1995 12:51:08 -0800 Message-Id: <199501092051.AA24078@remmel.NSD.3Com.COM> To: nimrod-wg@BBN.COM Subject: Re: One place to simplify In-Reply-To: Your message of "Mon, 09 Jan 1995 13:22:32 EST." <9501091822.AA01256@ginger.lcs.mit.edu> Cc: tracym@nsd.3com.com Date: Mon, 09 Jan 1995 12:51:08 -0800 From: Tracy Mallory > > The hop-by-hop acknowledgement of flow setups is extra complication > > Is there an end-to-end ack? Or do I send the setup, start sending data, > and hope it works? :-) > > Hmm, my original note spoke of one, but now that you mention it, we don't > really need it. I think an optional end-end ack on the flow setup (requested > by the sender setting a bit in the flow setup request) may be a useful idea, > but let me think about it. A mandatory ack is not necessary, and I think, in > practise won't be used much (if it's optional). On the original topic of hop-by-hop acks: Do you have a model that failed flow setups are cheap/free? There may be regions where leaving stale flow state from failed setups is undesirable, for which a hop-by-hop ack/nak would be useful. Perhaps this is an attribute (inherited by the path from its constituent nodes (arcs? ;-)) that explicit acks/naks are required on certain paths? Regards, Tracy [Apologies if I've missed some basic assumptions/mechanisms in this area, in which case 'nevermind'. I'm lurking in fits and starts days.]   Received: from PIZZA.BBN.COM by BBN.COM id aa13282; 9 Jan 95 16:24 EST Received: from pizza by PIZZA.BBN.COM id aa19098; 9 Jan 95 16:05 EST Received: from KARIBA.BBN.COM by PIZZA.BBN.COM id aa19094; 9 Jan 95 16:03 EST To: nimrod-wg@BBN.COM Subject: We don't need no steenking arcs! Date: Mon, 09 Jan 95 16:06:11 -0500 From: Isidro Castineyra The majority opinion seems to be that arcs should have no attributes. Let's call arcs without attributes adjacencies. If adjacencies exist as independent entities, they are used to hold a pair of locators: the locator of the origin node and the locator of the destination node (or tail and head, if you want). Instead of this, each node could have as one of its attributes a list/set of neighbor node locators. (This is even more attractive if we are not going to give locators to arcs.) Of course, we could still draw little arrows and call them arcs. But do we need the formal concept of arc in the architecture and as a formal element in the database? (Wearing editor/co-chair hat) Unless I hear a good reason, I am going to obliterate/expunge/eliminate the "a" word from the architecure and database documents. Isidro PS. Of course, this is the "Kissing Amoebae" note all over again.   Received: from PIZZA.BBN.COM by BBN.COM id aa24571; 9 Jan 95 19:48 EST Received: from pizza by PIZZA.BBN.COM id aa20515; 9 Jan 95 19:30 EST Received: from BBN.COM by PIZZA.BBN.COM id aa20511; 9 Jan 95 19:25 EST Received: from GAAK.BBN.COM by BBN.COM id aa23668; 9 Jan 95 19:24 EST Date: Mon, 9 Jan 1995 19:24:27 EST Message-ID: To: nimrod-wg@BBN.COM Subject: Violent agreement... ?? From: "Michael A. Patton" Over the weekend, I thought a bit more about the questions of selecting the right combination of arcs/nodes/attributes/metanodes or whatevers and ended up deciding we might possibly be in violent agreement... I think the use of the terms nodes and arcs is what's causing the apparent conflict, and that, in fact, neither camp is actually proposing nodes and arcs in the original mathematical sense, but adapting these terms in slightly different ways. It's my impression that whichever of these we pick, when we get down to actual binary representation, it may well be (effectively) the same... The only difference is how you squint your eyes. One way of looking at the similarity is to note that both camps have some set of things which have attributes, the difference is that one camp calls some of these nodes and some arcs, while the other calls them all nodes(*), and allows for the node/arc dichotomy to be an attribute if you want it... In either case, you need these attribute holding things, and some way to list the table of connectivity. That mainly leaves the way the connection of these things is rtepresented as a distinguishing factor. This is actually an aspect that hasn't been discussed much, but one where they _might_ offer differences in expressiveness that are useful. I'll describe (at a very glossy level) what I see as the candidates and how similar the two camps are... In the metanode camp, the metanodes need to be pretty much isomorphic so that leads to only two candidate representations. A metanode has a table for each outgoing link saying where the other end is, or it has a similar table for incoming. The former seems more pleasing to think about, but, I believe they are essentially equivalent. In the other camp, there is more flexibility in this representation. The particularly interesting case, is to say that only arcs have these lists of links, one list of incoming links and one of outgoing. In this case, you also enforce a restriction that routes must alternate between arcs and nodes. This has the disadvantage that you need one of these attribute bearing things between two nodes, even if it doesn't, in fact, have any attributes of consequence. Additionally separate arcs and nodes could use either of the two methods above, i.e. all nodes and all arcs have a list of links (flip a coin for incoming or outgoing). In this case it's indistinguishable at the representation level except for the fact that in one case the bit distinguishing arcs from nodes is in the type and in the other it's an attribute... why are these different? So, I think the argument isn't over anything substantial, but rather over the semantics of what we call the various frobs with attributes and at what levels they get distinguished in their pourpose. I expect that, in actual application, there will be lots of attributes in these frobs that are not actually used in route generation (as a network operator, one of the attributes *I* want in the frob representing the line from Cambridge to DC is the circuit number, but only in the version of the map that I *don't* give out :-) and whether the frob is an arc or a node is probably one of these... -MAP (*) This was why we started calling them metanodes, but I don't think that really helped...   Received: from PIZZA.BBN.COM by BBN.COM id aa23779; 10 Jan 95 11:11 EST Received: from pizza by PIZZA.BBN.COM id aa25582; 10 Jan 95 10:49 EST Received: from BBN.COM by PIZZA.BBN.COM id aa25578; 10 Jan 95 10:45 EST Received: from quern.epilogue.com by BBN.COM id aa20619; 10 Jan 95 10:40 EST From: Dave Bridgham Sender: dab@epilogue.com To: nimrod-wg@BBN.COM In-reply-to: Noel Chiappa's message of Sat, 7 Jan 95 04:07:05 -0500 <9501070907.AA26731@ginger.lcs.mit.edu> Subject: Open map questions Date: Tue, 10 Jan 95 10:40:01 -0500 Message-ID: <9501101040.aa22654@quern.epilogue.com> Date: Sat, 7 Jan 95 04:07:05 -0500 From: Noel Chiappa (They should also be able to nest other attributes, so you can give any other defined attribute complex availability; hmm, the more I think about it, the more S-expressions are the way to go for representing attributes! :-) Do I sense a convert? In working on answering Ram's original message I decided to play a bit with writing up Epilogue's map and connection with NearNet. I certainly found that it worked out quite naturally to have one thing (call it a node or metanode or node/arc) that was the base entitiy in the map and just use it over and over. I also used s-expressions but I'm sure it could easily be converted to many other, less powerful, representations. :-) In this example, each proper noun would really be a locator. The maps I've included here are two nodes in the universe, epilogue and nearnet, and the internal maps of those two nodes. It should be obvious how this could be expanded to as many levels as needed. I didn't include any hosts because I didn't want to type that much, but in fact I think the hosts should show up in the maps too. I'd like to keep the base map description language no more complex than this. I don't think it needs to be so I don't think it should be. (universe (epilogue (links nearnet)) (nearnet (links epilogue)) (epilogue (epilogue-ethernet-1 (bandwidth 10000000) (latency 10us) (links gw-main)) (gw-main (latency 1ms) (links epilogue-ethernet-1 epilogue-internal-line)) (epilogue-internal-line (bandwidth 56000) (lateny 20us) (links gw-main gw-gavin)) (gw-gavin (latency 1ms) (links epilogue-internal-line epilogue-ethernet-2)) (epilogue-ethernet-2 (latency 10us) (bandwidth 10000000) (links gw-gavin epilogue-gw.near.net))) (nearnet (epilogue-gw.near.net (latency 100us) (links epilogue-ethernet-2 nearnet-line-to-epilogue)) (nearnet-line-to-epilogue (bandwidth 56000) (latency 20us) (links epilogue-gw.near.net mit1-gw.near.net)) (mit1-gw.near.net (latency 100us) (links nearnet-line-to-epilogue)))   Received: from PIZZA.BBN.COM by BBN.COM id aa28291; 10 Jan 95 12:08 EST Received: from pizza by PIZZA.BBN.COM id aa26101; 10 Jan 95 11:49 EST Received: from BBN.COM by PIZZA.BBN.COM id aa26097; 10 Jan 95 11:47 EST Received: from Newbridge.COM by BBN.COM id aa25162; 10 Jan 95 11:29 EST Received: from Newbridge.COM ([138.120.100.14]) by nbkanata.Newbridge.COM (4.1/SMI-4.1) id AA06556; Tue, 10 Jan 95 11:23:48 EST Received: from mako.newbridge.com by Newbridge.COM (4.1/SMI-4.0) id AA21456; Tue, 10 Jan 95 11:23:45 EST Received: from lobster.Newbridge.COM by mako.newbridge.com (4.1/SMI-4.1) id AA00999; Tue, 10 Jan 95 11:29:08 EST Received: by lobster.Newbridge.COM (5.0/SMI-SVR4) id AA00134; Tue, 10 Jan 1995 11:29:26 +0500 Date: Tue, 10 Jan 1995 11:29:26 +0500 From: Joel Halpern Message-Id: <9501101629.AA00134@lobster.Newbridge.COM> To: dab@epilogue.com Subject: Re: Open map questions Cc: nimrod-wg@BBN.COM X-Sun-Charset: US-ASCII Content-Length: 836 From having maintained LISP interpretters, I tend not to think of S-Expressions as an easy thing for computers to parse. The underlying parsing processing code was "interesting". This note is prompted by trying to figure out why I want nested TLVs, which are formally equivalent to S-Expressions. My reasoning is that If I have a numeric type code, and a length then: 1) I can add some tags on the type code to describe the processing for unknown types 2) The length makes skipping entries eisier 3) The type code will drive the parsing of the contents. For cases where the contents are a repeated list, one can include as part of the value a count, and then the repeated entries. Or to put it another way, computers don't read ASCII strings very well. Yours, Joel M. Halpern jhalpern@newbridge.com Newbridge Networks Inc.   Received: from PIZZA.BBN.COM by BBN.COM id aa01106; 10 Jan 95 12:43 EST Received: from pizza by PIZZA.BBN.COM id aa26261; 10 Jan 95 12:03 EST Received: from TTL.BBN.COM by PIZZA.BBN.COM id aa26257; 10 Jan 95 12:01 EST To: nimrod-wg@BBN.COM Subject: Update and Query-Response Protocols and associated Functionality Date: Tue, 10 Jan 95 12:03:31 -0500 From: Ram Ramanathan This is the first article of a series of articles that we expect, after revisions, to comprise the Nimrod Protcol Specification document. Other members of the working group will cover the following in other articles: - Path Setup and Teardown Protocol - Nimrod Database Contents organization - Agent and Neighbor discovery protocols - Reliable Transport Protocol Please chew on these and post your comments/concerns/questions/suggestions/ pet-peeves etc. Cheers, -Ram. -------------------------Begin Draft Article (715 lines)---------------------- Specification of the Hierarchical Update and Hierarchical Query-Response Protocols for Nimrod (DRAFT). Author : Ram Ramanathan Affiliation : BBN Systems and Technologies, Cambridge, MA. Contact : ramanath@bbn.com, (617) 873-2736. 1. ABOUT THIS ARTICLE This article describes the Hierarchical Update Protocol (henceforth referred to simply as the Update Protocol) and the Hierarchical Query-Response Protocol (henceforth referred to simply as the Q-R Protocol) for Nimrod. Emphasis is on protocol engines and packet contents and not packet formats. Additionally, we also briefly discuss the functionality of Map Construction and Association Maintenance and their realization using the Update and Q-R protocols. This article uses a number of concepts and terms from the Internet-Drafts "The Nimrod Architecture" (draft-castineyra-routing-arch-00.txt) and "A Perspective on Nimrod Functionality" (draft-steenstrup-fun-perspective-00. txt). Much of the discussion assumes that the reader is familiar with at least "The Nimrod Architecture". The protocol specifications given here reflect the current state of the work in progress, and may be updated, replaced or obsoleted by other documents at any time. The main purpose of this article is to solicit comments, suggestions from the members of the nimrod working-group. Please send such comments and suggestions to nimrod-wg@bbn.com. Specific questions may also be addressed to the author at the contact points given above. 2. FUNCTIONALITY 2.1. BACKGROUND Nimrod functionality includes the following : Agent Discovery, Neighbor Discovery, Locator Acquisition, Arc Formation, Map Construction and Query, Association Database Maintenance and Query, Route construction and Query, Path Setup and Teardown. Each functionality will be described in an article on the protocol that supports it. A tentative list of such articles is given below, along with the functionality they will probably be dealing with. 1. Map Construction and Query, Association Maintenance and Query: Described in this article. 2. Locator acquisition and Query, Route construction and Query, Arc Formation: To be included in the next version of this article. 3. Agent Discovery, Neighbor discovery: To be described in another article by other member(s) of the working group. 4. Path Setup and Teardown : To be described in another article by other member(s) of the working group. The functionality mentioned above is realized using Nimrod "Agents". There are five kinds of agents: Endpoint representatives, that maintain the attributes of an endpoint and act on its behalf; Node representatives that maintain the attributes of a node and act on its behalf; Association agents responsible for answering and propagating assoication queries; Route agents, responsible for collecting maps from nodes and for generating and dispensing routes; and Forwarding agents, responsible for initiating neighbor relationships with forwarding agents in other nodes, requesting routes, installing forwarding information and forwarding messages. In this section, we briefly describe how maps are constructed and associations are maintained. The description is based on and rephrases that given in [2]. In describing the functionality, we focus on an arbitrary node N in the Nimrod hierarchy and consider the interaction between agents in N and agents in the immediate hierarchial vicinity of N (i.e., agents in the parent, sibling and child nodes of N). Describing the behavior at a single level suffices because the functionality of an agent is independent of its absolute hierarchical level, barring boundary conditions at the topmost node and the bottommost nodes (though straightforward, we shall ignore these boundary conditions in this section, in the interest of simplicity). For ease and brevity of description, we use E, O, A, R and F to denote the endpoint rep., node rep., association agent, route agent and forwarding agent, and suffixes p, s and c to denote parent, sibling and child. For example, Ap denotes an association agent in the parent node of the considered node. Our description assumes that Agent Discovery has been completed and agents within a node have some knowledge of each other,as described in [2] and summarized below: a. All forwarding agents in a node N know how to reach at least one Entity Representative, at least one Association Agent (if one exists) and at least one Route Agent (if one exists) in N. b. All agents of a given type and belonging to the same node know how to reach each other. c. All boundary forwarding agents of a node know how to reach each other. d. Each interior forwarding agent knows how to reach at least one boundary forwarding agent. 2.2. MAP CONSTRUCTION A map specifies the nature of the connectivity between and within Nimrod nodes. Maps are maintained and updated by node respresentatives. A node representative maintains two kinds of maps for its node: a "detailed map" that depicts the children nodes, the arcs interconnecting children nodes and the arcs connecting children nodes to external nodes plus the services provided by each of these nodes and arcs; an "abstract map" that depicts the node, the arcs connecting it to other nodes and the services provided by the node between any pair of incoming and outgoing arcs and by the outgoing arcs themselves. A node representative may construct its abstract map using information obtained from abstraction of detailed map, configuration or measurement of service qualities across the node. A node N that requires the map of another node M in order to construct its route sends a "map query" using the Q-R Protocol (detailed in section 3) to M. M responds to N with its abstract/detailed map. Maps are also automatically updated in response to topological changes using constrained hierarchical flooding. A change in the topology within a node N may change the abstract map of that node. This in turn changes the detailed map of N's parent. This change may cause a change in abstract map of N's parent and so on. These changes are effected using the "map update" mechanism described below. Let us consider a node N in the hierarchy and assume that its abstract map has changed. Then the node representative O of N initiates the map update using the Update Protocol (described in section 3). O sends the map to a boundary forwarding agent F for N, which is also a (interior) forwarding agent for N's parent p(N). F distributes the map to one node representative Op and one route agent Rp in p(N), if it exists. Op further redistributes the map all of the node representatives in p(N) and Rp redistributes the map to all of the route agents in p(N). Now that Op has gotten the new abstract map of N, it is in a position to update *its* detailed map and abstract map. If there is indeed a change in the abstract map of p(N), Op initiates a map update. The description in the preceding paragraph now applies recursively at this higher level. Note that only *one* entity representative in p(N), namely the one that received the update from the forwarding agent, takes the initiative in continuing the update to higher levels. In the worst case, a change in node's abstract map may force changes in all of its ancestral nodes' abstract maps. We expect such changes to be rare, especially in nodes whose descendants are multiply connected. 2.3. ASSOCIATION MAINTENANCE Nimrod maintains the associations between endpoints and their locators in an "association database". Each endpoint has at least one endpoint identifier (EID), which is a globally unique, "computer-friendly" bit-string. In addition, we expect that an endpoint will also have an endpoint name (EN) that are structure "user-friendly" (ASCII) strings designed to be used as keys in a distributed database. An agent that requires the association entry for a given endpoint queries the association database with the EN as the key and obtains the corresponding EID(s) and locator(s). Changes in association are incorporated into the database using "association updates", described below. Before discussing how association updates work, it is important to look at how the association database might be stored in the network. A possible approach and the rationale for it are given in [2]. We describe here the main features of this approach and use it as our method of choice. The association database is organized as follows. We assume that endpoint labels are structured hierarchically using a dotted notation. For instance, nodes with ENs A.B and A.C are contained within the node with EN A. We begin with the universal node with EN U. For each x such that U.x is a valid EN prefix, we find the node n(U.x) containing the management authority corresponding to U.x. A pointer is placed in all of the association agents in U to the effect that a query for label U.x.* should go to n(U.x). Then we go down one level and repeat the procedure recursively for each of the nodes that were selected above. We repeat this all the way down the hierarchy. Thus, given an EN, say U.A.B.C, there is a linked chain of nodes (LCN) realized in the corresponding association agents that ends up at the node containing the association for U.A.B.C. We call an association agent in such a node the "authoritative source" for the association. All queries that need an up-to-date answer must reach the authoritative source. All updates must eventually reach the authoritative source (caching of associations may be done for efficiency (see [2])). Thus the crux of the association update (and also the association query) functionality lies in seeking the linked chain of nodes (LCN) and upon finding it, going down the chain until the authoritative source is reached. An association update (AUPD) is initiated by an endpoint representative E of the endpoint whose locator has changed. E hands the AUPD to an association agent in the same node N if one exists, or to the boundary forwarding agent F otherwise. F also acts as an interior forwarding agent for p(N) and sends the AUPD to an association agent in p(N) if one exists or to the boundary forwarding agent Fp in p(N). In this manner, the AUPD goes up the hierarchy until it reaches an association agent A in some node M. Upon receipt of the AUPD, A checks to see if it is in the linked chain of nodes corresponding to the EN in the AUPD. If it is not, then A forwards the AUPD to the boundary forwarding agent F. F also acts as an interior forwarding agent for p(M) and sends the AUPD higher up in the hierarchy. Thus, the AUPD goes up the hierarchy until it reaches an association agent B that is within the LCN. In the worst case, this will be the top-level (universal) node's association agents. B uses the EN and the its pointers (explained earlier) to determine the next node in the linked chain and forwards the AUPD towards that node. There, it will be received by the forwarding agent and handed over to an association agent which will repeat the procedure. In this manner, the update will eventually reach the authoritative source. The non-authoritative association agents encountered by the AUPD also distribute the AUPD to all other association agents in the same node. All such agents cache the association and may use this cache to respond to a future (non-authoritative) query. 3. PROTOCOLS 3.1. The Hierarchical Update Protocol 3.1.1. Introduction The Update Protocol is used to update database contents (e.g., the association database, the map database etc.) in an efficient manner. By efficient, we mean that the implicit flooding constituting the protocol is carefully constrained by involving only a few agents per update. The Update Protocol assumes the existence of a Reliable Transport Protocol and uses it to achieve reliability in its updates. No reliability mechanism (such as retransmissions etc.) is incorporated into the Update Protocol itself. Additionally, we assume that authentication and/or encryption of the message is done elsewhere, either as a separate layer or as part of the reliable transport. This will be specified separately in another document by the Nimrod working group. We also assume that agent discovery has been completed with agents within a node knowing how to reach other agents directly or indirectly (see section 2.1). Also, we assume that path setup and data forwarding functionality is available when required. Agent Discovery and Path Setup will be specified separately in another document by the Nimrod working group. The Update Protocol consists of an Update Message that is generated by the agent wishing to make an update to a particular database. The originating agent forwards the message to one or more agents which further forward it to other agents and so on, until all the necessary database locations have been updated. Once an originating or transit agent has successfully forwarded a message, it does not retain any state corresponding to the message. No acknowledgements are sent from the recipients of the Update Message. Exceptions are handled by triggering SNMP events. Thus, the state machine constituting the protocol engine at the agents is quite simple, if not trivial. However, the decision of whether to cache the message contents or not, and the decision of who to forward the message to requires some specification. We have used an Update Message Forwarding Table (UMFT) for this purpose. There is one UMFT for each of the five types of agents. The UMFT describes the actions to be taken on the receipt of a particular message from a particular agent. The UMFT depends on what functionality we map into the protocol and how we do the mapping. The UMFT given here maps the association and map update in the manner described in section 2. We note that the UMFT-based protocol specification approach provides flexibility by making it easy to change the functionality and the mapping - you just need to alter the entries in the table. We expect to include the locator update functionality also in the next version of this document. The Update Protocol is typically used by Nimrod agents or other "users" in order to initiate updates. We use the word "Application" to denote these users. For instance, the generation of the initial association update is done by an endpoint representative, which is the application using the protocol. 3.1.2. Message Contents Apart from the "standard" fields in the IP and Nimrod headers, the Update Message should contain the following. Some of these fields may eventually be pulled out to the Nimrod header. For the protocol, it is sufficient that these fields are present somewhere in the packet. - Originating agent EID. - Originating agent locator. - Database Type (which database the message refers to). - Timestamp of when the message was generated. - Sequence number for the message (a different stream for each database). - Update data (specific to the database). The length and packet format of these fields is TBD. 3.1.3. Transit Agent Protocol Engine Given below is the algorithm executed by transit agent (ThisAgent) upon receipt of Update Message (UpdMsg) from another agent (PrevAgent). The UMFT is described in section 3.1.5. begin /* Check message contents. More checks than those given here are probably needed. */ if timestamp(UpdMsg) is invalid /* too old or too new */ then trigger SNMP event and discard UpdMsg. if seq_num(UpdMsg) is invalid /* duplicate */ then trigger SNMP event and discard UpdMsg. /* Consult the UMFT table for caching and forwarding directions */ NextAgentType = UMFT(ThisAgent, PrevAgent, UpdMsg) if NextAgentType is not a valid agent, discard message. repeat choose a (previously unchosen) agent A of NextAgentType. if none found then trigger SNMP event and discard message else forward UpdMsg to A. until successfully forwarded or message discarded. end. 3.1.4. Originating Agent Protocol Engine This is identical to the transit agent protocol engine except for the fact that the UpdMsg is received from an application and not from another agent. That is, make PrevAgent = Application and the same algorithm applies. Also, the packet is timestamped and a sequence number is put on it. The differences are small and so we dispense with the complete specification. 3.1.5. The Update Message Forwarding Table (UMFT) For each of 5 agent types (Forwarding Agent, Enpoint Rep., Node Rep., Association Agent and Route Agent), we give below the actions upon receipt of an UpdMsg. The agents are represented by F, E, O, A and R and suffixed by p, c or s to indicate the agent in the parent, child or sibling node of the node under consideration. No suffix means the agent belongs to the node under consideration. Note that a boundary forwarding agent for a given node acts also as an interior forwarding agent for its parent node. We shall use F to represent the boundary forwarding agent and Fc to represent the interior forwarding agent (boundary forwarding agent for some child of the node). A *particular* child/sibling node is indicated by paranthesizing the node. For instance the forwarding agent of child node N is Fc(N). The 1st column contains the type of the message, 2nd contains the previous agent type and the 3rd contains the actions to be taken. Combinations not given represent "Unexpected" situations. If these happen, an SNMP event is triggered and the message is discarded. The table makes use of two functions "forward" and "present", whose semantics are described following the table. whose semantics are indicated following the table. The table uses the concept of Linked Chain of Nodes (LCN) details of which were given in section 2.1. *********** UMFT for F *********** --------------------------------------------------------------------------- Message PrevAgent Actions --------------------------------------------------------------------------- Association Ep,A, if present(Ap) Update Fc (interior FA) then forward (UpdMsg, Ap) else forward (UpdMsg, Fp) --------------------------------------------------------------------------- Association Fp,Ap if present(A) Update then forward (UpdMsg, A) else forward (UpdMsg, Fc) -------------------------------------------------------------------------- Map Update O forward (UpdMsg, {Ep, Rp}) -------------------------------------------------------------------------- *********** UMFT for O *********** -------------------------------------------------------------------------- Message PrevAgent Actions --------------------------------------------------------------------------- Map Update Fc, forward (UpdMsg, {all O}); Application if abstract map of MyNode changed put new abstract map in NewUpdMsg; forward (NewUpdMsg, F); --------------------------------------------------------------------------- Map Update O Cache i.e., Update Map Database --------------------------------------------------------------------------- ********** UMFT for E ********** -------------------------------------------------------------------------- Message PrevAgent Actions --------------------------------------------------------------------------- New Assoc. Application make NewUpdMsg and put new assoc. Indication F = neighboring forwarding agent; forward (NewUpdMsg, F); --------------------------------------------------------------------------- *********** UMFT for A *********** -------------------------------------------------------------------------- Message PrevAgent Actions --------------------------------------------------------------------------- Association Fc forward (UpdMsg, {all A}); Update (interior FA) if (ThisAgent is not Author. Src) if (ThisAgent in LCN) N = next node in chn; forward (UpdMsg, Fc(N)); else forward (UpdMsg, F); -------------------------------------------------------------------------- Association F forward (UpdMsg, {all A}); Update if (ThisAgent is not Author. Src) N = next node in LCN; forward (UpdMsg, Fc(N)); ------------------------------------------------------------------------- Association A Cache, i.e, Update Association Databs Update ------------------------------------------------------------------------- *********** UMFT for R *********** -------------------------------------------------------------------------- Message PrevAgent Actions --------------------------------------------------------------------------- Map Update F forward (UpdMsg, {all R}) --------------------------------------------------------------------------- Map Update R Cache, i.e., Update Map Database --------------------------------------------------------------------------- Semantics of functions: forward (Msg, AgentSet) : forward Msg *reliably* to one agent of each type given in Agent Set. Includes the functionality of resending to another agent if one agent cannot be reached. The set {all X} indicates all agents of type X including itself. May involve multiple hops. If an agent A in AgentSet is not 1 hop away, Msg is handed over to a neighboring forwarding agent that knows how to reach A. present (Agent) : returns true if there is an agent of type AgentType 3.2. The Hierarchical Query-Response Protocol 3.2.1. Introduction The Q-R Protocol is used to obtain database information(e.g., the association database, the map database etc.) in an efficient manner. The Q-R Protocol assumes the existence of a Reliable Transport Protocol and uses it to achieve reliability in its updates. No reliability mechanism (such as retransmissions etc.) is incorporated into the Q-R Protocol itself. Additionally, we assume that authentication and/or encryption of the message is done elsewhere, either as a separate layer or as part of the reliable transport. This will be specified separately in another document by the Nimrod working group. We also assume that agent discovery has been completed with agents within a node knowing how to reach other agents directly or indirectly (see section 2.1). Also, we assume that path setup and data forwarding functionality is available when required. Agent Discovery and Path Setup will be specified separately in another document by the Nimrod working group. The Q-R protocol consists of a Query Message that is generated by the agent wishing to make a query. The originating agent forwards the message to one or more agents and awaits a response to the query. The response to the query is contained in a Response Message that is generated by the agent that has access to the information requested in the query. If the originator does not get a response within a certain time t, it informs the application of a query failure. The value of t may be configured or given to the protocol by the application. The application also has the option of requesting an abort of the query - in this case, the state is reset and the response is ignored. As in the case of the Update Protocol, exceptions are handled by triggering SNMP events. The state machine for the originating agent has two states - INITIAL and WAITING (for a response). A transition from INITIAL to WAITING is made when a query is sent and the state is reset to INITIAL when a response arrives, timer expires or the query is aborted. The transit agent state machine, as in the Update Protocol, is trivial. The decision of whether to cache the message contents or not, and the decision of who to forward the message is done using the Query Message Forwarding Table (QMFT). There is one QMFT for each of the five types of agents. The QMFT describes the actions to be taken on the receipt of a particular message from a particular agent. The QMFT depends in a large way on what functionality we map into the protocol and how we do the mapping. The QMFT given here maps the association and map update in the manner described in section 2. We note that the QMFT-based protocol specification approach provides flexibility by making it easy to change the functionality and the mapping - you just need to alter the entries in the table. We expect to include route query and locator query functionalities also in the next version of this document. The Q-R Protocol is typically used by Nimrod agents or other "users" in order to initiate updates. We use the word "Application" to denote these users. For instance, the generation of the initial association update is done by an endpoint representative, which is the application using the protocol. 3.2.2. Message Contents Apart from the "standard" fields in the IP and Nimrod headers, the Query Message should contain the following. Some of these fields may eventually be pulled out to the Nimrod header. For the protocol, it is sufficient that these fields are present somewhere in the packet. - Originating agent EID. - Originating agent locator. - Database Type (which database the information is requested from). - Timestamp of when the message was generated. - Query identification number (used to match responses to queries) - Query data (specific to the database). The length and packet format of these fields is TBD. Apart from the "standard" fields in the IP and Nimrod headers, the Response Message should contain the following. Some of these fields may eventually be pulled out to the Nimrod header. For the protocol, it is sufficient that these fields are present somewhere in the packet. - Originating agent EID. - Originating agent locator. - Database Type (which database the information is about) - Timestamp of when the message was generated. - Response identification number (equal to the id of Query responding to) - Response data (specific to the database). 3.2.3. Transit Agent Protocol Engine Given below is the algorithm executed by the originating agent (ThisAgent) upon receipt of Query Message (QryMsg) from another agent (PrevAgent). The QMFT is described in section 3.2.5. begin /* Check message contents. More checks than those given here are probably needed. */ if timestamp(QryMsg) is invalid /* too old or too new */ then trigger SNMP event and discard QryMsg. if seq_num(QryMsg) is invalid /* duplicate */ then trigger SNMP event and discard QryMsg. /* Consult the QMFT table for caching and forwarding directions */ NextAgentType = QMFT(ThisAgent, PrevAgent, QryMsg) if NextAgentType is not a valid agent, discard message. repeat choose a (previously unchosen) agent A of NextAgentType. if none found then trigger SNMP event and discard message else forward QryMsg to A. until successfully forwarded or message discarded. end 3.2.4. Originating Agent Protocol Engine The originating agent protocol engine has two states INITIAL and WAITING. We define three types of messages that it can receive : QryAbort, a message from the application requesting the agent to abort the query; QryFail, a message sent by the agent to the application informing of failure; a DoQuery message from the application, requesting execution of the Q-R protocol. We note that each query will initiate a new state machine. We assume that messages are demultiplexed apriori to the "right" state machine. begin receive process message state INITIAL : if it is DoQuery message from application Prepare QryMsg and put timestamp and sequence number on it; set query-timer with value from application or configuration; Execute Transit Agent Protocol Engine (see section 3.2.3); Transition to state WAITING. if it is any other message Discard the message state WAITING : if it is QryResp from peer deliver database contents to application; Transition to state INITIAL; if it is QryAbort from application Transition to state INITIAL; if it is query-timer expiration send a QryFail message to application; Transition to state INITIAL; if it is any other message Discard the message. end. 3.2.5. The Query Message Forwarding Table For each of 5 agent types (Forwarding Agent, Enpoint Rep., Node Rep., Association Agent and Route Agent), we give below the actions upon receipt of an UpdMsg. The agents are represented by F, E, O, A and R and suffixed by p, c or s to indicate the agent in the parent, child or sibling node of the node under consideration. No suffix means the agent belongs to the node under consideration. Note that a boundary forwarding agent for a given node acts also as an interior forwarding agent for its parent node. We shall use F to represent the boundary forwarding agent and Fc to represent the interior forwarding agent (boundary forwarding agent for some child of the node). A *particular* child/sibling node is indicated by paranthesizing the node. For instance the forwarding agent of child node N is Fc(N). The 1st column contains the type of the message, 2nd contains the previous agent type and the 3rd contains the actions to be taken. Combinations not given represent "Unexpected" situations. If these happen, an SNMP event is triggered and the message is discarded. The table makes use of three functions "forward", "send" and "present" whose semantics are indicated following the table. The table uses the concept of Linked Chain of Nodes (LCN) details of which were given in section 2.1. ********** QMFT for F ********** --------------------------------------------------------------------------- Message PrevAgent Actions --------------------------------------------------------------------------- Association Ep,A if present(Ap) Query Fc (interior FA) then forward (QryMsg, Ap) else forward (QryMsg, Fp) --------------------------------------------------------------------------- Association Fp,Ap if present(A) Query then forward (QryMsg, A) else forward (QryMsg, Fc) --------------------------------------------------------------------------- Map Querying forward (QryMsg, E) Query node --------------------------------------------------------------------------- ********** QMFT for O ********** --------------------------------------------------------------------------- Message PrevAgent Actions --------------------------------------------------------------------------- Map Query F if query is answerable send-response(QryRsp, Queryingnode) --------------------------------------------------------------------------- *********** QMFT for E *********** --------------------------------------------------------------------------- Message PrevAgent Actions --------------------------------------------------------------------------- Request for Application make QryMsg using Request for loc; Associaton Fnbr = neighboring forwarding agent; forward (QryMsg, Fnbr); --------------------------------------------------------------------------- ********** QMFT for A ********** --------------------------------------------------------------------------- Message PrevAgent Actions --------------------------------------------------------------------------- Association Fc if (ThisAgent is Author. Src OR Query (cached answer is okay AND assoc. found in cache)) send-response (QryRsp, Queryingnode) else if (ThisAgent in Linked Chain) N = next node in chn; forward (QryMsg, Fc(N)); else forward (QryMsg, F); ---------------------------------------------------------------------------- Association F if (ThisAgent is Author. Src OR Query (cached answer is okay AND assoc. found in cache)) send-response (QryRsp, Queryingnode) else N = next node in linked chn; forward (QryMsg, Fc(N)); ---------------------------------------------------------------------------- ********** QMFT for R ********** --------------------------------------------------------------------------- Message PrevAgent Actions --------------------------------------------------------------------------- Request for Application N = node whose map is required Map make QryMsg using Request for Map send (QryMsg, N); --------------------------------------------------------------------------- Semantics of functions: forward (Msg, AgentSet) : forward Msg *reliably* to one agent of each type given in Agent Set. Includes the functionality of resending to another agent if one agent cannot be reached. The set {all X} indicates all agents of type X including itself. May involve multiple hops. If an agent A in AgentSet is not 1 hop away, Msg is handed over to a neighboring forwarding agent that knows how to reach A. send (Msg, Node) : conveys Msg to a boundary forwarding agent in Node. May need to set up a path to do this. present (Agent) : returns true if there is an agent of type AgentType. 4. REFERENCES [1] I. Castineyra, J. N. Chiappa, M. Steenstrup, "The Nimrod Routing Architecture", Working-Draft, July 1994. [2] M. Steenstrup, "A Perspective on Nimrod Functionality", Working-Draft, January 1995.   Received: from PIZZA.BBN.COM by BBN.COM id aa02816; 10 Jan 95 13:08 EST Received: from pizza by PIZZA.BBN.COM id aa26627; 10 Jan 95 12:50 EST Received: from BBN.COM by PIZZA.BBN.COM id aa26623; 10 Jan 95 12:48 EST Received: from ginger.lcs.mit.edu by BBN.COM id aa00521; 10 Jan 95 12:34 EST Received: by ginger.lcs.mit.edu id AA06715; Tue, 10 Jan 95 12:34:22 -0500 Date: Tue, 10 Jan 95 12:34:22 -0500 From: Noel Chiappa Message-Id: <9501101734.AA06715@ginger.lcs.mit.edu> To: kasten@ftp.com, nimrod-wg@BBN.COM Subject: Re: One place to simplify Cc: jnc@ginger.lcs.mit.edu From: kasten@ftp.com (Frank Kastenholz) To me it seems that there are three possible outcomes of sending a flow setup: 1. The request got lost in the network 2. The request can't be honored at some point in the network 3. Everything is just fine. I certainly want to be able to differentiate numbers 1 and 2 from number 3. If the request fails for some reason then I want to be able to detect it and re-do it (performing whatever failure processing is needed). And then results 1 and 2 indicate different problems in the network and have different recovery modes. As long as I can differentiate the two then recovery is vastly helped. But surely you can differentiate between 1 and 2, because for 2 you always get a nack? Also, don't forget, nacks (and optional end-end acks) probably are not transmitted reliably, so that even if you do have *required* acks, you still have the "silence" case to deal with; i.e. in those cases you can't tell whether it was 1 or 2 (or 3, for that matter). Yes, you need to be able to distinquish between 3 and the other two, but there's got to be some higher level thing (e.g. transport connection ack, or an answer to your query, or whatever) that allows you to find that out. > Anyway, if you don't hear a nack, try doing a transport connection setup, When? I'd rather get a positive e2e ack that it worked, then I can start sending data as soon as possible, which might be very important for any sort of real-time application _or_ if a flow costs me money just to for keeping the flow set up. Yeah, the more I think about it the more I think the right thing is to piggy- back the transport setup on the flow setup, the way I talked about. Also, it might be that flow-setups are 2-step. The setup packet would be a provisional setup, with the flow not being truly 'committed' until the e2e ack comes back. This has a number of issues. One, you can't start sending data until you get an ack; maybe not a problem but still. Second, the ack has to come back by the same path. This could very well be a problem. Third, I'd be worried that, if the resources aren't comitted, you'd get failure modes involving resource deadlocks, or something. I don't know what the resource guys think about all this, but as far as I recall all their stuff commits resources as soon as it gets a real request (i.e. not a discovery thing). In general, it's more complicated, and I hate complicated stuff. > Actually, we probably want to piggyback the transport connection setup > on the flow setup, to avoid a round-trip time of delay on transport > connection setup. That way, the transport ack *is* the flow setup ack. What happens for applications that use an ack-less transport -- such as RTP/video/audio? I'm talking about setup acks, not data acks. Noel   Received: from PIZZA.BBN.COM by BBN.COM id aa05292; 10 Jan 95 13:43 EST Received: from pizza by PIZZA.BBN.COM id aa26974; 10 Jan 95 13:21 EST Received: from BBN.COM by PIZZA.BBN.COM id aa26966; 10 Jan 95 13:20 EST Received: from wd40.ftp.com by BBN.COM id aa03087; 10 Jan 95 13:12 EST Received: from ftp.com by ftp.com ; Tue, 10 Jan 1995 13:12:06 -0500 Received: from mailserv-D.ftp.com by ftp.com ; Tue, 10 Jan 1995 13:12:06 -0500 Received: by mailserv-D.ftp.com (5.0/SMI-SVR4) id AA10499; Tue, 10 Jan 95 13:11:03 EST Date: Tue, 10 Jan 95 13:11:03 EST Message-Id: <9501101811.AA10499@mailserv-D.ftp.com> To: jnc@ginger.lcs.mit.edu Subject: Re: One place to simplify From: Frank Kastenholz Reply-To: kasten@ftp.com Cc: kasten@ftp.com, nimrod-wg@BBN.COM, jnc@ginger.lcs.mit.edu Content-Length: 1010 > > Actually, we probably want to piggyback the transport connection setup > > on the flow setup, to avoid a round-trip time of delay on transport > > connection setup. That way, the transport ack *is* the flow setup ack. > > What happens for applications that use an ack-less transport -- such > as RTP/video/audio? > > I'm talking about setup acks, not data acks. One of us is very confused. I read your comment ("Actually, ...") to imply that the opening of the transport connection (eg, the syn/syn-ack/ack of TCP) to serve as the e2e ACK that the flow was properly set up. So, if I set up a flow and use a connectionless transport over that flow (such as a udp-based audiocast) there is no transport setup ACK (i.e. no connection-open ack) to serve as the flow setup ACK. -- Frank Kastenholz "The dogmas of the quiet past are inadequate to the stormy present... As our case is new, so we must think anew, and act anew" - A. Lincoln   Received: from PIZZA.BBN.COM by BBN.COM id aa05418; 10 Jan 95 13:45 EST Received: from pizza by PIZZA.BBN.COM id aa26994; 10 Jan 95 13:23 EST Received: from BBN.COM by PIZZA.BBN.COM id aa26990; 10 Jan 95 13:21 EST Received: from ginger.lcs.mit.edu by BBN.COM id aa03261; 10 Jan 95 13:15 EST Received: by ginger.lcs.mit.edu id AA06971; Tue, 10 Jan 95 13:14:56 -0500 Date: Tue, 10 Jan 95 13:14:56 -0500 From: Noel Chiappa Message-Id: <9501101814.AA06971@ginger.lcs.mit.edu> To: nimrod-wg@BBN.COM, ramanath@BBN.COM Subject: Re: In praise of arcs with attributes Cc: jnc@ginger.lcs.mit.edu From: Ram Ramanathan First of all, my intention in using a C structure was only to clarify a point and I did not mean for anyone to take it literally. Therefore, I only gave the barest minimum needed to make my point. Understood. In any case, I wonder whether a design decision should be made depending on whether or not we implementation considerations like by using pointers to pointer arrays or other such powerful constructs? The thing is, that if you look at the course of design of information handling systems over the decades (and centuries, for that matter, if you go back to Babbage), you find that underneath all the ephemeral effluvium of details, the fundamentals of the irreducible minimum of what it takes to store and manipulate information starts to take shape, although of course it's somewhat murky. I find that considering the concrete details of what's going on here do help me get a feel for the underlying fundamentals, even if I can't articulate them precisely quite yet. Anwyway, enough philosophy of information systems, on to the matter at hand! Yes, arcs have locators too, that was one of the things covered in . Ah, OK. Of course, my adjacencies do not. here is the way to extend simply the structure I gave to have multi-point arcs etc. ... The obvious simple extension is for an arc to point to more than one node. The first field in struct _arcs would be a linked list of neighboring node or an array if you wish But then your "arc" structure looks *even more* like your "node" structre! That's what I've been saying all along; that when you actually look at what you need, in the way of bits (and this is really irrespective of the particular language or whatever you're working in, I'm talking about the underlying fundamentals I was alluding to above), arcs with attributes look just like nodes with attributes, especially if they are multi-point arcs. > two nodes A and B connected with an bidirectional link X, with some > attributes. In my scheme, each of A, B and X gets a metanode object ... > In your scheme, you need two node objects, but also two arc objects, > since each of your arc objects can only point to one node The only reason your representation is "superior" (assuming superior == space complexity, which may not necessarily be true) Understood (but space complexity can translate to processing complexity, all else being equal...) in my structure before, I did not worry about optimization for arc symmetry. There are several ways of doing that - one is to keep a bit (1 = bidirected, 0 = unidirected). Then, I'd have only 3 node objects - 2 node objects and 1 bidirectional arc object with *one* set of attributes. Sure, but then your arc object would have to have two node pointers in it (one for each direction); i.e. even if you don't go for full-blown multi-point arcs, your arc objects now still look more like node objects than your original "one-node" arc objects did. See, we keep coming back to the same place! Further, this representation explicitly precludes one from connecting arcs to arcs which would be allowed if everything were (meta)nodes. Nah, I can fix that easily. I simply define "arc" and "node" attributes, and say it's illegal to not alternate them. But as I talked about in a later note, I'm not sure this is worth it. Implementations would be less error prone and errors much easier to trace. Yes, but I'd like to see things like "router", "interface", and "network" attributes to allow all that. I am now convinced that the difference between the two schemes is too small to be of paramount importance - esp. in comparison to the importance of moving forward. Yes. But I think this has all been very education for all of us; we are all (including me) now totally familiar, and comfortable, with the underlying model. What's more, it's absolutely clear that we have followed the Nimrod motto, which is that "perfection is attained when there is nothing left to take away". I simply cannot conceive of a basic model simpler than metanodes and adjacencies, so it must be Right! :-) Noel   Received: from PIZZA.BBN.COM by BBN.COM id aa05673; 10 Jan 95 13:48 EST Received: from pizza by PIZZA.BBN.COM id aa27048; 10 Jan 95 13:29 EST Received: from BBN.COM by PIZZA.BBN.COM id aa27044; 10 Jan 95 13:27 EST Received: from Newbridge.COM by BBN.COM id aa03388; 10 Jan 95 13:17 EST Received: from Newbridge.COM ([138.120.100.14]) by nbkanata.Newbridge.COM (4.1/SMI-4.1) id AA08696; Tue, 10 Jan 95 13:11:49 EST Received: from mako.newbridge.com by Newbridge.COM (4.1/SMI-4.0) id AA25511; Tue, 10 Jan 95 13:11:44 EST Received: from lobster.Newbridge.COM by mako.newbridge.com (4.1/SMI-4.1) id AA01638; Tue, 10 Jan 95 13:16:49 EST Received: by lobster.Newbridge.COM (5.0/SMI-SVR4) id AA00141; Tue, 10 Jan 1995 13:17:08 +0500 Date: Tue, 10 Jan 1995 13:17:08 +0500 From: Joel Halpern Message-Id: <9501101817.AA00141@lobster.Newbridge.COM> To: nimrod-wg@BBN.COM Subject: Re: One place to simplify X-Sun-Charset: US-ASCII Content-Length: 480 In the discussion of piggy-backing the flow setup and the connection setup, it seems to me that we do have on additional case to consider: The one-way flow, which may not have a "connection setup" in the TCP sense. There probably is a packet exchange for receiving a video feed. But it is not a TCP connection. And it may take place in a fashion which makes piggy-backing the flow setup on it difficult. Yours, Joel M. Halpern jhalpern@newbridge.com Newbridge Networks Inc.   Received: from PIZZA.BBN.COM by BBN.COM id aa07182; 10 Jan 95 14:08 EST Received: from pizza by PIZZA.BBN.COM id aa27229; 10 Jan 95 13:48 EST Received: from BBN.COM by PIZZA.BBN.COM id aa27223; 10 Jan 95 13:46 EST Received: from ginger.lcs.mit.edu by BBN.COM id aa04515; 10 Jan 95 13:31 EST Received: by ginger.lcs.mit.edu id AA07091; Tue, 10 Jan 95 13:31:24 -0500 Date: Tue, 10 Jan 95 13:31:24 -0500 From: Noel Chiappa Message-Id: <9501101831.AA07091@ginger.lcs.mit.edu> To: nimrod-wg@BBN.COM, tracym@nsd.3com.com Subject: Re: One place to simplify Cc: jnc@ginger.lcs.mit.edu From: Tracy Mallory On the original topic of hop-by-hop acks: Do you have a model that failed flow setups are cheap/free? There may be regions where leaving stale flow state from failed setups is undesirable, for which a hop-by-hop ack/nak would be useful. Good point. We have to have some sort of underlying flow state GC mechanism (imagine if the host that set up a flow crashes, without taking down the flow, and forgets it set it up), probably a timer, but there might be some useful optimizations for removing state from failed flow setups. As long as it's not complicated! :-) Perhaps this is an attribute (inherited by the path from its constituent nodes (arcs? ;-)) that explicit acks/naks are required on certain paths? Interesting idea; that goes in the quiver for when we attack this part of the problem. Apologies if I've missed some basic assumptions/mechanisms in this area, in which case 'nevermind'. I'm lurking in fits and starts days. Nah. There's a lot that's still sketchy. I would encourage people to speak up; I'd rather hear potential good ideas than have them die in silence. Noel   Received: from PIZZA.BBN.COM by BBN.COM id aa07531; 10 Jan 95 14:13 EST Received: from pizza by PIZZA.BBN.COM id aa27282; 10 Jan 95 13:54 EST Received: from BBN.COM by PIZZA.BBN.COM id aa27277; 10 Jan 95 13:51 EST Received: from ginger.lcs.mit.edu by BBN.COM id aa05114; 10 Jan 95 13:40 EST Received: by ginger.lcs.mit.edu id AA07166; Tue, 10 Jan 95 13:40:23 -0500 Date: Tue, 10 Jan 95 13:40:23 -0500 From: Noel Chiappa Message-Id: <9501101840.AA07166@ginger.lcs.mit.edu> To: isidro@BBN.COM, nimrod-wg@BBN.COM Subject: Re: We don't need no steenking arcs! Cc: jnc@ginger.lcs.mit.edu From: Isidro Castineyra The majority opinion seems to be that arcs should have no attributes. Yes, but I'm more concerend with doing the Best thing, techically, if at all possible... Let's call arcs without attributes adjacencies. If adjacencies exist as independent entities, they are used to hold a pair of locators: the locator of the origin node and the locator of the destination node ... Instead of this, each node could have as one of its attributes a list/set of neighbor node locators. (This is even more attractive if we are not going to give locators to arcs.) Yes, I prefer the latter. (Of course, then we get into my open question about "is everything, including the list of adjacencies, an attribute, or are some things, like locators and adjacencies, "built in" to the node. Of course, I guess we could have one answer to that question for the protocol representation, and a different answer inside implementations.) Of course, we could still draw little arrows and call them arcs. But do we need the formal concept of arc in the architecture and as a formal element in the database? ... Unless I hear a good reason, I am going to obliterate/expunge/eliminate the "a" word from the architecure and database documents. Hmm. I think the non-Nimrodians in the IETF might find it easier to grasp the terminology of "node and arc" rather than "metanode and adjacency", since they're just going to look at a finished product, rather than understand *why* we did it that way. On the other hand, retaining the "metanode" naming allows us to explain how you can use them to build arcs with attributes, multi-point arc, etc. I personally can live with either (or the cross-product of "node and adjacency"), so I'll leave it up to what people think would be easiest for the rest of the IETF to understand and follow. Of course, this is the "Kissing Amoebae" note all over again. Yes, sigh. However, as I said to Ram, I think this length, repetitive process has helped us all understand what's going on here better, and I hope the result is a deep understanding in everyone as to why this is the technically best way to go. I take your unspoken point, that we need to stop this, and move on! Noel   Received: from PIZZA.BBN.COM by BBN.COM id aa09803; 10 Jan 95 14:41 EST Received: from pizza by PIZZA.BBN.COM id aa27569; 10 Jan 95 14:23 EST Received: from BBN.COM by PIZZA.BBN.COM id aa27565; 10 Jan 95 14:21 EST Received: from ginger.lcs.mit.edu by BBN.COM id aa07544; 10 Jan 95 14:14 EST Received: by ginger.lcs.mit.edu id AA07552; Tue, 10 Jan 95 14:13:53 -0500 Date: Tue, 10 Jan 95 14:13:53 -0500 From: Noel Chiappa Message-Id: <9501101913.AA07552@ginger.lcs.mit.edu> To: MAP@BBN.COM, nimrod-wg@BBN.COM Subject: Re: Violent agreement... ?? Cc: jnc@ginger.lcs.mit.edu From: "Michael A. Patton" It's my impression that whichever of these we pick, when we get down to actual binary representation, it may well be (effectively) the same... The only difference is how you squint your eyes. Yes, that's what I've been saying, *except* that with meta-nodes you only have one kind of object, not two, and I think that simplicity is good. One way of looking at the similarity is to note that both camps have some set of things which have attributes ... In either case, you need these attribute holding things, and some way to list the table of connectivity. That mainly leaves the way the connection of these things is represented as a distinguishing factor. Along with the question of whether you have to deal with two kinds of basic "things", or one. This is actually an aspect that hasn't been discussed much, but one where they _might_ offer differences in expressiveness that are useful. ... I'm dubious, actually. They seem to be functionally equivalent, so my prejudice is to pick the ones that's simpler. the metanodes need to be pretty much isomorphic so that leads to only two candidate representations. A metanode has a table for each outgoing link saying where the other end is, or it has a similar table for incoming. The former seems more pleasing to think about Yes. The particularly interesting case, is to say that only arcs have these lists of links, one list of incoming links and one of outgoing. In this case, you also enforce a restriction that routes must alternate between arcs and nodes. You can make, and enforce, this same retriction with metanodes, though. This has the disadvantage that you need one of these attribute bearing things between two nodes, even if it doesn't, in fact, have any attributes of consequence. Right. I've been thinking of ways to simplify maps, and one thing that comes to mind is that *iff* you have a part of the network which is resource-limited in the links (i.e. the routers have enough crunch to keep the links filled), and/or which has policies on the transmission facilities, we could simplify maps by simply dropping all the routers, and retaining only the indications of which networks are connected to each other. Even better, if you have parallel routers (for robustness) between a given pair of nets, you can hide all that, without needing to go to having a "virtual router" which encompasses the two. Of course, this would mean we'd have to skip the consistency check I proposed, for making sure that routers alternate between networks, but we can finesse that by changing the type of those networks to "area", or something. It would also allow us to express network-level bridges between networks; you'd have two separate networks in the map, but you can get from somethign attached to one to something attached to the other, without going through a router. Etc, etc. Additionally separate arcs and nodes could use either of the two methods above, i.e. all nodes and all arcs have a list of links ... In this case it's indistinguishable at the representation level except for the fact that in one case the bit distinguishing arcs from nodes is in the type and in the other it's an attribute... why are these different? Right. They both walk like ducks, quack like ducks, etc... So, I think the argument isn't over anything substantial, but rather over the semantics of what we call the various frobs with attributes and at what levels they get distinguished in their pourpose. Yes. I expect that, in actual application, there will be lots of attributes in these frobs that are not actually used in route generation Yes, I talked about that. as a network operator, one of the attributes *I* want in the frob representing the line from Cambridge to DC is the circuit number, but only in the version of the map that I *don't* give out :-) That's an interesting problem we haven't talked about. One way to do it is to encrypt such attributes, so that although everyone can get them, they can't read them. To have some that you don't pass out is a little tricker, although if we have an attribute language, one of the attributes could be an "envelope" attribute that says "don't give this attribute out to anyone who shouldn't see it" (a form of information hiding policies, now that I think about it). Actually, we ought to have another "envelope" attribute that says "this attribute is not useful for making routing decisions", to allow path selection algorithms to quickly skip over such attributes, or, more likely, to delete them from maps used by path selection. Noel   Received: from PIZZA.BBN.COM by BBN.COM id aa12636; 10 Jan 95 15:18 EST Received: from pizza by PIZZA.BBN.COM id aa27736; 10 Jan 95 14:50 EST Received: from BBN.COM by PIZZA.BBN.COM id aa27731; 10 Jan 95 14:49 EST Received: from ginger.lcs.mit.edu by BBN.COM id aa09655; 10 Jan 95 14:39 EST Received: by ginger.lcs.mit.edu id AA07760; Tue, 10 Jan 95 14:38:26 -0500 Date: Tue, 10 Jan 95 14:38:26 -0500 From: Noel Chiappa Message-Id: <9501101938.AA07760@ginger.lcs.mit.edu> To: dab@epilogue.com, nimrod-wg@BBN.COM Subject: Re: Open map questions Cc: jnc@ginger.lcs.mit.edu From: Dave Bridgham > the more I think about it, the more S-expressions are the way to go for > representing attributes! :-) Do I sense a convert? Well, to the general concept of an attribute syntax that can contain arbitrary nestings, tree structures, etc, yes. To representing them in ASCII, no (or at least, not yet). I also used s-expressions but I'm sure it could easily be converted to many other, less powerful, representations. :-) Whether the structure is *represented* in binary or ASCII is not really very important. Whether it can express everything as concisely and flexibly, in terms of the *underlying information structure*, is. In this example, each proper noun would really be a locator. The locator of an object is an attribute too, I think. Also, I can tell from context when additional terms in an expression in your examples are constituents, and when they are attributes, but we'd need to formalize this. Here's a question: do we want to be able to list contituents only by refernce (which means everything has to have a locator), or in some cases directly (as you have done). (You can't use just direct inclusion, since there's no way to represent structures like cycles that way)? I'm not sure I see a good use for the second, and it's more complication; if so, away with it! :-) I didn't include any hosts because I didn't want to type that much, but in fact I think the hosts should show up in the maps too. I blow hot and cold on this. In general, there's no need: if I'm attached to network X, and my locator is {A,B,C,...X,}, a router attached to X can forward packets to me with nothing more than my locator. I'm also a little uneasy about having to register yourself in a map, or with a router, before you can get data. I understand that running a router-host protocol has some benefits; you can fix black-hole disease, etc. I'd like to keep the base map description language no more complex than this. Yup, but we're already talking about adding quite a few "operators", such as: (or ... ) -> for disjoint attributes (inc-connspec ... ) -> for connectivity (exc-connspec ... ) -> specifiers (ignore ... ) -> for info not needed for path sel (restrict ... ) -> for putting "hidden" info in The basic language (which supports arbitrary nestings, tree structures, etc) is pretty simple, but it's going to have lots of complex operators. Noel   Received: from PIZZA.BBN.COM by BBN.COM id aa14882; 10 Jan 95 15:33 EST Received: from pizza by PIZZA.BBN.COM id aa27877; 10 Jan 95 15:14 EST Received: from BBN.COM by PIZZA.BBN.COM id aa27873; 10 Jan 95 15:04 EST Received: from ginger.lcs.mit.edu by BBN.COM id aa10710; 10 Jan 95 14:52 EST Received: by ginger.lcs.mit.edu id AA07880; Tue, 10 Jan 95 14:52:41 -0500 Date: Tue, 10 Jan 95 14:52:41 -0500 From: Noel Chiappa Message-Id: <9501101952.AA07880@ginger.lcs.mit.edu> To: dab@epilogue.com, jhalpern@newbridge.com Subject: Re: Open map questions Cc: jnc@ginger.lcs.mit.edu, nimrod-wg@BBN.COM From: Joel Halpern From having maintained LISP interpretters Ooooh, real-world experience. I'm not sure we can allow that here in the halls of Nimrod academia! :-) I tend not to think of S-Expressions as an easy thing for computers to parse. The underlying parsing processing code was "interesting". Yeah, but LISP has all sorts of syntactic kludges, like quote, back-quote, and all the jazz. Simple S-expressions would probably be somewhat easier... This note is prompted by trying to figure out why I want nested TLVs, which are formally equivalent to S-Expressions. Yes, that's what important. As long as they are equally powerful, in terms of the information fabrics and relationships they can express, that's what critical. The actual representation is secondary. My reasoning is that If I have a numeric type code, and a length then: 1) I can add some tags on the type code to describe the processing for unknown types Yes, but you can do the same thing if you start all S-expression string atoms with a subfield (delineated by "-", say) which does the same thing. 2) The length makes skipping entries eisier True, but again, we could add such a mandatory field to the S-expressions. 3) The type code will drive the parsing of the contents. Yes, but that just means that you've saved a binding step, to look up the string atom and translate it to some value you do your "switch" statement on. The processing efficiency is not to be sneezed at, of course (says the person who yesterday was counting memory references :-), which may be the best reason to pick TLV's over ASCII S-Expressions. For cases where the contents are a repeated list, one can include as part of the value a count, and then the repeated entries. True, but again, we could add such a mandatory field to the S-expressions. Or to put it another way, computers don't read ASCII strings very well. Yes and no. We use ASCII when it suits the overall system goals (e.g. they seem to read C programs pretty well). But your unspoken thrust is correct; unless there is a good reason to prefer ASCII, probably the operational efficiency of TLV's (getting rid of the ASCII->something binding stage) is reason to prefer them. Since these maps are going to be directly read by automatons far more than they are by humans, I'd say we go with what make best sense for the automatons, i.e. TLV's. Noel   Received: from PIZZA.BBN.COM by BBN.COM id aa16769; 10 Jan 95 15:57 EST Received: from pizza by PIZZA.BBN.COM id aa28035; 10 Jan 95 15:28 EST Received: from BBN.COM by PIZZA.BBN.COM id aa28031; 10 Jan 95 15:25 EST Received: from ginger.lcs.mit.edu by BBN.COM id aa12087; 10 Jan 95 15:09 EST Received: by ginger.lcs.mit.edu id AA08123; Tue, 10 Jan 95 15:09:44 -0500 Date: Tue, 10 Jan 95 15:09:44 -0500 From: Noel Chiappa Message-Id: <9501102009.AA08123@ginger.lcs.mit.edu> To: kasten@ftp.com, nimrod-wg@BBN.COM Subject: Re: One place to simplify Cc: jnc@ginger.lcs.mit.edu From: kasten@ftp.com (Frank Kastenholz) One of us is very confused. Mathematically, there's another possibilty, which is at least one! :-) I read your comment ... to imply that the opening of the transport connection (eg, the syn/syn-ack/ack of TCP) to serve as the e2e ACK that the flow was properly set up. Yes. So, if I set up a flow and use a connectionless transport over that flow (such as a udp-based audiocast) there is no transport setup ACK (i.e. no connection-open ack) to serve as the flow setup ACK. Ah. OK, but if you're sending audio to someone, there is *never* any ack that the data you're about to send is actually going somewhere useful, and not into a bit bucket? That's pretty odd. Still, assuming there really are applications where you don't have *any* higher level ack, then that's when you could ask for an optional flow-setup ack, so maybe we do need an optional end-end flow-setup ack. I dunno, the concept of any application (other than radio-like multicast listening, and even there, there's an implicit ack, in that you expect to start getting a data stream) *never* getting an ack is really pretty bizarre. I've heard of it in military em-con environments, principally naval, but it's pretty unusual. Noel   Received: from PIZZA.BBN.COM by BBN.COM id aa16797; 10 Jan 95 15:58 EST Received: from pizza by PIZZA.BBN.COM id aa28044; 10 Jan 95 15:31 EST Received: from BBN.COM by PIZZA.BBN.COM id aa28040; 10 Jan 95 15:27 EST Received: from quern.epilogue.com by BBN.COM id aa12145; 10 Jan 95 15:11 EST From: Dave Bridgham Sender: dab@epilogue.com To: nimrod-wg@BBN.COM In-reply-to: Noel Chiappa's message of Tue, 10 Jan 95 14:38:26 -0500 <9501101938.AA07760@ginger.lcs.mit.edu> Subject: Open map questions Date: Tue, 10 Jan 95 15:10:05 -0500 Message-ID: <9501101510.aa25363@quern.epilogue.com> Date: Tue, 10 Jan 95 14:38:26 -0500 From: Noel Chiappa The locator of an object is an attribute too, I think. That's possible but I prefer my approach. Also, I can tell from context when additional terms in an expression in your examples are constituents, and when they are attributes, but we'd need to formalize this. I don't know what you mean by a "constituent". The format I used was very regular. (map-name (node-name (attribute-name ) (attribute-name )) (node-name (attribute-name ) (attribute-name ))) I used string names for map-name and node-name but I expect those to actually be locators. That was the whole of the base language and that's what I wanted to keep simple. I understand that the list of attribute names will get long over time and what can be placed in is completely open ended for now (limited only by what our choice of language lets us represent). Here's a question: do we want to be able to list contituents only by refernce (which means everything has to have a locator), or in some cases directly (as you have done). Is a "constituent" a node? I meant to reference all nodes by locator. That's what I meant when I said at the top that all proper nouns were really locators. I blow hot and cold on this [hosts in maps]. In general, there's no need: if I'm attached to network X, and my locator is {A,B,C,...X,}, a router attached to X can forward packets to me with nothing more than my locator. I'm also a little uneasy about having to register yourself in a map, or with a router, before you can get data. I want the hosts in the maps because, as you might see in my example, I see no good reason to break a small net like Epilogue (or even a rather larger one) into more than one aggregate. So there's no information in a host's locator to tell anyone which Epilogue subnet a host is on. But I also believe nimrod should be able to support both methods of operation and we'll find out what people run when given the choice. I'd like to keep the base map description language no more complex than this. Yup, but we're already talking about adding quite a few "operators", such as: (or ... ) -> for disjoint attributes (inc-connspec ... ) -> for connectivity (exc-connspec ... ) -> specifiers (ignore ... ) -> for info not needed for path sel (restrict ... ) -> for putting "hidden" info in I think I wouldn't do that. I've already argued against connectivity specifications. The operator (ignore ... ) doesn't seem useful. Whoever is doing path selection will include or ignore whichever attributes it wants. Disjoint attributes - hadn't thought of that one. Might be useful. Could also be done by multiple nodes but that has problems. Don't understand (restrict ...). By "hidden" I assume you mean not transmitted in the map transfer. So then why do we need to spec it as part of the map language? The basic language (which supports arbitrary nestings, tree structures, etc) is pretty simple, but it's going to have lots of complex operators. Okay, I agree. Dave   Received: from PIZZA.BBN.COM by BBN.COM id aa21239; 10 Jan 95 17:02 EST Received: from pizza by PIZZA.BBN.COM id aa28588; 10 Jan 95 16:46 EST Received: from BBN.COM by PIZZA.BBN.COM id aa28584; 10 Jan 95 16:42 EST Received: from GAAK.BBN.COM by BBN.COM id aa19485; 10 Jan 95 16:35 EST Date: Tue, 10 Jan 1995 16:35:40 EST Message-ID: To: jhalpern@newbridge.com CC: dab@epilogue.com, nimrod-wg@BBN.COM In-reply-to: <9501101629.AA00134@lobster.Newbridge.COM> (message from Joel Halpern on Tue, 10 Jan 1995 11:29:26 +0500) Subject: Re: Open map questions From: "Michael A. Patton" Reply-To: "Michael A. Patton, general reply address" Date: Tue, 10 Jan 1995 11:29:26 +0500 From: Joel Halpern Or to put it another way, computers don't read ASCII strings very well. When I heard the suggestion of s-expressions for representing this, I was whole heartedly in favor, but I NEVER thought that meant sending actual ASCII text strings between machines (internal to the NIMROD routing[*]). I envisioned a representation like CDR-coded lists or count enumerated lists would be adopted for the wire protocol between machines. These don't require any parsing (at least not in the same sense). I am very much in favor of s-expressions and pretty much opposed to sending ASCII. -MAP [*] If we do think about these in terms of a printed rep, there may be a reason for higher level things (like user interfaces on routing debuggers) to see it in this form. But, I expect pretty-printing the internal form would be good enough, and eliminate the need for passing around anything but the internal form.   Received: from PIZZA.BBN.COM by BBN.COM id aa24389; 10 Jan 95 17:39 EST Received: from pizza by PIZZA.BBN.COM id aa28871; 10 Jan 95 17:17 EST Received: from BBN.COM by PIZZA.BBN.COM id aa28866; 10 Jan 95 17:15 EST Received: from quern.epilogue.com by BBN.COM id aa21708; 10 Jan 95 17:10 EST From: Dave Bridgham Sender: dab@epilogue.com To: nimrod-wg@BBN.COM In-reply-to: "Michael A. Patton"'s message of Tue, 10 Jan 1995 16:35:40 EST Subject: Open map questions Date: Tue, 10 Jan 95 17:09:45 -0500 Message-ID: <9501101709.aa26323@quern.epilogue.com> First, understand that I'm not defending ASCII real hard. I mean, it's what I'd choose if I were doing it on my own but it sounds like I've been successful in getting the semantics of s-expressions through even if you all want to invent your own encoding. I'm happy. But as for ASCII, I really don't think it's as bad as you're saying. It's going to be larger than a well done binary encoding, maybe three or four times larger (though I don't think it's quite that bad), but I certainly hope that nimrod traffic is never more than a tiny percentage of the capacity of the net. Whatever encoding you use there needs to be an encoding and a decoding step. I don't believe ASCII encoding and decoding is especially worse than any other. There are tradeoffs of course and when you have a really good idea of your data you can do things like fixed length fields with maybe byte swapping being the only encoding/decoding step you need and you win really big. If you don't have those data restrictions then I don't think other encodings are going to be significantly better than ASCII. With ASCII, I can use a language that's already specified and has been debugged for many years. It was sort of amusing to watch the IMAP folks start with basically s-expressions except they'd changed them enough that they kept running into ambiguities in their spec. I'm basically lazy and feel no great urge to redo that work until I've built the demo system and find that it's too slow after all. In this case I wouldn't expect that but if it happened THEN I'd put the effort into inventing my own encoding. The argument for a TLV encoding - that you want the length so you can skip over things when you can decide early on that you don't care - is a good one. I don't know yet how common that will be but it's a good thing to keep in mind. An argument that I've thought of and havn't heard anyone say yet has to do with security. With simple ASCII representations it is trivial to represent the same map in many different ways. If the originator of a map wants to crypto-sign it, then each cache of the map would have to keep the original bits they received and couldn't just keep the signature and regenerate the map from their internal representation. Dave   Received: from PIZZA.BBN.COM by BBN.COM id aa19743; 11 Jan 95 17:57 EST Received: from pizza by PIZZA.BBN.COM id aa07751; 11 Jan 95 17:01 EST Received: from KARIBA.BBN.COM by PIZZA.BBN.COM id aa07747; 11 Jan 95 16:57 EST To: nimrod-wg@BBN.COM Subject: Revised Architecture Document Date: Wed, 11 Jan 95 16:59:42 -0500 From: Isidro Castineyra Here is an updated version of the architecture. Main changes: arcs have been demoted to be attributes of nodes; arcs do no have locators. Also, some cleaning up. Please comment. Isidro -------------------- Internet Draft I. Castineyra Nimrod J. N. Chiappa January 1995 M. Steenstrup ?draft-ietf-nimrod-arch-00.txt? Expires July 1995 The Nimrod Routing Architecture 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 We present a scalable internetwork routing architecture, called Nimrod. The Nimrod architecture is designed to accommodate a dynamic internetwork of arbitrary size with heterogeneous service requirements and restrictions and to admit incremental deployment throughout an internetwork. The key to Nimrod's scalability is its ability to represent and manipulate routing-related information at multiple levels of abstraction. Internet Draft Nimrod Architecture July 1994 Contents 1 Introduction 1 2 Overview 1 2.1 Constraints of the Internetworking Environment . . . . . . . . . . 2 2.2 The Basic Routing Functions . . . . . . . . . . . . . . . . . . . . 3 2.3 Scalability Features . . . . . . . . . . . . . . . . . . . . . . . 5 2.3.1Clustering and Abstraction . . . . . . . . . . . . . . . . . . . 5 2.3.2Restricting Information Distribution . . . . . . . . . . . . . . 6 2.3.3Local Selection of Feasible Routes . . . . . . . . . . . . . . . 6 2.3.4Caching . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.3.5Limiting Forwarding Information . . . . . . . . . . . . . . . . 7 3 Architectural Overview 7 3.1 Endpoints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.2 Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.2.1Connectivity Specifications . . . . . . . . . . . . . . . . . . 9 3.3 Nodes and Arcs . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.4 BTEs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.5 Locators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.6 Node Attributes . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.6.1Arcs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.6.2Internal Maps . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.6.3Transit Connectivity . . . . . . . . . . . . . . . . . . . . . . 11 3.6.4Inbound Connectivity . . . . . . . . . . . . . . . . . . . . . . 12 3.6.5Outbound Connectivity . . . . . . . . . . . . . . . . . . . . . 12 i Internet Draft Nimrod Architecture July 1994 4 Physical Realization 12 4.1 Contiguity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 4.2 An Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 4.3 Multiple Locator Assignment . . . . . . . . . . . . . . . . . . . . 14 5 Forwarding 20 5.1 Policy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 5.2 Trust . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 5.3 Connectivity Specification (CSC) Mode . . . . . . . . . . . . . . . 22 5.4 Flow Mode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 5.5 Datagram Mode . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 6 Connectivity Specification Sequence Mode 26 7 Renumbering 26 8 Security Considerations 27 9 Authors' Addresses 27 ii Internet Draft Nimrod Architecture July 1994 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. In this document, we present a detailed description of this architecture. The goals of Nimrod are as follows: 1. To support a dynamic internetwork of arbitrary size by providing mechanisms to control the amount of routing information that must be known throughout an internetwork. 2. To provide service-specific routing in the presence of multiple constraints imposed by service providers and users. 3. To admit incremental deployment throughout an internetwork. We have designed the Nimrod architecture to meet these goals. The key features of this architecture include: 1. Representation of internetwork connectivity and services in the form of maps at multiple levels of abstraction. 2. User-controlled route generation and selection based on maps and traffic service requirements. 3. User-directed packet forwarding along established paths. Nimrod is a general routing architecture that can be applied to routing both within a single routing domain and among multiple routing domains. As a general internetwork routing architecture designed to deal with increased internetwork size and diversity, Nimrod is equally applicable to both the TCP/IP and OSI environments. 2 Overview Before describing the Nimrod architecture in detail, we provide an overview. We begin with the internetworking requirements, followed by the routing functions, and concluding with Nimrod's scaling characteristics. 1 Internet Draft Nimrod Architecture July 1994 2.1 Constraints of the Internetworking Environment Internetworks are growing and evolving systems, in terms of number, diversity, and interconnectivity of service providers and users, and therefore require a routing architecture that can accommodate internetwork growth and evolution. A complicated mix of factors such as technological advances, political alliances, and service supply and demand economics will determine how an internetwork will change over time. However, correctly predicting all of these factors and all of their effects on an internetwork may not be possible. Thus, the flexibility of an internetwork routing architecture is its key to handling unanticipated requirements. In developing the Nimrod architecture, we first assembled a list of internetwork environmental constraints which have implications for routing. This list, enumerated below, includes observations about the present Internet; it also includes predictions about internetworks five to ten years in the future. 1. The Internet will grow to include O(10^9) networks. 2. The number of internetwork users may be unbounded. 3. The capacity of internetwork resources is steadily increasing but so is the demand for these resources. 4. Routers and hosts have finite processing capacity and finite memory, and networks have finite transmission capacity. 5. Internetworks comprise different types of communications media -- including wireline and wireless, terrestrial and satellite, shared multiaccess and point-to-point -- with different service characteristics in terms of throughput, delay, error and loss distributions, and privacy. 6. Internetwork elements -- networks, routers, hosts, and processes -- may be mobile. 7. Service providers will specify offered services and restrictions on access to those services. Restrictions may be in terms of when a service is available, how much the service costs, which users may subscribe to the service and for what purposes, and how the user must shape its traffic in order to receive a service guarantee. 8. Users will specify traffic service requirements which may vary widely among sessions. These specifications may be in terms of requested qualities of service, the amounts they are willing to pay for these services, the times at which they want these services, and the providers they wish to use. 2 Internet Draft Nimrod Architecture July 1994 9. A user traffic session may include m sources and n destinations, where m, n > or = 1. 10. Service providers and users have a synergistic relationship. That is, as users develop more applications with special service requirements, service providers will respond with the services to meet these demands. Moreover, as service providers deliver more services, users will develop more applications that take advantage of these services. 11. Support for varied and special services will require more processing, memory, and transmission bandwidth on the part of both the service providers offering these services and the users requesting these services. Hence, many routing-related activities will likely be performed not by routers and hosts but rather by independent devices acting on their behalf to process, store, and distribute routing information. 12. Users requiring specialized services (e.g., high guaranteed throughput) will usually be willing to pay more for these services and to incur some delay in obtaining them. 13. Service providers are reluctant to introduce complicated protocols into their networks, because they are more difficult to manage. 14. Vendors are reluctant to implement complicated protocols in their products, because they take longer to develop. Collectively, these constraints imply that a successful internetwork routing architecture must support special features, such as service-specific routing and component mobility in a large and changing internetwork, using simple procedures that consume a minimal amount of internetwork resources. We believe that the Nimrod architecture meets these goals, and we justify this claim in the remainder of this document. 2.2 The Basic Routing Functions The basic routing functions provided by Nimrod are those provided by any routing system, namely: 1. Collecting, assembling, and distributing the information necessary for route generation and selection. 2. Generating and selecting routes based on this information. 3. Establishing in routers information necessary for forwarding packets along the selected routes. 3 Internet Draft Nimrod Architecture July 1994 4. Forwarding packets along the selected routes. The Nimrod approach to providing this routing functionality includes map distribution according to the "link-state" paradigm, localization of route generation and selection at traffic sources and destinations, and specification of packet forwarding through path establishment by the sources and destinations. Link-state map distribution permits each service provider to have control over the services it offers, through both distributing restrictions in and restricting distribution of its routing information. Restricting distribution of routing information serves to reduce the amount of routing information maintained throughout an internetwork and to keep certain routing information private. However, it also leads to inconsistent routing information databases throughout an internetwork, as not all such databases will be complete or identical. We expect routing information database inconsistencies to occur often in a large internetwork, regardless of whether privacy is an issue. The reason is that we expect some devices to be incapable of maintaining the complete set of routing information for the internetwork. These devices will select only some of the distributed routing information for storage in their databases. Route generation and selection, based on maps and traffic service requirements, may be completely controlled by the users or, more likely, by devices acting on their behalf and does not require global coordination among routers. Thus these devices may generate routes specific to the users' needs, and only those users pay the cost of generating those routes. Locally-controlled route generation allows incremental deployment of and experimentation with new route generation algorithms, as these algorithms need not be the same at each location in an internetwork. Packet forwarding, according to paths, may be completely controlled by the users or the devices acting on their behalf. These paths may be specified in as much detail as the maps permit. Such packet forwarding provides freedom from forwarding loops, even when routers in a path have inconsistent routing information. The reason is that the forwarding path is a route computed by a single device and based on routing information maintained at a single device. We note that the Nimrod architecture and Inter-Domain Policy Routing (IDPR) [2] share in common link-state routing information distribution, localized route generation and path-oriented message forwarding. In developing the Nimrod architecture, we have drawn upon experience gained in developing and experimenting with IDPR. 4 Internet Draft Nimrod Architecture July 1994 2.3 Scalability Features Nimrod must provide service-specific routing in arbitrarily large internetworks and hence must employ mechanisms that help to contain the amount of internetwork resources consumed by the routing functions. We provide a brief synopsis of such mechanisms below, noting that arbitrary use of these mechanisms does not guarantee a scalable routing architecture. Instead, these mechanisms must be used wisely, in order enable a routing architecture to scale with internetwork growth. 2.3.1 Clustering and Abstraction The Nimrod architecture is capable of representing an internetwork as clusters of entities at multiple levels of abstraction. Clustering reduces the number of entities visible to routing. Abstraction reduces the amount of information required to characterize an entity visible to routing. Clustering begins by aggregating internetwork elements such as hosts, routers, and networks according to some predetermined criteria. These elements may be clustered according to relationships among them, such as "managed by the same authority", or so as to satisfy some objective function, such as "minimize the expected amount of forwarding information stored at each router". Nimrod does not mandate a particular cluster formation algorithm. New clusters may be formed by clustering together existing clusters. Repeated clustering of entities produces a hierarchy of clusters with a unique universal cluster that contains all others. The same clustering algorithm need not be applied at each level in the hierarchy. All elements within a cluster must satisfy at least one relation, namely connectivity. That is, if all elements within a cluster are operational, then any two of them must be connected by at least one route that lies entirely within that cluster. This condition prohibits the formation of certain types of separated clusters, such as the following. Suppose that a company has two branches located at opposite ends of a country and that these two branches must communicate over a public network not owned by the company. Then the two branches cannot be members of the same cluster, unless that cluster also includes the public network connecting them. Once the clusters are formed, their connectivity and service information is abstracted to reduce the representation of cluster characteristics. Example abstraction procedures include elimination of services provided by a small fraction of the elements in the cluster or expression of services in terms of average values. Nimrod does not mandate a particular abstraction algorithm. The same abstraction algorithm need not be applied to each cluster, and multiple abstraction algorithms may be applied to a single cluster. 5 Internet Draft Nimrod Architecture July 1994 A particular combination of clustering and abstraction algorithms applied to an internetwork results in an organization related to but distinct from the physical organization of the component hosts, routers, and networks. When a clustering is superimposed over the physical internetwork elements, the cluster boundaries may not necessarily coincide with host, router, or network boundaries. Nimrod performs its routing functions with respect to the hierarchy of entities resulting from clustering and abstraction, not with respect to the physical realization of the internetwork. In fact, Nimrod need not even be aware of the physical elements of an internetwork. 2.3.2 Restricting Information Distribution The Nimrod architecture supports restricted distribution of routing information, both to reduce resource consumption associated with such distribution and to permit information hiding. Each cluster determines the portions of its routing information to distribute and the set of entities to which to distribute this information. Moreover, recipients of routing information are selective in which information they retain. Some examples are as follows. Each cluster might automatically advertise its routing information to its siblings (i.e., those clusters with a common parent cluster). In response to requests, a cluster might advertise information about specific portions of the cluster or information that applies only to specific users. A cluster might only retain routing information from clusters that provide universal access to their services. 2.3.3 Local Selection of Feasible Routes Generating routes that satisfy multiple constraints is usually an NP-complete problem and hence a computationally intensive procedure. With Nimrod, only those entities that require routes with special constraints need assume the computational load associated with generation and selection of such routes. Moreover, the Nimrod architecture allows individual entities to choose their own route generation and selection algorithms and hence the amount of resources to devote to these functions. 2.3.4 Caching The Nimrod architecture encourages caching of acquired routing information in order to reduce the amount of resources consumed and delay incurred in obtaining the information in the future. The set of routes generated as a by-product of generating a particular route is an example of routing information that is amenable to caching; future requests for any of these routes may be satisfied directly from the route cache. However, as with any caching scheme, the cached information may become stale and its use may result in poor quality routes. Hence, the routing information's expected 6 Internet Draft Nimrod Architecture July 1994 duration of usefulness must be considered when determining whether to cache the information and for how long. 2.3.5 Limiting Forwarding Information The Nimrod architecture supports two separate approaches for containing the amount of forwarding information that must be maintained per router. The first approach is to multiplex, over a single path (or tree, for multicast), multiple traffic flows with similar service requirements. The second approach is to install and retain forwarding information only for active traffic flows. With Nimrod, the service providers and users share responsibility for the amount of forwarding information in an internetwork. Users have control over the establishment of paths, and service providers have control over the maintenance of paths. This approach is different from that of the current Internet, where forwarding information is established in routers independent of demand for this information. 3 Architectural Overview Nimrod is a hierarchical, map-based routing architecture that has been designed to support a wide range of user requirements and to scale to very large dynamic internets. Given a traffic stream's description and requirements (both quality of service requirements and usage-restriction requirements), Nimrod's main function is to manage in a scalable fashion how much information about the internetwork is required to choose a route for that stream. In other words, to manage the trade-off between amount of information about the internetwork and the quality of the computed route. Nimrod is implemented as a set of protocols and distributed databases. The following sections describe the basic architectural concepts used in Nimrod. The protocols and databases are specified in other documents. 3.1 Endpoints The basic entity in Nimrod is the endpoint. An endpoint represents a user of the internetwork layer: for example, a transport connection. Each endpoint has at least one endpoint identifier (EID). Any given EID corresponds to a single endpoint. EIDs are globally unique, relatively short "computer-friendly" bit strings---for example, small multiples of 64 bits. EIDs have no topological significance whatsoever. For ease of management, EIDs might be organized hierarchically, but this is not required. 7 Internet Draft Nimrod Architecture July 1994 BEGIN COMMENT In practice, EIDs will probably have a second form, which we can call the endpoint label (EL). ELs are ASCII strings of unlimited length, structured to be used as keys in a distributed database (much like DNS names). Information about an endpoint---for example, how to reach it---can be obtained by querying this distributed database using the endpoint's label as key. END COMMENT 3.2 Maps The basic data structure used for routing is the map. A map expresses the available connectivity between different points of an internetwork. Different maps can represent the same region of a physical network at different levels of detail. A map is a graph composed of nodes and arcs. Properties of nodes are contained in attributes associated with them. Arcs have no attributes. Arcs appear in maps as attributes of nodes. Nimrod defines languages to specify attributes and to describe maps. Maps are used by routers to generate routes. In general, it is not required that different routers have consistent maps. In this document we speak only of routers. By "router" we mean a physical device that implements functions related to routing: for example, forwarding, route calculation, path set-up. A given device need not be capable of doing all of these to be called a router. Later---for example, in protocol specification documents---it might be convenient to explicitly split these functionalities. We might then speak of forwarding engines, path set-up agents, route servers, etc. BEGIN COMMENT Nimrod has been designed so that there will be no routing loops even when the routing databases of different routers are not consistent. A consistency requirement would not permit representing the same region of the internetwork at different levels of detail. Also, a routing-database consistency requirement would be hard to guarantee in the very large internets Nimrod is designed to support. END COMMENT 8 Internet Draft Nimrod Architecture July 1994 3.2.1 Connectivity Specifications By connectivity between two points we mean the available services and the restrictions on their use. Connectivity specifications are among the attributes associated with nodes. The following are informal examples of connectivity specifications: o "Between these two points, there exists best-effort service with no restrictions." o "Between these two points, guaranteed 10 ms delay can be arranged for traffic streams whose data rate is below 1 Mbyte/sec and that have low (specified) burstiness." o "Between these two points, best-effort service is offered, as long as the traffic originates in and is destined to research organizations." BEGIN COMMENT Connectivity specifications can be defined not only between two points, but also between sets of points. Nimrod includes a language to define connectivity specifications. END COMMENT 3.3 Nodes and Arcs A node represents a region of the physical network. The region of the network represented by a node can be as large or as small as desired: a node can represent a continent or a process running inside a host. Moreover, as explained in section 4, a region of the network can simultaneously be represented by more than one node. Arcs are unidirectional. An arc has two distinguishable ends: a head and a tail. (Arcs are often visualized and drawn as arrows; the head of the arc corresponds to the head of the arrow.) The head and tail of an arc are each connected to a node. The presence of an arc between two nodes specifies that traffic can flow between those two points in the direction indicated by the arc (from tail to head). Between two given nodes, there can be only one arc in each direction. Arcs always connect different nodes. 9 Internet Draft Nimrod Architecture July 1994 3.4 BTEs The distinguishable components of a map are called basic topological entities (BTEs): nodes and connectivity specifications. 3.5 Locators A locator is a string of binary digits that identifies a basic topological entity (BTE) in a map. Different BTEs have necessarily different locators. A given BTE is assigned only one locator. Locators identify BTEs and specify *where* a BTE is in the network. Locators do *not* specify a path to the BTE. In this document locators are written as ASCII strings that include colons to underline node structure: for example, a:b:c. This does not mean that the representation of locators in packets or in databases will necessarily have something equivalent to the colons. A given physical element of the network might implement more than one BTE---for example, a router that is part of two different nodes. Though this physical element might therefore be associated with more than one locator, the BTEs that this physical element implements have each only one locator. A node is said to own those locators that have as a prefix the locator of the node. In a node that has an internal map, the locators of all BTEs in this internal map are prefixed by the locator of the original node. Specifically, the locators of nodes appearing in the internal map of a node are prefixed by the locator of that node. Arcs do not have locators. The locators of all connectivity specifications associated with a node are also prefixed by the node's locator. All routing map information is expressed in terms of locators, and routing selections are based on locators. EIDs are *not* used in making routing decisions---see section 5. 3.6 Node Attributes The following are node attributes defined by Nimrod. 10 Internet Draft Nimrod Architecture July 1994 3.6.1 Arcs Arcs appear in maps as attributes of their tail node---the "from" node. Every arc associated with a node identifies a neighboring node to which the original node can send data to. Given a node, an "adjacent source" is a node that can send data to the original node. That is, a node that has an arc with the original node as its head. Similarly, an "adjacent destination" is a node to which the original node can send data. That is, a node that is the head of one of the orignal node's arcs. 3.6.2 Internal Maps As part of its attributes, a node can have internal maps. A router can obtain a node's internal maps---or any other of the node's attributes, for that matter---by requesting that information from a representative of that node. (A router associated with that node can be such a representative.) A node's representative can in principle reply with different internal maps to different requests---for example, because of security concerns. This implies that different routers in the network might have different internal maps for the same node. Given a map, a router can obtain a more detailed map by substituting one of the map's nodes by one of that node's internal maps. This process can be continued recursively. (Presumably, a router would expand nodes in the region of the map of its current interest.) Nimrod defines standard internal maps that are intended to be used for specific purposes. A node's "detailed map" gives more information about the region of the network represented by the original node. Typically, it is closer to the physical realization of the network than the original node. The nodes of this map can themselves have detailed maps. 3.6.3 Transit Connectivity For a given node, this attribute specifies the services available between adjacent sources and adjacent destinations. This attribute is requested and used when a router intends to route traffic *through* a node. Conceptually, the traffic connectivity attribute is a matrix that is indexed by a pair of locators: the locator of an adjacent source and the locator of an adjacent destination. The entry indexed by such a pair contains the connectivity specifications of the services available across the given node for traffic entering from the adjacent source going to the adjacent destination. The actual format of this attribute need not be a matrix. This document does not specify the format for this attribute, nor for the next two attributes. 11 Internet Draft Nimrod Architecture July 1994 3.6.4 Inbound Connectivity For a given node, this attribute represents connectivity from adjacent sources to points within the node. This attribute is requested and used when a router intends to route traffic to a point within the node but does not have, and either cannot or does not want to obtain, a detailed map of the node. The inbound connectivity attribute identifies what connectivity specifications are available between pairs of locators. The first element of the pair is the locator of an adjacent source, node, the second is a locator owned by the node. 3.6.5 Outbound Connectivity For a given node, this attribute represents connectivity from points within the node to adjacent destinations. This attribute identifies what connectivity specifications are available between pairs of locators. The first element of the pair is a locator owned by the node, the second is the locator of an adjacent destination. 4 Physical Realization A network is modeled as being composed of physical elements: routers, hosts, and communication links. The links can be either point-to-point---e.g., T1 links---or multi-point---e.g., ethernets, X.25 networks, IP-only networks, etc. The physical representation of a network can have associated with it one or more Nimrod maps. A Nimrod map is a function not only of the physical network, but also of the configured clustering of elements (locator assignment) and of the configured connectivity. Nimrod has no pre-defined "lowest level": for example, it is possible to define and advertise a map that is physically realized inside a CPU. In this map, a node could represent, for example, a process or a group of processes. The user of this map need not necessarily know or care. ("It is turtles all the way down!", in [3] page 63.) 4.1 Contiguity Locators sharing a prefix must be assigned to a contiguous region of a map. That is, two elements (BTEs) of a map that have been assigned locators sharing a prefix should be connected to each other with elements that themselves have been assigned locators with that prefix. The main consequence of this requirementD is that "you cannot take your locator with 12 Internet Draft Nimrod Architecture July 1994 you." As an example of this, see figure 1, consider two providers x.net and y.net (these designations are *not* locators but DNS names) which appear in a Nimrod map as two nodes with locators A and B. Assume that corporation z.com (also not a locator) was originally connected to x.net. Locators corresponding to elements in z.com are, in this example, A-prefixed. Corporation z.com decides to change providers---severing its physical connection to x.net. The connectivity requirement described in this section implies that, after the provider change has taken place, elements in z.com will have been, in this example, assigned B-prefixed locators and that it is not possible for them to receive data destined to A-prefixed locators through y.net. The contiguity requirement simplifies routing information exchange: if it were permitted for z.com to receive A-prefixed locators through y.net, it would be necessary that a map that contains node B include information about the existence of a group of A-prefixed locators inside node B. Similarly, a map including node A would have to include information that the set of A-prefixed locators asigned to z.com is not to be found within A. The more situations like this happen, the more the hierarchical nature of Nimrod is subverted to "flat routing." The contiguity requirement can also be expressed as "EIDs are stable; locators are ephemeral." The contiguity requirement rules out some approaches to implementing mobility in Nimrod. For example, a mobile host cannot advertise its "home" locator from its new location. For more on mobility see [4]. 4.2 An Example Figure 2 shows a physical network. Hosts are drawn as squares, routers as diamonds, and communication links as lines. The network shown has the following components: five ethernets ---EA through EE; five routers---RA through RE; and four hosts---HA through HD. Routers RA, RB, and RC interconnect the backbone ethernets---EB, EC and ED. Router RD connects backbone EC to a network consisting of ethernet EA and hosts HA and HB. Router RE interconnects backbone ED to a network consisting of ethernet EE and hosts HC and HD. The assigned locators appear in lower case beside the corresponding physical entity. Figure 3 shows a Nimrod map for that network. The nodes of the map are represented as squares. Lines connecting nodes represent two arcs in opposite directions. Different regions of the network are represented at different detail. Backbone b1 is represented as a single node. The region of the network with locators prefixed by "a" is represented as a single node. The region of the network with locators prefixed by "c" is represented in full detail. 13 Internet Draft Nimrod Architecture July 1994 +-------+ +-------+ | | | | | x.net | | y.net | | | | | | | | | +-------+ +-------+ / / / / / / / +-------+ | | | z.com | | | | | +-------+ Figure 1: Connectivity after switching providers 4.3 Multiple Locator Assignment Physical elements can form part of, or implement, more than one BTE. In this sense it can be said that they can be assigned more than one locator. Consider figure 4, which shows a physical network. This network is composed of routers (RA, RB, RC, and RD), hosts (HA, HB, and HC), and communication links. Routers RA, RB, and RC are connected with point-to-point links. The two horizontal lines in the bottom of the figure represent ethernets. The figure also shows the locators assigned to hosts and routers. In figure 4, RA and RB have each been assigned one locator (a:t:r1 and b:t:r1, respectively). RC has been assigned locators a:y:r1 and b:d:r1; one of these two locators shares a prefix with RA's locator, the other shares a prefix with RB's locator. Hosts HA and HB have each been assigned three locators. Host HC has been assigned one locator. Depending on what communication paths have been set up between points, different Nimrod maps result. A possible Nimrod map for this network is given in figure 5. Nodes and arcs represent the *configured* clustering and connectivity of the network. Notice that even though a:y and b:d are defined on the same hardware, the map shows no connection between them: this connection has not been configured. A packet given to node `a' addressed to a locator prefixed 14 Internet Draft Nimrod Architecture July 1994 a:h1 +--+ a:h2 +--+ |HA| |HB| | | | | +--+ +--+ a:e1 | | --------------------- EA | /\ /\ /RB\ b1:r1 /RD\ b2:r1 /\ /\ \ / / \/ \ \/ EB b1:t:e1 / \ | EC ------------------------ -------------------------- b2:e1 / \ / \ /\ \ /RA\ b1:r2 \/\ \ / /RC\ b2:t:r2 \/ \ / \ \/ \ / ED ----------------------------------- b3:t:e1 | | | /\ /RE\ b3:t:r1 \ / EE \/ ----------------------------- c:e1 | | +--+ +--+ |HC| c:h1 |HD| c:h2 | | | | +--+ +--+ Figure 2: Example Physical Network 15 Internet Draft Nimrod Architecture July 1994 +-----+ +-----+ +----------+ | | | | | |--------------| b2:t| --------------| a | | | | | | | | b1 | +-----+ +-----+ | | | | | | | | | +----------+ | \ | \ | \ | \ | \ +--------+ \ | | ------- | b3:t:e1| | | +--------+ | | | | +-------+ | | |b3:t:r1| | | +-------+ | +-----+ +-----+ +-----+ | | | | | | | c:h1|-------| c:e1|-----| c:h2| | | | | | | +-----+ +-----+ +-----+ Figure 3: Nimrod Map 16 Internet Draft Nimrod Architecture July 1994 a:t:r1 b:t:r1 +--+ +--+ |RA|------------|RB| +--+ +--+ \ / \ / \ / \ / \ / \ / \ / \ +--+ |RC| a:y:r1 +--+ b:d:r1 | --------------------------- a:y:h1 +--+ +--+ +--+ a:y:h2 b:d:h2 |HA| |RD| c:r1 |HB| b:d:h1 c:h1 +--+ +--+ +--+ c:h2 | | -------------------- +--+ |HC| c:h3 +--+ Figure 4: Multiple Locators 17 Internet Draft Nimrod Architecture July 1994 a b c +-------------+ +-------------+ +---------------+ | | | | | | | a:t | | b:t | | | | +--+ | | +--+ | | | | | |--------------|--| | | | | | +--+ | | +--+ | | | | | | | | | | | | +--+ | | +--+ | | | | + + | | + + | | | | +--+ a:y | | +--+ b:d | | | | | | | | | +-------------+ +-------------+ +---------------+ Figure 5: Nimrod Map with "b:d" would have to travel from node a to node b via the arc joining them before being directed towards its destination. Similarly, the map shows no connection between the c node and the other two top level nodes. If desired, these connections could be established, which would necessitate setting up the exchange of routing information. Figure 6 shows the map when these connections have been established. In the strict sense, Nimrod nodes do not overlap: they are distinct entities. But, as we have seen in the previous example, a physical element can be given more than one locator, and, in that sense, participate in implementing more than one node. That is, two different nodes might be defined on the same hardware. In this sense, Nimrod nodes can be said to overlap. But to notice this overlap one would have to know the physical-to-map correspondence. It is not possible to know when two nodes share physical assets by looking only at a Nimrod map. BEGIN COMMENT A contiguous region of the network that is not Nimrod-aware can be represented as node with associated transit connectivity specifications that describe the connectivity offered by this region of the network. An example of this is an IP-only network that is connected to the Nimrod internetwork via Nimrod routers. Nimrod-aware hosts connected to this network are represented as nodes connected to this node. Nimrod packets destined for Nimrod hosts, or for Nimrod routers "on the other side of the network," could, for example, be encapsulated inside IP packets. IP-only hosts connected to this network can be reached from other IP-only clouds by, for example, encapsulating IP packets inside 18 Internet Draft Nimrod Architecture July 1994 +--------+ +--------+ | | | | | a:t:r1 |-----------------------------------------------| b:t:r1 | | | | | +--------+ +--------+ | | | | | /-----------------------------------------\ | | | | | | | | | | +--------+ +--------+ +--------+ | | | | | | | | | | | a:y:h1 --------| c:h1 |--------------------| b:d:h1 | | | | | | | | | | | +--------+ +--------+ +--------+ | | | | | | | | | +--------+ | | +------+ +------+ | +--------+ | | | | | | | | | | | | a:y:r1 | | | | c:r1 |--| c:h3 | | | b:d:r1 | | | | | | | | | | | | +--------+ | | +------+ +------+ | +--------+ | | | | | | | | | +--------+ +--------+ +--------+ | | | | | | | | | | | a:y:h2 |-------- c:h2 |--------------------| b:d:h2 | | | | | | | | | | | +--------+ +--------+ +--------+ | | | | | | | | | | | | | | \-----------------------------------------/ | \-------------------------------------------------------------/ Figure 6: Nimrod Map II 19 Internet Draft Nimrod Architecture July 1994 packets of the format being used by Nimrod. Nimrod routers connecting the IP network to the Nimrod internetwork would "de-capsulate" packets destined to IP-only hosts. IP-only hosts could, for example, be given locators prefixed by the locator of a Nimrod router that knows how to get packets to them, this way putting them "inside" the associated Nimrod router. Other treatments are possible: for example, they could be given locators prefixed with the locator of the node that represents the IP network. In the first case, "within" a router, only that router needs to know how to forward packets to IP hosts; however, this makes this router a single point of failure. In the second case, all Nimrod routers connected to this node need to know how to forward IP packets to IP-only hosts. To simplify packet forwarding, the locator for an IP-only host might include the IP address of the host. END COMMENT 5 Forwarding Nimrod does not specify a packet format. It is possible to use Nimrod with different formats, conceivably simultaneously, in the same network. This section specifies Nimrod's requirements on the packet-forwarding mechanism. Nimrod supports four forwarding modes: 1. Connectivity Specification Chain (CSC) mode: in this mode, packets carry a list of connectivity specification locators. The packet is required to go through the nodes that own the connectivity specifications using the services specified. The nodes associated with the listed connectivity specifications should define a continuous path in the map. A more detailed description of the requirements of this mode is given in section 5.3. 2. Connectivity Specifications Sequence (CSS) mode: in this mode, packets carry a list of connectivity specification locators. The packet is supposed to go sequentially through the nodes that own each one of the listed connectivity specifications in the order they were specified. The nodes need not be neighbours. This mode can be seen as a generalization of the CSC mode. Notice that CSCs are said to be a *chains* of locators, CSSs are *sequence* of locators. This difference emphasizes the contiguity requirement in CSCs. A detailed description of this mode is in section 6. 3. Flow mode: in this mode, the packet header includes a path-id that indexes state that has been previously set up in routers along the path. Packet forwarding when flow state has been established is relatively simple: follow the instructions in the routers' state. 20 Internet Draft Nimrod Architecture July 1994 Nimrod includes a mechanism for setting up this state. A more detailed description of this mode can be found in section 5.4. 4. Datagram mode: in this mode, every packet header carries source and destination locators. This mode can be seen as a special case of the CSS mode. Forwarding is done following procedures as indicated in section 5.5. BEGIN COMMENT The obvious parallels are between CSC mode and IPV4's strict source route and between CSS mode and IPV4's loose source route. END COMMENT In all of these modes, the packet header also carries locators and EIDs for the source and destinations. In normal operation, forwarding does not take the EIDs into account, only the receiver does. EIDs are carried for demultiplexing at the receiver, and to detect certain error conditions. For example, if the EID is unknown at the receiver, the locator and EID of the source included in the packet could be used to generate an error message to return to the source (as usual, this error message itself should probably not be allowed to be the cause of other error messages). Forwarding can also use the source locator and EID to respond to error conditions, for example, to indicate to the source that the state for a path-id cannot be found. Packets can be visualized as moving between nodes in a map. A packet's header indicates, implicitly or explicitly, a destination locator. In a packet that uses the datagram, CSC, or CSS forwarding mode, the destination locator is explicitly indicated in the header. In a packet that uses the flow forwarding mode, the destination locator is implied by the path-id and the distributed state in the network (it might also be included explicitly). Given a map, a packet moves to the node in this map to which the associated destination locator belongs. If the destination node has a "detailed" internal map, the destination locator must belong to one of the nodes in this internal map (otherwise it is an error). The packet goes to this node (and so on, recursively). 5.1 Policy CSC and CSS mode packets implement policy by specifying the connectivity specifications associated with those nodes that the packet should traverse. Strictly speaking, there is no policy information included in the packet header. That is, in principle, it is not possible to determine what criteria were used to select the route by looking at the header. The packet header only contains the results of the route generation process. 21 Internet Draft Nimrod Architecture July 1994 Similarly, in a flow mode packet, policy is implicit in the chosen route. A datagram-mode packet can indicate a limited form of policy routing by the choice of destination and source locators. For this choice to exist, the source or destination endpoints must have several locators associated with them. This type of policy routing is capable of, for example, choosing providers. 5.2 Trust A node that does not divulge its internal map can work internally any way its administrators decide, as long as the node satisfies its external characterization as given in its Nimrod map advertisements. Therefore, the advertised Nimrod map should be consistent with a node's actual capabilities. For example, consider the network shown in figure 7 which shows a physical network and the advertised Nimrod map. The physical network consists of hosts and a router connected together by an ethernet. This node can be sub-divided into component nodes by assigning locators as shown in the figure and advertising the map shown. The map seems to imply that it is possible to send packets to node a:x without these being observable by node a:y; however, this is actually not enforceable. In general, it is reasonable to ask how much trust should be put in the maps obtained by a router. Even when a node is "trustworthy," and the information received from the node has been authenticated, there is always the possibility of an honest mistake. These are difficult issues that are not unique to Nimrod. Many research and standards groups are addressing them. We plan to incorporate the output of these groups into Nimrod as they become available. 5.3 Connectivity Specification (CSC) Mode Routing for a CSC packet is specified by a list of locators carried in the packet header. The locators correspond to connectivity specifications that make the specified path, in the order that they appear along the path. These connectivity specifications are attributes of nodes. Note that the route indicated by a CSC packet is specifed in terms of connectivity specifications rather than physical entities: a locator in the CSC header could correspond to a type of service between two points of the network without specifying the physical path. Given two connectivity specification locators that appear consecutively in the header of a CSC mode packet, there should exist an arc going from the node corresponding to the first connectivity specification to the node corresponding to the second connectivity specification. The first connectivity specification referenced in a CSC mode header should be an outbound connectivity specification; similarly, the last connectivity 22 Internet Draft Nimrod Architecture July 1994 +--+ |RA| a:r1 +--+ | | | | ------------------------------- +--+ +--+ |Ha| a:x:h1 |Ha| a:y:h2 +--+ +--+ Physical Network a | +----------------|-------------------- | | | | +----+ | | |a:r1| | | a:x +----+ a:y | | +------+ / \ +-------+ | | | | / \| | | | | | | | | | | | | | | | +------+ +-------+ | | | + -----------------------------------+ Advertised Nimrod Map Figure 7: Example of Misleading Map 23 Internet Draft Nimrod Architecture July 1994 specification referenced in a CSC mode header should be an indicated connectivity specification; the rest should be transit connectivity specifications. 5.4 Flow Mode The header of a flow mode packet includes a path-id field. This field identifies state that has been established in intermediate routers. This header might also contain locators and EIDs for the source and destination. Nimrod includes protocols to set up and modify flow-related state in intermediate routers. These protocols not only identify the requested route, but also describe the resources requested by the flow---e.g., bandwidth, delay, etc. The result of a set-up attempt might be either confirmation of the set-up or notification of its failure. The source-specified routes in flow mode are specified in terms of CSCs. 5.5 Datagram Mode A realistic routing architecture must include an optimization for datagram traffic, by which we mean user transactions which consist of single packets, such as a lookup in a remote translation database. Either of the two previous modes contains unacceptable overhead if much of the network traffic consists of such datagram transactions. A mechanism is needed which is approximately as efficient as the existing IPV4 "hop-by-hop" mechanism. Nimrod has such a mechanism. The scheme can be characterized by the way it divides the state in a datagram network, between routers and the actual packets. Most packets currently contain only a small amount of state associated with the forwarding process ("forwarding state")---the hop count. Nimrod proposes that enlarging the amount of forwarding state in packets can produce a system with useful properties. It was partially inspired by the efficient source routing mechanism in SIP ( [5]), and the locator pointer mechanism in PIP ( [6]). Nimrod datagram mode uses pre-set flow-mode state to support a strictly non-looping path, but without a source-route. In the datagram mode, the packet contains, in addition to a locally usable path-id field: o the source and destination locators, and o a pointer into the locators. The pointer starts out at the lowest level of the source locator, and moves "up" that locator, then to the destination locator, and then "down". In 24 Internet Draft Nimrod Architecture July 1994 addition to these extra fields in the packet, all routers have to contain a minimal set of "pre-setup" flows, or be prepared to set these flows on demand, to certain routers which are at critical places in the abstraction hierarchy. The "pre-setup" flows do not actually have to be set up in advance, but can be created on demand. There is a minimum set of flows which do have to be *able* to be set up for the system to operate, however. It is purely a local decision, which, if any, of those flows to set up before there is an actual traffic requirement for them. As an efficiency move, when a datagram requires that a flow actually be set up to handle it, the data packet could be sent along with the flow setup request, avoiding the round-trip delay. We call these flows "datagram mode flows", or "DMFs", realizing that none of them need be created until actually needed. The actual operation of the mechanism is fairly simple. While going up the source locator, each "active" router (i.e., one that actually makes a decision about where to send the packet, as opposed to handling it as part of a flow) selects a DMF which will take the packet to the "next higher" level object in the source locator, advances the pointer, and sends the packet off along that DMF. When it gets to the end of that DMF, the process repeats, until the packet reaches a router which is at the least common intersection of the two locators. (e.g., for A:P:Q:R and A:X:Y:Z, this would be when the packet reaches A). The process then inverts, with each active router selecting a DMF which takes the packet to the next lower object in the destination locator. So, A would select a flow to A:X, and once it got to A:X, A:X would select a flow to A:X:Y, etc. It can easily be seen that the process guarantees that the resulting path is loop-free. Each flow selected must necessarily get the packet closer to its destination (since each flow selection results in the pointer being monotonically advanced through the locator), and the flows themselves are guaranteed not to loop when their paths are selected, prior to being set up. If the system keeps more than the minimal set of DMFs (which is just up to one border router in internal routers, and down to each object one level down for each border router), and keep the table sorted for efficient lookups (e.g., in much the same way as the current routing table for hop-by-hop datagrams), routing can be more efficient. For example, using the case above (a packet from A:P:Q:R to A:X:Y:Z), if A:P:Q is actually a neighbour to A:X:Y, and maintains a flow directly from A:P:Q to A:X:Y, then when the packet reaches A:P:Q, instead of going the rest of the way up and down, the pointer can be set into the destination locator at A:X:Y, and the packet sent there directly. Traffic monitoring and analysis (again, using purely local algorithms) can result in a database being created over time, which shows which DMFs above and beyond the minimal set are worth keeping around. This traffic 25 Internet Draft Nimrod Architecture July 1994 monitoring would also show which flows from the required minimal set of DMFs would be useful to set up in advance of actual traffic which needed them. Again, however, all these sets can be changed in a local, incremental way, without disturbing the operation of the system as a whole. These new fowarding state fields would not be covered by an end-end authentication system, any more than the existing hop count field (which is also forwarding state) would be. This would prevent problems caused by the fact that the contents of these fields change as the packet traverses the network. The forwarding of these packets can be quite efficient (possibly more so than even standard hop-by-hop). In the non-active routers, the packet is associated with a flow in a way that makes possible hardware processing without any software involvement at all. In active routers, the process of looking up the next DMF would be about as expensive as the current routing table lookup, and the main difference would be that the result of that lookup would have to be stored in the packet, not a great expense. 6 Connectivity Specification Sequence Mode The connectivity specification sequence mode specifies a route by a list of connectivity specification locators. There are no contiguity restrictions on consecutive locators. BEGIN COMMENT The CSS and CSC modes can be seen as combination of the datagram and flow modes. Therefore, in a sense, the basic forwarding modes of Nimrod are just these last two. END COMMENT 7 Renumbering This section presents an example of how to renumber a Nimrod network. Figure 8 shows a network halfway in the process of being renumbered. The figure shows the physical network and the associated locators. The network is formed by router RA which is connected to three ethernets. The figure shows five hosts, "HA" to "HE". To the right of each host two locators are shown. The first locator shown corresponds to the old numbering; the second, to the new numbering. Renumbering has consisted of adding a new level of hierarchy---to simplify the work of RA, say. Because it is possible for a network element to have more than one locator, the two sets of locators can be active at the same time. Initially, only 26 Internet Draft Nimrod Architecture July 1994 the first set of locators is active. It means that Router RA knows to which ethernet a packet should be directed given the locator in the header. (Given a packet destined to one of the hosts, the router would pick one of the three interfaces based on the "host part" of the locator---i.e., "h1" in locator a:h1.) When the second set of locators is introduced, for a time, Router RA would forward based on the two sets of locators---because the first set of locators might still be cached by some sources. Eventually, RA would de-activate the original set of locators. Presumably, RA would be prepared to forward messages to the new set of locators before the DNS (or its equivalent) is instructed to use them. If a packet containing an old locator is given to RA after the locator has been de-activated, an error message would be generated. There exists the possibility that the old locators might be re-assigned. If a packet is received by the wrong endpoint, this situation can be detected by looking at the destination EID which is included in the packet header. The renumbering scheme described above implies that it should be possible to update the DNS (or its equivalent) securely and, relatively, dynamically. However, because renumbering will, most likely, be infrequent and carefully planned, we expect that the load on this updating mechanism should be manageable. A second implication of this renumbering scheme is a requirement for a secure and simple way to update hosts' and routers' locators. 8 Security Considerations Security Considerations are not addressed in this document. 9 Authors' Addresses Isidro Castineyra BBN Systems and Technologies 10 Moulton Street Cambridge, MA 02138 Phone: (617) 873-6233 Email: isidro@bbn.com Martha Steenstrup BBN Systems and Technologies 10 Moulton Street Cambridge, MA 02138 Phone: (617) 873-3192 Email: msteenst@bbn.com Noel Chiappa 27 Internet Draft Nimrod Architecture July 1994 +--+ | | a:r1 |RA| +--+ | /|\ / | \ / | \ / | \ / | \ / | \ / | \ / | \ / | \ / | \ / | \ / | \ ----------------- --------- --------------------------- +--+ +--+ +--+ +--+ +--+ | | a:h5 | | a:h1 | | a:h2 | | a:h4 | | A:h3 |HD| a:a:h1 |HA| a:a:h2 |HB| a:a:h1 |HC| a:c:h1 |HE| A:c:h3 +--+ +--+ +--+ +--+ +--+ Figure 8: Renumbering a Network 28 Internet Draft Nimrod Architecture July 1994 Email: gnc@ginger.lcs.mit.edu References [1] J. N. Chiappa, "A New IP Routing and Addressing Architecture," IETF Internet Draft, 1991. [2] M. Steenstrup, "Inter-Domain Policy Routing Protocol Specification: version 1," RFC 1479, June 1993. [3] R. Wright, Three Scientists and their Gods Looking for Meaning in an Age of Information. New York: Times Book, first ed., 1988. [4] S. Ramanathan, "Mobility Support for Nimrod: Requirements and Approaches.," Working Draft, June 1994. [5] S. Deering, "SIP: Simple Internet Protocol," IEEE Network, vol. 7, May 1993. [6] P. Francis, "A Near-Term Architecture for Deploying Pip," IEEE Network, vol. 7, May 1993. 29   Received: from PIZZA.BBN.COM by BBN.COM id aa26563; 13 Jan 95 15:57 EST Received: from pizza by PIZZA.BBN.COM id aa24842; 13 Jan 95 15:33 EST Received: from KARIBA.BBN.COM by PIZZA.BBN.COM id aa24838; 13 Jan 95 15:28 EST To: nimrod-wg@BBN.COM Subject: Draft of Database Document Date: Fri, 13 Jan 95 15:31:33 -0500 From: Isidro Castineyra I am including a draft of the routing database specification. This draft does not yet include a formal specification of the database. It organizes and expands the presentation given in San Jose. A more detailed version that will include a formal specification is forthcoming. Isidro ----------- Internet Draft I. 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 Database Structure 1 2.1 Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2.2 Node . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2.3 Arcs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2.4 Partial Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2.5 Partial Node . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2.6 Qualified Connectivity Specification . . . . . . . . . . . . . . . 2 2.7 Connectivity Specification . . . . . . . . . . . . . . . . . . . . 3 2.8 Performance Specification . . . . . . . . . . . . . . . . . . . . . 3 2.9 Policy Specification . . . . . . . . . . . . . . . . . . . . . . . 3 2.10Locator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.11Type . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.12Handling Code . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3 External Representation 4 4 Query Language 4 5 Security Considerations 4 6 Authors' Addresses 5 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. Information is typically in the form of node maps. This document gives an implementation-independent description of the database and a description of a suitable external representation. Section 2 describes the structure of the database. This description includes a naming system. Names are used, for example, by a querying process to request elements of the database. The description also defines a simple type system. Section 3 describes the proposed external representation. Section 4 briefly describes the query language. 2 Database Structure This issue of this document does not use formal notation to describe the elements of the database. Instead, the component elements of each database item type are given as a list of name-type pairs. A future revsion of this of this document will include a specification using a formal notation. We use the "*Set*" construct to indicate a grouping of distinct elements of the same type. The *Set* construct could be implemented, for example, as a list. Section 3 specifies an external representation for *Set*. The elements specified in this section are: maps, nodes, arcs, and connectivity specifications. 2.1 Map o Nodes: *Set* of node. 2.2 Node o ID: Locator; o Outgoing-arcs: *Set* of arc; 1 Internet Draft Nimrod Routing Database January 1995 o Internal-map: map; o Topology: partial map; comment: Contains the topology of the internal map without the nodes's characteristics. o Transit-connectivity: *Set* of qualified connectivity specification; o Incoming-connectivity: *Set* of qualified connectivity specification; o Outgoing-connectivity: *Set* of qualified connectivity specification; 2.3 Arcs o Arc-number: typeinteger; o Arc-head: typelocator; comment: Locator of the head node 2.4 Partial Map Contains the topology of a map without the node characteristics. o P-nodes: *Set* of partial nodes; 2.5 Partial Node o ID: locator; o Outgoing-arcs: *Set* of arcss; 2.6 Qualified Connectivity Specification o Input-prefixes: *Set* locator; o Output-prefixes: *Set* of locator; o Value: connectivity specification. 2 Internet Draft Nimrod Routing Database January 1995 2.7 Connectivity Specification o Kind: type; comment: Indicates what kind of connectivity specification it is, allows a receiver to determine if it undesrtands this connectivity specification o Action: handling code; comment: Indicates what to do with the connectivity specification in case it is a type not understood o ID: Locator; o Value: performance specification; o Restrictions: policy specification: 2.8 Performance Specification TBD. 2.9 Policy Specification TBD. 2.10 Locator TBD. 2.11 Type TBD. 2.12 Handling Code TBD. 3 Internet Draft Nimrod Routing Database January 1995 3 External Representation The external representation should make possible to interoperate implementations that do not understand the same set of connectivity 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. The external representation should be easily parseable. In particular, it should be possible to "jump" over the external representation of elements without having to parse them. Every element is represented by a (type, handling code, length, value) tuple. Each one of the elements defined in section 2 has its own type. Moreover, each connectivity specification has a type associated with it. The type allows an implementation to determine if this element is understood. The type is a 16 bit integer. The handling code is a 16 bit field. The length indicates the length in bytes of the whole tuple. It is a 32 bit unsigned integer. The value part can itself by formed by a sequence of tuples. The type field indicates how this field should be parsed. Terminal elements are represented using the external data representation of RFC 1014. 4 Query Language Queries are used to obtain information from node representatives. The query language allows requesting specific elements of the database. The query language does not allow requests that depend on the values of the elements. For example, request of the style "send all connectivity specifications with property foo" are not defined. 5 Security Considerations Security Considerations are not addressed in this document. 4 Internet Draft Nimrod Routing Database January 1995 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. 5   Received: from PIZZA.BBN.COM by BBN.COM id aa09366; 13 Jan 95 19:51 EST Received: from pizza by PIZZA.BBN.COM id aa26477; 13 Jan 95 19:32 EST Received: from KARIBA.BBN.COM by PIZZA.BBN.COM id aa26473; 13 Jan 95 19:29 EST Date: Fri, 13 Jan 95 19:32:39 EST From: Martha Steenstrup To: nimrod-wg@BBN.COM Subject: drafty draft Hi guys, We are releasing preliminary versions of the Nimrod protocol, procedure, and database specifications as separate memos. Eventually, all of this information will be integrated into a single Nimrod specification document, but we figured that it would be easier for readers to digest the memos separately rather than as one large document. This (drafty) memo describes the Nimrod packet forwarding procedures and path management protocol. The design is based on the one described in the Nimrod functionality document and expands upon the details provided at the December IETF. We assume that the reader is familiar with the terminology defined in the Nimrod architecture and functionality documents. Please send comments on this memo to the Nimrod working group mailing list. Thanks, m ----------------- Nimrod Data Packet Forwarding 1 Introduction Nimrod forwarding agents are responsible for establishing forwarding state information and for forwarding packets according to this state information and according to forwarding directives carried along in the packets. The forwarding state information maintained by forwarding agents is derived from the routes selected by forwarding agents and is installed using a "path management" protocol. Forwarding agents select routes according to the traffic service requirements supplied by endpoint representatives acting on behalf of the hosts and according to the available maps. Nimrod routes are expressed as a sequence of locators of nodes and corresponding connectivity specifications. Each route must at least contain information about the source and destination nodes. Different portions of the same route may be expressed at different granularities of nodes with respect to the node clustering hierarchy. Forwarding agents establish forwarding information according to the routes selected. The forwarding state established in forwarding agents along the specified route is called a path, and it may ultimately connect one or more source endpoints and one or more destination endpoints. Multiple traffic sessions may use the same path, thus helping to contain the amount of internetwork resources consumed in managing paths. Moreover, multiple paths may be established based on the same route. 2 Forwarding Modes Nimrod supports two packet forwarding modes: flow and datagram. Flow mode requires the establishment of forwarding state specific to the traffic session, in forwarding agents along the routes selected for that session. With flow mode, each session is assigned one or more paths, derived from the selected routes. The minimum forwarding state required for flow-mode forwarding includes the path "label", service guarantees (if any), and the path's previous- and next-hop forwarding agents (and path labels). Flow mode provides fast and consistent packet forwarding according to path labels, once the session-specific state is established in the forwarding agents. However, this state consumes memory in forwarding agents, and the protocol for its installation imposes some delay before data packets can be forwarded successfully to their destinations. Flow mode should be used when session-specific state is necessary to meet traffic service requirements or when the cost of forwarding state installation and maintenance can be amortized over many packets. Hence, we recommend flow mode for traffic sessions requiring guaranteed service or consisting of several packets. Datagram mode does not require the establishment of any forwarding state specific to the session. In datagram mode, data packets carry a description of the selected route, which guides the packet forwarding decisions at forwarding agents along the route. For each node in the specified route, a forwarding agent at the entry to that node makes an independent decision for forwarding traffic toward the next node on the route, and hence the session source and destination relinquish some control over packet forwarding. Datagram mode, however, does provide robust forwarding, in the sense that the intermediate forwarding agents can base their packet forwarding decisions on the current state of their portion of the internetwork. Datagram mode should be used when the state of the internetwork is unpredictable or when the cost of forwarding state installation and maintenance is unacceptable. Hence, we recommend datagram mode for traffic sessions traversing highly mobile or unreliable portions of an internetwork or consisting of few packets. 3 Path Management Protocol Forwarding agents use a path management protocol to install and remove forwarding state information from their forwarding databases. Each forwarding agent maintains forwarding information for those paths that originate, terminate, or pass through it. Paths may be set up from source to destination or from destination to source. Each path has an initiator and a target. We expect that most paths will be set up from the source endpoint to the destination endpoint. Hence, the initiator usually begins the path setup procedure on behalf of the source endpoint, and the target usually accepts or rejects a path on behalf of the destination endpoint. Forwarding agents try to form new paths by piecing together existing paths rather than by setting up new paths, provided the existing paths meet the traffic service requirements. (See the Nimrod functionality document for an example of this procedure.) Hence, Nimrod paths are inherently multilevel. This method provides the lowest-cost packet forwarding in terms of the amount of route generation and forwarding state installation required. In a busy internetwork, there are likely to be many existing paths, and hence we expect this mechanism to be much less expensive than individually setting up and maintaining the paths required for every traffic session. Paths are identified by path labels, which are unique along the path but not necessarily globally unique throughout the internetwork. By no requiring global uniqueness of path labels, paths can have relatively short labels, reducing the overhead in carrying them in packets and the overhead of looking up forwarding information indexed by these labels. We currently believe that we can assign relatively short path labels that are not globally unique in a way that results in minimal collisions of path labels from different paths, by "spreading" the path labels. (We will discuss this further in a separate note.) 3.1 Protocol Packets The path management protocol uses three packets: setup, accept, and teardown. These packets are described below; explicit formats will be provided in a future version of this memo. All such packets travel along the path to which they refer. Path management protocol packets may be used to collect and return performance monitoring information for a path (e.g., path delay and throughput) as well as set up and tear down a path. The setup packet is generated by the path initiator and is used to establish forwarding state in forwarding agents. It contains the label for the path, the route, the endpoint identifiers, an indication of whether the path is source- or destination-initiated, any service requirements, and any monitored information for the path. The accept packet is generated by the path target and is used to indicate successful path establishment from initiator to target. It contains the label for the accepted path and any monitored information for the path. Accept packets travel backwards along paths. A path may be used for data transport before an accept packet is generated by the target or received by the initiator. Note that a source as initiator may wish to wait for an accept packet from the target before sending data on a path is as follows. For example, if the source pays for all packets sent, whether or not they are successfully received at the destination, it may want to wait to make sure that the path is successfully established before sending data to the destination. The teardown packet is generated by any forwarding agent on the path and is used to remove forwarding state. It contains the label for the path to tear down, the reason for the teardown and associated information, and any monitored information for the path. Teardown packets travel in both directions along paths and may result from any of the following: - loss of a lower-level path which is a component of the specified path; - a timeout (paths have a maximum lifetime to ensure that forwarding state for broken paths is eventually removed); - a change in service requirements for the traffic session; - a change in connectivity specifications for a node on the route; - preemption in favor of another path. All path management protocol packets (and in fact all Nimrod packets except data packets) are covered by integrity and authentication checks and are sent using a reliable transaction protocol (with positive and negative acknowledgements) between successive forwarding agents along the path. This helps to reduce the amount of network resources consumed by retransmissions in lossy environments and also helps to determine problems (e.g., incompatible protocol versions) for unsuccessful mpacket transmissions. 3.2 Protocol Finite-State Machines There are two finite-state machines for the path management protocol, one applicable to the initiator and one applicable to any other forwarding agent in the path. 3.2.1 Initiator The state machine for the initiating forwarding agent has four states: idle, check, ready, and done. State transitions are depicted below: idle -> check: This transition occurs when the initiator begins to set up a path. check -> ready: This transition occurs after the initiator has successfully completed all of the consistency and resource availability checks for the path. These checks are described in section 3.2.3. At this point, the initiator installs the forwarding information for the path in its forwarding database. From the perspective of the initiator, the path may be used to carry data traffic. check -> idle: This transition occurs if the initiator fails to complete the consistency and resource availability checks for the path. ready -> done: This transition occurs when the initiator receives an accept packet from the target. ready -> idle, done -> idle: This transition occurs when the initiator receives or generates a teardown packet for the path. At this point, the initiator removes the forwarding information for the path from its forwarding database. 3.2.2 Intermediate and Target The state machine for the intermediate and target forwarding agents has three states: idle, check, and ready. State transitions are depicted below: idle -> check: This transition occurs when the forwarding agent receives a setup packet. check -> ready: This transition occurs after the forwarding agent has successfully completed all of the consistency and resource availability checks for the path. At this point, the forwarding agent installs the forwarding information for the path in its forwarding database. From the perspective of the forwarding agent, the path may be used to carry data traffic. check -> idle: This transition occurs if the forwarding agent fails to complete the consistency and resource availability checks for the path. ready -> idle: This transition occurs when the forwarding agent receives or generates a teardown packet for the path. At this point, the initiator removes the forwarding information for the path from its forwarding database. 3.2.3 Check State Actions When in the check state, a forwarding agent must perform a series of tests to determine whether to install forwarding information for the path. These tests are partitioned into two sets, those related to consistency and those related to resource availability. Consistency checks include verification of the following: - The setup packet is not out of date and is not a duplicate. This check is not performed by the initiator. - The path label carried in the setup packet is not already in use at the forwarding agent. - The forwarding agent acts on behalf of the current node in the route carried in the setup packet. - The connectivity specification associated with the node and carried in the setup packet is a valid connectivity specification for this node. - The node's service restrictions do not preclude carrying traffic along the specified route. - The route carried in the setup packet meets the target endpoint's service requirements. This check is specific to the target. When the target receives a setup packet, it passes the packet to endpoint representative for corresponding endpoint. This endpoint representative performs the appropriate check and returns the result to the target. If the check is successful, the target accepts the path. Otherwise, the target tears down the path and takes one of the following actions: 1. If the target is at the destination endpoint, the teardown packet contains the destination endpoint's service requirements. The initiator is responsible for obtaining a feasible route that accounts for these service requirements. 2. If the target is at the source endpoint, the teardown packet indicates that the source will generate a feasible route. If the setup packet successfully passes all of these consistency checks, the forwarding agent performs a set of resource availability checks including verification of the following: - The forwarding database can accommodate state for a new path. - There exists a feasible path to the next node on the specified route. The forwarding agent may have to request a route and set up this path or there may be such a path already established. If such a path Q has already been established, the forwarding agent associates the current path P with Q so that traffic entering the forwarding agent along the path labelled P will be forwarded along the path labelled Q. If no such path Q yet exists, the forwarding agent requests a route from a route agent. This route must go from the forwarding agent to the next node in path P's route, and it must satisfy the service requirements for path P (carried in P's setup packet). If the forwarding agent obtains a feasible route, it proceeds to set up a path for that route and determines whether the necessary resources can be reserved along path Q. Only when the forwarding agent receives an accept packet for path Q does it make the corresponding path label associations between P and Q in its forwarding database. Note that the forwarding agent also makes a path label association for the reverse direction of the path so that path management protocol packets can travel in either direction along a path. Specifically, the forwarding agent makes an association between the path R, the previous hop along P that terminates at the forwarding agent, and path P. 4 Forwarding Information in Nimrod Packets Datagram packets and setup packets for flow mode carry almost exactly the same information and are processed by forwarding agents in similar ways. The principal difference in packet processing for datagram and setup packets is that no forwarding state is established specific to datagrams. Most of the consistency and resource availability checks previously described for setup packets are also performed for datagram packets. Shared contents of setup and datagram packets include: - Source and destination endpoint identifiers. - The route in terms of the locators for nodes and their relevant connectivity specifications. - Service requirements (e.g., bandwidth guarantees, delay bounds) from the perspective of the initiator of the packet. Forwarding agents use this information in deciding how to forward the packet toward the next node on the route. - User data (setup messages might not always contain user data). Most paths are composed of paths which in turn are composed of paths and so on. Hence, a flow mode data packet must contain the path labels of all the component paths at all levels, but only one path label is used for forwarding at a given time. These path labels are stacked in the packet and manipulated (pushed and popped) by the forwarding agents handling the packet. 4.1 IPv6 Optimizations For initial implementations of Nimrod, we plan to encapsulate Nimrod packets within IP packets, independent of the version of IP currently in use. Hence, there is no information that must be added to IP packets (other than the identifier of the enclosed protocol - Nimrod). All Nimrod-specific information will be carried in Nimrod packets encapsulated within IP. For an IPv6 internetwork, one may opt to define Nimrod-specific options that will allow some Nimrod information to migrate up to the IP header. The proposed options include hop-by-hop options, a route option, and end-to-end options. Suggested formats for these options were provided at the December IETF and will be depicted in a future version of this document. 4.1.1 Hop-by-Hop Options The hop-by-hop options are those that must be modified at most forwarding agents and include the stack of path labels (for flow-mode data packets) and monitoring information (which may be carried in setup packets or flow-mode data packets). The monitoring option would enable multiple path performance quantities, such as delay and throughput, to be monitored and updated at each hop along the path. All monitoring information would be expressed in terms of type, length, and value. Collected monitoring information would be returned to the other end of the path in an end-to-end performance option described below. 4.1.2 Route Option The Nimrod route specified in terms of locators of component nodes and connectivity specifications would be included in a route option. 4.1.3 End-to-End Options Source and destination endpoint identifiers would be carried in an end-to-end option. Path service requirements and moitored performance information would be carried in separate end-to-end options. Each service requirement and each performance parameter would be specified in terms of type, length, and value.   Received: from PIZZA.BBN.COM by BBN.COM id aa12594; 13 Jan 95 21:18 EST Received: from pizza by PIZZA.BBN.COM id aa26952; 13 Jan 95 20:53 EST Received: from CLynn.BBN.COM by PIZZA.BBN.COM id aa26948; 13 Jan 95 20:51 EST Date: Fri, 13 Jan 95 20:50:11 EST From: Charles Lynn To: nimrod-wg@BBN.COM Subject: Draft of Nimrod Deployment Plan A draft of the Nimrod Deployment Plan follows. Please send comments on this memo to the Nimrod working group mailing list. Thanks, Charlie ---------------------------------------------------------------------------- Internet Draft C. Lynn Nimrod Working Group January 1995 Expires July 1995 Nimrod Deployment Plan Status of this Memo This document is one of several by the IETF Nimrod Working Group. It describes how Nimrod can be incrementally deployed into the existing Internet. Consideration is also given to IPv6. 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. Internet Drafts may be updated, replaced, or obsoleted by other documents at any time. It is not appropriate to use Internet Drafts as reference material or to cite them other than as a "working draft" or "work in progress". Please check the 1id-abstracts.txt listing contained in the internet- drafts Shadow Directories on ftp.isi.edu, ds.internic.net, nic.nordu.net, munnari.oz.au, or ftp.is.co.za to learn the current status of any Internet Draft. Distribution of this Internet Draft is unlimited. Please send all comments to nimrod-wg@BBN.Com. Abstract We describe how the Nimrod routing system can be deployed incrementally into an internetwork, and in particular into the Internet. We discuss the initial implementation required to obtain Nimrod functionality in some places within an internetwork, and we also discuss the migration path to the full implementation. Internet Draft Nimrod Deployment January 1995 Contents 1 Introduction 1 1.1 Nodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Identifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.3 Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.4 Agents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 Objectives of this Transition Plan 4 3 Initial Deployment 5 3.1 Hosts. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3.2 IP Versions. . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3.2.1 Endpoint Labels . . . . . . . . . . . . . . . . . . . . . . . 6 3.2.2 Agent Discovery . . . . . . . . . . . . . . . . . . . . . . . 7 3.3 Deployment Locations . . . . . . . . . . . . . . . . . . . . . . . 7 3.4 Implementations . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.4.1 Plug and Play . . . . . . . . . . . . . . . . . . . . . . . . 8 3.4.2 Independent Implementation . . . . . . . . . . . . . . . . . . 11 4 Full-Scale Deployment 13 4.1 Directory Services . . . . . . . . . . . . . . . . . . . . . . . . 13 4.1.1 Format . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 4.2 Host Changes . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 4.3 Boot Server Changes . . . . . . . . . . . . . . . . . . . . . . . 15 4.4 EID Administration . . . . . . . . . . . . . . . . . . . . . . . . 15 5 Security Considerations 15 5.1 Accountability . . . . . . . . . . . . . . . . . . . . . . . . . . 16 5.1.1 Integrity of Routing Information . . . . . . . . . . . . . . . 16 5.1.2 Compromised Components . . . . . . . . . . . . . . . . . . . . 16 5.1.3 Interactions with Other Internetwork Subsystems . . . . . . . 17 5.1.4 Enhanced Service Considerations . . . . . . . . . . . . . . . 17 5.2 Summary of Nimrod Security Services. . . . . . . . . . . . . . . . 18 6 Utilities 18 7 Author's Address 19 References 19 i Internet Draft Nimrod Deployment January 1995 1 Introduction Nimrod is a scalable routing architecture for large, heterogeneous, and dynamic internetworks, providing service-specific routing in the presence of multiple constraints and admitting incremental deployment throughout an internetwork. This document presents a plan for deploying the Nimrod routing system in an internetwork. We briefly describe the Nimrod architecture to provide context for the deployment plan presented in subsequent sections of this document. Detailed descriptions of the Nimrod architecture and functionality can be found in [1], [2], [3], and [4]. 1.1 Nodes Nimrod aggregates the physical assets of an internetwork into a hierarchy of clusters, called "nodes", and abstracts connectivity and service information (e.g., adjacency relationships, service offerings, and restrictions on the use of these services) associated with the component assets to determine the connectivity and service information for a node. Clustering and information abstraction allow the Nimrod routing system to scale to an internetwork the size of the projected Internet. At the top of the hierarchy, there is a single "universal node" representing the complete internetwork. Other examples of nodes include autonomous systems, networks (including routers, hosts, and links between them), individual routers, and even interfaces on routers. Assets within a (non-partitioned) node must be able to intercommunicate over routes that do not traverse any assets outside of the node. 1.2 Identifiers The Nimrod architecture makes a fundamental distinction between the name and the location of the endpoints for a traffic session. Three separate label spaces are used: endpoint names, endpoint identifiers, and locators. "Endpoint names" are variable length, relatively long, globally unique text strings used by humans to name endpoints in an internetwork. They are administratively allocated and are not necessarily related to the topology of the internetwork. "Endpoint identifiers" (EIDs) are fixed length, relatively short, topologically insignificant, densely packed, globally unique identifiers used by the transport layer to identify the source and destination endpoints of traffic sessions. An EID has the semantics of "who". In most situations, an EID will correspond to a host but may also, for example, correspond to a migratory process or a sub-component of a host. EIDs are administratively allocated and are not necessarily related to the topology of the internetwork. An EID has no internal structure useful to routing. 1 Internet Draft Nimrod Deployment January 1995 "Locators" are moderate (and possibly variable) length, topologically significant, structured bit strings used by routing to identify the source and destination nodes containing the endpoints of a traffic session. A locator has the semantics of "where". It has internal structure that consists of a list of "elements", one from each node in the hierarchy that contains the given node. It does not appear that an arbitrary observer need be able to parse an arbitrary locator into its component elements. However, each Nimrod agent must be able to recognize its own locator and prefix, and can thus isolate any remaining portion, e.g., suffix, of locators within itself. 1.3 Maps The Nimrod architecture assembles, distributes, and uses routing information in the form of "maps" of contiguous portions of an internetwork, represented by nodes and their associated adjacencies and service attributes. The adjacencies between nodes in a Nimrod map may be visualized as arcs. However, arcs are not part of the Nimrod Architecture, only the adjacencies. There are several maps associated with a node. A node's "basic map" is built from the maps of its component (next lower-level) nodes. It may contain information that the administrators of the node do not wish to be made available outside of the node. An "internal map" is a map that is made available outside of the node for those interested in the node's internal structure. The contents of an internal map is a filtered version of the basic map. There may be several internal maps as the filtering applied to the basic map may be a function of the credentials of the requester of the map. An "abstract map" is a map that is made available outside of the node for those interested in passing traffic through the node. The contents of a abstract map is a filtered, abstracted version of the basic map that contains the node's adjacencies, and "inbound", "transit", and "outbound" service offerings and restrictions, but does not contain the node's internal structure. The advertised services apply to node entry and exit points from and to adjacent nodes and need not be uniform over all such points. There may be several abstract maps as the filtering and abstraction applied to the basic map may be a function of the credentials of the requester of the map. Filtering results from information hiding considerations and implies that the map distributor trusts the recipient not to redistribute the map arbitrarily. Nimrod version 1 will not rely on such trust relationships. We expect that those who choose to be part of the initial deployment will distribute service restrictions with the maps rather than restrict service information distribution in maps. 1.4 Agents The Nimrod functions of map construction and distribution, endpoint location, route generation, path establishment, and packet forwarding are 2 Internet Draft Nimrod Deployment January 1995 performed by Nimrod "agents". These agents may reside within routers, hosts, or special-purpose Nimrod "boxes". "Node representatives" construct and distribute maps for the given node. When a node's abstract map changes, one of its representatives distributes the new map to a node representative at the next level up in the hierarchy, ensuring that higher-level node representatives can accommodate lower-level map changes in their own maps. Node representatives also respond to requests for specific maps from "route agents", which generate routes on behalf of endpoints. The Nimrod architecture does not specify clustering and abstraction algorithms for constructing maps nor route generation algorithms. We will, however, provide in a future document a Nimrod usage guide detailing several example algorithms and their suitability with respect to various internetwork topologies and traffic service requirements. The Nimrod clustering and abstraction algorithms may differ from node to node, and the route generation algorithms may differ from endpoint to endpoint. In fact, these algorithms may be proprietary. We expect that in a full-scale implementation of Nimrod in the Internet, some organizations may specialize in providing map construction or route generation services for its Internet customers. There is always a simple route between any two locators by simply going up the clustering hierarchy to a common node then down the hierarchy to the destination. Such an organization might find better routes by exploring more detailed maps in order to find adjacencies that have been filtered out of higher level maps. There may also be a market for optimizing multicast routes between a number of pre-specified nodes. Other organizations will contract for these services, either instead of providing this functionality in their own organization, or because it is more cost effective to purchase some routes than it is to generate them locally. As the internal and abstract maps returned to a route agent might depend on the credentials of the requester of the map, a route agent should be prepared to receive different versions of a map for a given node. "Endpoint representatives" request acceptable routes on behalf of endpoints, providing route agents with endpoint locators, EIDs, and traffic service requirements. They obtain endpoint locators from "association agents" that maintain the database of endpoint names, EIDs, and locators. Using this endpoint information, service requirements, and maps obtained from node representatives, route agents generate routes between source and destination endpoints. Maps requested during, and routes resulting from, route generation may be cached by the route agents for use in fulfilling future route requests. Endpoint representatives pass the acceptable routes routes supplied by the route agent back to the endpoint so that it may select the route or routes that best satisfies its requirements. The endpoint initiates path setup, which sets up forwarding information in "forwarding agents" along the path(s) to the destination(s). Other acceptable routes might be cached for later use if the alternative selected fails during use. Nimrod supports 3 Internet Draft Nimrod Deployment January 1995 unicast, multicast, and multiple-path routes. Forwarding agents forward traffic according to stored state information and forwarding directives contained in packets. "Boundary forwarding agents" reside at points along a node's boundary and are responsible for forwarding traffic and, during path setup, enforcing any local policy applicable to traffic entering or leaving the node. 2 Objectives of this Transition Plan This transition plan focuses on the deployment issues most relevant in the Internet. It does not attempt to cover the obscure or innovative ways that the Nimrod architecture and functionality might be used. The process of moving from the current Internet routing systems (e.g. BGP, OSPF) to the Nimrod routing system must be accomplished in a smooth and incremental way. Both the old and new routing systems will be operating simultaneously indefinitely. There is no requirement that all portions of the Internet switch over to the Nimrod routing system. Thus, it is incorrect to think that the "transition" will ever be "completed". The functionality offered by Nimrod must be made available as Nimrod is being incrementally deployed. We expect that organizations will want to see the benefits provided by Nimrod before investing in it. Hence, we plan to make a Nimrod implementation available that is inexpensive and easy to use to allow prospective Nimrod users to become familiar with Nimrod's functions and benefits. The cost to an organization to "buy in" to a Nimrod deployment should be as low as possible. A target cost is one box running freely available software that includes all the necessary Nimrod agents. When an organization's demand increases to the point where the one box solution does not have sufficient resources to meet the demand, additional boxes would be economically justifiable. Nimrod deployment does not require any changes to host software before an organization is able to take advantage of Nimrod functionality. Moreover, an organization's routers need not be changed for Nimrod support. The plan does not require existing hosts or networks to be renumbered. Changes to hosts and routers to support Nimrod functionality will occur when there are sufficient customers to justify the host and router vendors' development costs and when performance improvements are attractive enough. These objectives both provide incentive to deploy the Nimrod routing system and permit more widespread implementation experience and interoperability testing to be gained so that any potential problems with either the protocols or specifications can be identified and fixed, and any areas that may need improvement can be addressed. 4 Internet Draft Nimrod Deployment January 1995 3 Initial Deployment There are several possible scenarios for deploying Nimrod in an internetwork in an incremental fashion. These scenarios differ depending on whether hosts are Nimrod capable, whether the internetwork is using IPv4, IPv6, or some other internetwork layer, whether Nimrod will be deployed in an existing portion of the Internet or will be employed in an entirely new network, and whether the prospective Nimrod users will use an "off-the-shelf" version or choose to implement their own version of Nimrod. 3.1 Hosts For initial deployment, hosts need not be Nimrod capable nor even Nimrod aware. The consequence of this requirement is that existing hosts cannot use the full functionality provided by EIDs, or the ability to dynamically specify service requirements. Later on, in section 4, we discuss potential benefits of introducing Nimrod functionality into hosts. 3.2 IP Versions Nimrod functionality can be added to internetworks that use any internetwork packet header and forwarding procedures. We note that this is the same approach used with IDPR [5], enabling that routing system to be used in any internetwork, independent of packet format and forwarding conventions. In particular, Nimrod will work with IPv4 and IPv6. However, Nimrod is not responsible for conversion between IPv4 and IPv6 addresses or formats. That translation functionality is part of the IPv6 transition and not part of the Nimrod deployment. With either version of IP, Nimrod information will be encapsulated within IP packets and forwarded between Nimrod agents. Currently deployed hosts and routers need not be aware of the presence of Nimrod; they forward packets solely on the IP header. The encapsulation will appear as a "Nimrod protocol". Packets destined to the box are passed up to the protocol handler, and either decapsulated for delivery to an IP host that is not Nimrod-aware, or re-encapsulated for delivery to the next Nimrod-aware entity. We note that in the case of IPv6, some performance improvements in data packet forwarding may be realized by placing Nimrod forwarding information in a Nimrod-specific IPv6 Routing Header and/or end-to-end EID option. One drawback of using options is that the IPv4/IPv6 translators would need to be modified to also translate the option, and that there might not be sufficient space in the IPv4 header for the option. Consequently, use of options can be restricted to communication between IPv6 capable systems. The simplest transition, in terms of the amount of implementation required, is to encapsulate all Nimrod information within IP packets, with none of the Nimrod-specific information visible at the IP level. An alternate viewpoint is that an IPv6 address is a Nimrod locator, and that the IPv6 Routing Header is the Nimrod routing header. It is not clear 5 Internet Draft Nimrod Deployment January 1995 at this point whether the aggressive IPv6 schedule will permit general consensus to be reached based on the as yet unproved Nimrod routing system. One issue is that the current IPv6 thinking is that intermediate systems may not insert a routing header, as we envision Nimrod endpoint representatives or forwarding agents doing. Another point is that the IPv6 Authentication Header is end-to-end, and only appears once in a packet. There has been no documented consideration to authentication between end systems and routers, as Nimrod is proposing. 3.2.1 Endpoint Labels For initial Nimrod deployment, we suggest using Domain Name System (DNS) names and/or IP addresses as endpoint names. These are the lookup keys used by the DNS system. There will be no "inverse lookup" on either EID or locator as Nimrod does not require such a mechanism. (Note that this does not to prohibit an EID or locator from being used as a cache key.) This simplifies both the administration and maintenance of those label spaces. IP currently overloads the IP address with the semantics of both an EID and a locator. Thus we will make the assumption that if no EID is specified either explicitly in a packet, or implicitly by a flow, that the IP address is to be used for the EID. Hosts that have been modified to use EIDs (that are not the same as the IP address) will interoperate with unmodified hosts using the Nimrod mechanism to communicate EID information. Locators will be handled similarly. The endpoint representatives will maintain the mapping between locators and unmodified local hosts. This approach reduces the amount of implementation effort required to get Nimrod running in a portion of the Internet. We suggest adding additional resource records to the DNS to specify EID and locator information. We further suggest that the EID and locator resource records be returned as additional information when either an IPv4 A or IPv6 AAAA record is requested. Unmodified hosts will not query for EID or locator records, and will not make use of the additional information returned with A or AAAA records. That information will be used by the endpoint representatives. DNS queries from an endpoint will most likely pass through the endpoint's representative, which can relay the request and then cache the reply. If the information is not in the cache when needed by the endpoint representative, it can query for it directly using the IP addresses in packets it is processing. Another approach is to use Nimrod to maintain the authoritative endpoint/locator associations. In this case, Nimrod boxes would be placed near hosts to intercept DNS queries, use the DNS names as keys into the association database of endpoint locators, retain the appropriate endpoint/locator associations, and return only the IP addresses to the hosts. While this approach may be more quickly implemented initially, it has several long term drawbacks which we feel outweigh its advantages. First, it would be another configuration database that would have to be documented, taught to the system administrators, and maintained. Looking up remote host information would require a mechanism to locate the Nimrod agent 6 Internet Draft Nimrod Deployment January 1995 responsible for the remote host, essentially setting up a parallel delegation hierarchy. Then, as the long term method is being introduced, there would need to be tools, documentation, training, and ongoing maintenance provided to maintain synchronization between the short term and the long term solutions. Nimrod code would then have to be provided to decide which method to use, and it would be hard to remove the short term solution once there was any significant installed base. For these reasons we do not advocate using this approach. Note, however, that using Nimrod to maintain non-authoritative information is logically the same as the caching described above, and that one mechanism to prime the cache would be through a local configuration file. This step on the path to the long term solution can be used for testing while the DNS solution is being implemented. It would require local configuration of all local and remote peers, but avoids the need for a second delegation and lookup hierarchy. IP addresses may be used as default EIDs for initial Nimrod deployment. Thus, no EID management mechanism need be in place prior to Nimrod deployment. This means that endpoints are initially confined to be hosts and not processes within hosts, as no port information is available in IP addresses. Multiple Nimrod traffic sessions may be established between a pair of hosts provided that information in addition to the IP address, such as protocol and ports, is visible in the packet. These restrictions disappear when hosts use EIDs that are independent of IP addresses. 3.2.2 Agent Discovery Agent discovery will be a key factor in any "plug-and-play" deployment of Nimrod. In IP internetworks, each type of Nimrod agent for a node will be assigned an IP multicast address that uniquely identifies them as Nimrod agents. To distribute their information to and to obtain information from other agents for the node, Nimrod agents will distribute their information using IP multicasting. Hence, all agents for a given node must be configured with the special IP multicast address(es) for such agents. Since IP multicast may not be available for the initial Nimrod deployment, configuration files for the Nimrod agents can be used. The availability of IP multicast will remove the necessity for the configuration information in a full-scale deployment. 3.3 Deployment Locations We expect that most prospective Nimrod users will want to introduce Nimrod functionality into existing portions of the Internet where there already exist IP routing and packet forwarding mechanisms. We do not expect Nimrod users to build new internetworks based entirely on Nimrod until it has been proven in existing internetworks, but they may choose to build a Nimrod only subnetwork within their organization. For an initial Nimrod deployment, we suggest two different methods, one based on breaking existing nodes into smaller nodes and the other based on 7 Internet Draft Nimrod Deployment January 1995 building new nodes by clustering existing nodes. In the first scenario, a large autonomous system (e.g., a campus network or even a transit network) becomes a node. This autonomous system is then decomposed into component nodes, for example, along network boundaries. In the second scenario, neighboring autonomous systems become nodes, and these autonomous systems are in turn clustered into a single larger node. For example, a regional service provider might clustered together into a single larger node the nodes of customers that have Nimrod capability. In any case, we suggest initial deployment of Nimrod in an area of the Internet that is large enough to enable observation of the benefits of Nimrod yet small enough for observers to be able to manage and understand Nimrod performance. Within a Nimrod-capable portion of the Internet, Nimrod functionality will be available among the clustered nodes, but conventional Internet routing (e.g., BGP, OSPF) will be used to route to or from hosts external to the Nimrod portion. Nimrod-capable portions of the Internet can be extended by introducing Nimrod functionality to autonomous systems or networks bordering on autonomous systems or networks that already handle Nimrod. Deployment of Nimrod in such a gradual fashion makes the process manageable and can eventually result in full-scale deployment without having to simultaneously convert large numbers of autonomous systems or networks to Nimrod. 3.4 Implementations Prospective Nimrod users will want to assess the performance of the Nimrod routing system through limited deployment in their networks. Although some users will build their own Nimrod implementations for this purpose, we expect most users will want to take advantage of existing Nimrod implementations in order to reduce the delay and cost of getting Nimrod up and running. For each case, we describe the deployment process, emphasizing the aspects that minimize the amount of work that must be performed to obtain a functional Nimrod routing system. 3.4.1 Plug and Play We plan to make available versions of Nimrod software that can execute on ordinary workstations for quick trial deployments of Nimrod. With these implementations, a single Nimrod "box" can provide all of the Nimrod functionality. These boxes must also be capable of performing ordinary IP routing and packet forwarding, but are not likely to provide the throughput of a high-performance router. Nimrod deployment within a node requires boundary forwarding agents---one for each node entry/exit point---to control traffic passing into and out of the node. It also requires a node representative and at least one endpoint representative if there are endpoints, i.e., hosts that are to use Nimrod routing, within the node. Association agent and route agent functionality need not be present in each node but there should be good connectivity to these agents. For minimal performance impact on traffic to non-Nimrod 8 Internet Draft Nimrod Deployment January 1995 destinations, we recommend the following deployment of Nimrod boxes within a node. Typical topologies for organizations that deploy Nimrod functionality consist of one or more high performance "border routers" that connect the organization's network(s) to the internetwork. These border routers may contain policy filters or firewall functionality. They also typically either define the boundary of IP Multicast intra-site scope connectivity, or do not pass native IP Multicast traffic. A provider typically has border routers that connect both to the provider's customers and to other providers. There needs to be subnetwork connectivity between each Nimrod endpoint and its endpoint representative. There should also be subnetwork connectivity between the Nimrod box(es) providing the boundary forwarding agent functionality and the organization's relevant border routers. Note that an organization may choose to restrict Nimrod traffic to only pass through a subset of its border routers so not all would be relevant. We require subnetwork connectivity for two reasons. First, so that default routes can be installed in each endpoint (boundary forwarding agent) pointing to the endpoint representative (border router), respectively, in order to reduce the amount of required configuration. Second, so that endpoints will accept ICMP Redirects when the communication peer(s) are not reachable through the Nimrod routing system. Boundary Forwarding Agents -- Attach a Nimrod box to each relevant border router for the Nimrod node representing the organization. Each such box will act as a boundary forwarding agent and node representative. It will also act as a route agent and association agent for queries about the given node. Nimrod traffic would enter the border router, be passed to the boundary forwarding agent, be processed, passed back to the border router, and then on to the next hop. Only Nimrod traffic will be forwarded to these boxes; non-Nimrod traffic will pass directly through the border routers. This topology is easily used when the connections to the border router are point-to-point links, as may be the case with service providers. Connecting the boundary forwarding agent to the border router in this manner allows the boundary forwarding agent to have a single default route pointing to the border router. This eliminates the need for Nimrod to exchange routing information with other routing protocols, e.g., BGP or OSPF, that are used by the border router. There are tradeoffs in the way the boundary forwarding agent is interconnected to the organization's network assets. One way is for the boundary forwarding agent to only be connected to the border router. This topology would require the border router to handle each Nimrod packet twice---once when it arrives at the border router from outside the organization destined to the boundary forwarding agent and once when it is passed from the boundary forwarding agent into the organization, and vice versa; it also requires another interface on the border router. 9 Internet Draft Nimrod Deployment January 1995 Another way would be to connect the boundary forwarding agent to a LAN that is directly connected to the border router. Using this topology, the each Nimrod packet would be handled once by the border router, but would appear twice in the LAN; no additional interfaces are required on the border router. Note that the LAN may be connected to other routers in addition to the border router. A third way that requires two interfaces on the boundary forwarding agent and one on the border router would be to connect the boundary forwarding agent to the border router and the boundary forwarding agent to a LAN. This topology would cause each Nimrod packet to be handled only once by the border router and boundary forwarding agent and it would appear only once on each link. Other topologies with slightly different tradeoffs are also possible. Each Nimrod box located at a border router must be configured with an EID, the types of agents it supports, the node's service attributes (if the node provides transit service), the node's (temporary) locator, the IP multicast address(es) associated with all Nimrod agents for the given node, and a default route to the border router. Note that because these boxes support the complete Nimrod functionality, they are capable of performing the discovery functions, including locator acquisition. Hence, each node will be able to acquire its own locator to replace the configured temporary locator. Endpoint Representatives -- Attach a Nimrod box to each LAN containing endpoints (hosts) that should take advantage of Nimrod packet forwarding. These boxes will act as endpoint representatives for the designated hosts. Each Nimrod host on the LAN should be configured with a default route pointing to the endpoint representative box, but the configuration of all other hosts should not be changed. Moreover, if the endpoint representative determines that a particular destination cannot be reached via Nimrod, it sends an ICMP Redirect back to the Nimrod host to route traffic for that destination directly to the preexisting LAN router. Hence, non-Nimrod traffic almost always travels directly to the LAN router. Each of these Nimrod boxes acting as an endpoint representative must be configured with an EID, the IP multicast address(es) associated with all Nimrod agents within the given node, the IP address of (one of) the LAN router(s), the service requirements of those hosts it serves, and the IP addresses of the hosts on whose behalf it acts, if different hosts should be given differing service requirements. Each endpoint representative will acquire the locators for the hosts on whose behalf it acts. Note that for certain topologies the endpoint representative functionality can be provided by the Nimrod boxes located next to the border routers and in these situations there would not have to be extra Nimrod boxes located near the hosts. The above deployment scenario has been designed to provide maximum Nimrod functionality with minimal effort. It requires only a small number of 10 Internet Draft Nimrod Deployment January 1995 Nimrod boxes per node, minimal configuration on the part of the administrators, no changes to routers or those hosts not using Nimrod services, and has no negative performance impacts on traffic to or from non-Nimrod hosts. Non-Nimrod traffic need never be processed by the Nimrod boxes. 3.4.2 Independent Implementation For those seeking to produce an independent implementation of Nimrod, we recommend a phased development of functionality. The phases in order of implementation are as follows: 1. Packet forwarding procedures. 2. Path setup protocol. 3. Map and association database maintenance including the update and query/response protocols. 4. Route generation procedures. 5. Discovery protocols. This functionality may be implemented across a combination of or completely within workstations, routers, and hosts. For the sake of this discussion, we assume that all Nimrod functionality is initially implemented in routers. Packet Forwarding -- A minimal Nimrod routing system provides Nimrod packet forwarding along preconfigured routes. In this case, only a node's boundary forwarding agents require any Nimrod functionality. Each boundary forwarding agent must be configured (e.g., using SNMP) with the routes to be used for specific traffic sessions. These routes list all the nodes that the packets pass through from source to destination and can be looked up using a key formed from the source and destination IP addresses contained in the data packets. Also, each of these agents must be configured with the IP addresses for the other boundary forwarding agents in the node and the locators for the neighboring nodes to which those boundary forwarding agents connect. This information is used to locate the boundary forwarding agent corresponding to the next hop along a specified route. Each of these boundary forwarding agents must also be able to execute a portion of the Nimrod path setup protocol and packet forwarding procedures. Initially, only the "datagram mode" packet forwarding need be implemented, provided that the route specification contained in each packet includes all intervening nodes. During path setup, forwarding agents normally perform checks on route consistency (e.g., the requested service is available through the node, the node permits traffic from the given source to use this 11 Internet Draft Nimrod Deployment January 1995 service) and resource availability (e.g., there is sufficient bandwidth on the next hop), but these checks need not be in place initially. Path Setup -- Once the datagram mode functionality is in place, the full path setup protocol including "flow mode" packet forwarding should be implemented. This includes both path setup and teardown, as well as route consistency and resource checks at boundary forwarding agents. With all of this functionality in place, both datagram and flow mode packet forwarding can be supported. Database Maintenance -- Both maps and endpoint/locator associations may be configured in boundary forwarding agents, e.g., a pre-loaded cache, for small numbers of nodes. Map distribution and association query functionality may be implemented to use that configured database information. Eventually, the entire database update and query/response protocols and the reliable transaction protocol should be put in place to reduce the amount of configuration required. Once boundary forwarding agents are able to determine the reachability of boundary forwarding agents in neighboring nodes and within the given node, they can then incorporate this information into their maps and can use the information to determine when an existing path is broken. Note that map construction using information from component nodes can be postponed until there are at least three levels in the clustering hierarchy. Route Generation -- Once it is possible to obtain maps, route generation algorithms can be implemented. We recommend implementing this functionality in routers attached to LANs whose hosts will be using the Nimrod routing system. These routers will act as route agents and as endpoint representatives, and thus must be configured with traffic service information for the hosts on whose behalf they generate routes. Nimrod Boxes -- Implementing all Nimrod functionality in routers is feasible when the Nimrod-capable portion of an internetwork consists of a small number of nodes. Eventually, the map, association, and route database maintenance (node representatives, association agents, and route agents) should be implemented in separate Nimrod boxes. To begin with, these boxes can be configured with the IP addresses, EIDs, and locators of the other such boxes with which they will communicate. Eventually, these configurations will become unmanageable, however, and at that point, the agent discovery mechanisms should be implemented. Ultimately, when Nimrod becomes popular, we expect vendors of networking products to implement Nimrod forwarding functionality in routers and Nimrod database functionality in specialized high-performance Nimrod boxes. A phased implementation minimizes the amount of Nimrod protocol implementation necessary to get portions of Nimrod up and running and ranks these phases according to their relative importance in providing Nimrod 12 Internet Draft Nimrod Deployment January 1995 functionality. The main disadvantage of this approach is the amount of configured information required to compensate for the missing protocols at certain stages. Each organization that produces a Nimrod implementation will have to decide on the tradeoffs between the approach given above and the associated costs, including development, documentation, training/customer support, and product releases. 4 Full-Scale Deployment Several Nimrod functions can be provided with modified versions of existing Internet services such as the Domain Name System and the Dynamic Host Configuration Protocol. For full-scale deployment of Nimrod, one should consider enhancing these services to include the functionality needed by Nimrod rather than implementing separate Nimrod-specific services. This will reduce the amount of implementation required to get a Nimrod routing system up and running. 4.1 Directory Services Existing directory services, such as those currently provided by the Domain Name System (DNS), can be expanded to handle associations between endpoint names and EIDs and locators. Each fully-qualified endpoint name will be associated one EID and one or more locators. It may be possible to get the necessary DNS server and resolver changes into the more popular code bases at the same time as the IPv6 additions. The association between endpoint name and EID is expected to change slowly, if at all, over time. The association between endpoint name and locators is expected to become more dynamic as endpoints become mobile and topology changes result in renumbering. Frequent updating of the DNS entries to correspond to the locations of rapidly moving endpoints, if in fact it turns out to be needed, is beyond the capabilities of the current DNS, but might be possible with a future version of DNS. We note that with the mobility approach currently proposed by the Mobile IP working group of the IETF, each mobile endpoint is associated with a "home" that remains stationary. Hence, only the home needs to track an endpoint's new location; dynamic endpoint locator information need not be updated in the DNS, as the DNS entry would only contain the locator of the home. This approach, however, also implies that some portion of traffic destined for a mobile endpoint must be sent via its home, often resulting in inefficient forwarding. This inefficiency is a property of the technique of using a home, whether or not Nimrod is used. 4.1.1 Format We now describe two ways of storing endpoint information in a directory. The first format, , has the advantage of permitting each endpoint to be individually configured. The second is a formatting optimization that reduces the number of directory records that 13 Internet Draft Nimrod Deployment January 1995 have to be updated when changing the locator for a node that contains many endpoints. With the second format, an endpoint's locator is split into two parts. The first part, or prefix, is the locator of a node that contains the endpoint, but not necessarily the lowest-level node containing the endpoint. Instead, it may refer to the node for the managing organization responsible for the endpoint or a node whose locator is likely to change often. The second part, or suffix, is the remaining portion of the node's locator. By storing the prefixes separately from the suffixes, none of the endpoint records have to be updated when the ancestral node's locator changes; only the single entry containing the prefix needs updating. For example, if an organization's provider prefix(es) are stored separately from the locators of the endpoints, then only the separately stored prefix would need to be updated when a provider changed the organizations prefix, e.g., when changing providers or renumbering to reduce costs after topology changes. When generating a reply to a locator query, the DNS will provide the prefix (there may be more than one prefix) and the suffix. It could concatenate them or leave the concatenation to the resolver and thus reduce the size of the DNS reply. We note that such techniques to simplify management of the directory can be implemented differently for each directory implementation. The issue of interoperability only arises when forming replies---must the locators be expanded in the replies or can they contain the abbreviated (non-concatenated) form---and when contracting for service from secondary directory servers, i.e., exchanging information between the primary and secondary DNS servers. 4.2 Host Changes Although changes to hosts are not required for initial deployment of Nimrod, they will eventually be required for hosts that wish to dynamically change their traffic service requirements, or to use the full EID functionality. Static configuration of traffic service requirements in endpoint representatives is not sufficient when service requirements change frequently. Instead, such hosts will need to communicate their service requirements to their endpoint representatives. The IPv4 and IPv6 packet headers currently allow a host to communicate coarse-grained traffic service requirements (e.g., low delay, high throughput), but do not permit communication of more specific services (e.g., bounds on maximum delay, minimum throughput, preferred service provider). For full-scale Nimrod deployment, Nimrod will have a protocol that enables hosts to communicate endpoint, e.g., DNS, names and traffic service requirements directly to Nimrod agents. Hosts with static service requirements need not implement this protocol, however. Endpoint representatives will be responsible for querying the DNS (using DNS names for hosts that supply this information and IP addresses for hosts that do not supply DNS names) to obtain the EID and locators for each endpoint, and for querying the route agent(s) for routes. Hosts may also be modified to 14 Internet Draft Nimrod Deployment January 1995 formulate their own DNS queries and to provide EID and locator information to endpoint representatives. This will eliminate a second DNS query by the endpoint representative. Furthermore, some hosts may even be modified to absorb all of the endpoint representative functionality. The network protocol stack must be modified to use EIDs when demultiplexing at the transport layer, and not base that operation on the address. Note that some hosts may support applications that require support for more than a single EID. Changes in the way that information from, e.g., DNS responses, is passed to the appropriate protocol layers will be needed. This may require changes to the current application programming interface (API) as they do not support the EID concept. The hosts will need to be able to support multiple locators, i.e., addresses, on a single interface. An interface to the configuration server and entity representative will be needed to allow the set of locators to be changed, through addition, removal, replacement, or a change in preference. The locator update process to the host must be done securely, as must any associated DNS update. 4.3 Boot Server Changes As noted above, full-scale deployment will require extensions to the mechanisms used to load configuration information into a host, e.g., using the Dynamic Host Configuration Protocol. This issue will be covered in a later version of this document. 4.4 EID Administration Once EIDs are in common use, there will need to be a mechanism to allocate them for each endpoint. Since the EID space is to be densely packed, handing out large blocks is undesirable. One way that might be used to solve this problem and reduce the amount of human labor required would be to provide EID Servers throughout the internet. They might be email based. Send a message containing an endpoint name to the server, and receive a reply containing the endpoint name and the assigned EID, possibly in the form of a DNS record to reduce the chance of human error. There could even be a background process to lookup the specified endpoint name and verify that the EID was correctly entered into the system. This process can be made robust and still provide quick turnaround. 5 Security Considerations Nimrod's main functions are distribution and manipulation of routing-related information contained within its databases. Corruption of this information can lead to communication failures, some affecting large portions of an internetwork. Hence, all Nimrod routing information must be protected from corruption to the extent practical. In particular, source authentication and information integrity checks should be performed on all Nimrod routing information distributed throughout an internetwork. To the 15 Internet Draft Nimrod Deployment January 1995 extent possible, Nimrod will take advantage of the security and key management protocols developed by the IETF and other standards bodies. If these security mechanisms (e.g., authentication in IPv6) are not available by the time of initial Nimrod deployment, the deployed version of Nimrod will contain its own selectable authentication and integrity mechanisms (as in IDPR), within the overall framework provided for IPv6. 5.1 Accountability This section provides motivation for security services that the Nimrod routing system will need. A more detailed discussion of the points will be presented in a Nimrod Security Architecture document. 5.1.1 Integrity of Routing Information Recall that the basic routing information flow in Nimrod is for information generated at the lowest levels to be gathered, abstracted, and filtered as it is passed up the clustering hierarchy. Endpoints request routes through their enpoint representative, one or more route agents, and node representatives. Any maps cached by a route agent should contain the credentials that were used to obtain the map. The resulting route is returned to the endpoint, or its representative, and used to establish a path through the various forwarding agents. Corruption within the network or the information processing components can be detected through use of integrity services. 5.1.2 Compromised Components One must consider the threat of a compromised component that either advertizes services that are not available or does not advertize services that are available. Detecting either of these situations is very difficult since similar advertizements could be the result of the aggregation and/or filtering algorithms used within a node, e.g., an "optimistic" or a "pessimistic" algorithm. However, if a route agent is suspicious of an advertizement it can always ask for maps at lower levels of the hierarchy. The threat then becomes whether a route agent can be denied access to the lower level node representatives within the hierarchy. It is difficult to provide mechanisms that prevent false information from being advertized. What Nimrod does is to make it clear where any piece of information originated, by having it signed. It provides the mechanisms that allow any endpoint or administration to incorporate previous experience when expressing its preferences to a route agent so as to encourage or prohibit its traffic from traversing portions of the internetwork. 16 Internet Draft Nimrod Deployment January 1995 5.1.3 Interactions with Other Internetwork Subsystems The Nimrod routing system also interacts with other components of the internet infrastructure. Examples of these interactions are changes to an endpoint's locator(s), e.g., renumbering, in response to topology changes, and the resulting update to both the association database, e.g., DNS, and the set of valid locators within the endpoint itself. There is an IETF working group investigating mechanisms for secure DNS updates as part of the IPv6 effort that we hope to build upon. These interactions must also be considered when analyzing potential threats to the integrity of the routing system. 5.1.4 Enhanced Service Considerations The inclusion of policy and quality of service information will require additional security services not present in current routing protocols. When charging for special services becomes more dynamic, it is likely that endpoints will want assurance that rates advertized by providers through the Nimrod routing system cannot be repudiated. Providers might also want assurance that customers of their service meet any restrictions the provider has placed on users of their services, and that endpoints cannot repudiate having sent the packets. A non-repudiation security service can be used to facilitate this requirement. The issue arises of what an endpoint should place into a data packet so that the multiple providers that handle the packet can be assured the packet was in fact sent by the endpoint and that the endpoint is authorized to use the services requested. The latter function can be validated at path setup time. Including an object per provider in each packet does not scale well, either in terms of packet size or processing required to find the appropriate object for a specific provider. A scalable technique would be to include a key in the setup request that was then part of the authenticated part of each packet sent. One problem with this approach is that providers then need to keep track of the object on a flow-by-flow basis. Whatever mechanism that is used would need a mechanism, e.g., a timestamp or sequence number, to be able to detect replay attacks. This endpoint to intermediate system authentication is separate from any end-to-end authentication required by the endpoints. This implies that data packets might have, in the context of IPv6, two authentication headers. The endpoint to intermediate system authentication would only be processed by those providers that require it and those providers might choose to only verify selected packets. Also, whatever verification scheme is used by the providers should not cause undue packet reordering, as likely candidates for enhanced service are real-time applications. When combined with a non-repudiation service, a provider could then prove, for example, that an endpoint did in fact send packets for which it was being billed. 17 Internet Draft Nimrod Deployment January 1995 5.2 Summary of Nimrod Security Services o All Nimrod protocols use authentication and integrity services. o All information is signed by originator. o Queries to endpoint representatives, route agents, and node representatives contain authentication information for each agent handling the query. o Advertized services and restrictions on their use may not be repudiated. o Endpoints may not repudiate sending packets that use special services. 6 Utilities There are several tools that should be developed to demonstrate the features of the Nimrod routing system and to assist with deployment and ongoing administration. They are not part of the core Nimrod protocols and can be developed independently from that effort (although their availability would make the protocol work easier). It may not be the case that the internal representation of a map is the same as an external representation as might be stored in a configuration file. A utility that converts between formats will be useful, both to initialize the maps in a node representative, and to save maps for subsequent analysis during debugging and ongoing operations. A utility, perhaps SNMP based, that collected and displayed the forwarding information and paths in forwarding agents will be useful during debugging and ongoing operation. A utility that could query for, combine, and save maps and display them graphically will help administrators visualize the Nimrod representation of their networks. It can also be used to illustrate to prospective Nimrod users how others have organized their networks and thus would provide models for their own organization. Similarly, a utility that accepts service requirements and endpoints and requests candidate routes would be useful. It would be similar to the common traceroute tool that has proven so useful in solving operational problems. It could graphically display the resulting routes, highlighting points where service requirements resulted in failure of a candidate route. It could be enhanced so that the user could guide exploration of the topology, and could even return a desirable route to an organization's route agents for caching and subsequent use. A graphical tool that let an organization explore alternative clustering hierarchies and evaluate and observe the results of different clustering and abstraction algorithms would help administrators select the best candidate. It might be possible to make the tool accept modifications from the user, 18 Internet Draft Nimrod Deployment January 1995 learn the rules that were used, load them into the organization's node representatives, and then apply those rules for subsequent abstraction and filtering operations. Currently existing tools, such as DNS lookup utilities and SNMP managers and agents will need to be extended to handle the new information useful to Nimrod. The EID Server described in section 4.4 is another utility that will simplify the deployment of Nimrod. 7 Author's Address Charles Lynn BBN Systems and Technologies 10 Moulton Street Cambridge, MA 02138 Phone: (617) 873-3367 Email: CLynn@BBN.Com References [1] I. Castineyra, J. N. Chiappa, and M. Steenstrup. "The Nimrod Routing Architecture". June 1994. Working Draft. [2] M. Steenstrup. "A Perspective on Nimrod Functionality". July 1994. Working Draft. [3] S. Ramanathan. "Multicast Support for Nimrod: Requirements and Approaches". June 1994. Working Draft. [4] S. Ramanathan. "Mobility Support for Nimrod: Requirements and Approaches". June 1994. Working Draft. [5] M. Steenstrup. "Inter-Domain Policy Routing Protocol Specification: Version 1". July 1993. RFC 1479. 19   Received: from PIZZA.BBN.COM by BBN.COM id aa04277; 17 Jan 95 18:47 EST Received: from pizza by PIZZA.BBN.COM id aa24635; 17 Jan 95 18:33 EST Received: from BBN.COM by PIZZA.BBN.COM id aa24629; 17 Jan 95 18:30 EST Received: from GAAK.BBN.COM by BBN.COM id aa02010; 17 Jan 95 18:29 EST Date: Tue, 17 Jan 1995 18:29:51 EST Message-ID: To: clynn@BBN.COM CC: nimrod-wg@BBN.COM In-reply-to: message from Charles Lynn on Fri, 13 Jan 95 20:50:11 EST Subject: Re: Draft of Nimrod Deployment Plan From: "Michael A. Patton" Reply-To: "Michael A. Patton, NIMROD mail" Just a simple note on one part of Charlie's draft: In section "4.1 Directory Services", the second paragraph ends with: ... updating of the DNS... is beyond the capabilities of the current DNS, ... This exact functionality is presently under development in the DNSIND working group (which I'm a member of) and I expect will be available before even the early stages of NIMROD deployment. So this should not be a constraint on what we can do. -MAP   Received: from PIZZA.BBN.COM by BBN.COM id aa23605; 8 Feb 95 14:37 EST Received: from pizza by PIZZA.BBN.COM id aa10535; 8 Feb 95 14:06 EST Received: from BBN.COM by PIZZA.BBN.COM id aa10529; 8 Feb 95 14:01 EST Received: from ginger.lcs.mit.edu by BBN.COM id aa16339; 8 Feb 95 13:26 EST Received: by ginger.lcs.mit.edu id AA27658; Wed, 8 Feb 95 13:26:11 -0500 Date: Wed, 8 Feb 95 13:26:11 -0500 From: Noel Chiappa Message-Id: <9502081826.AA27658@ginger.lcs.mit.edu> To: nimrod-wg@BBN.COM Subject: The IP model, locality, ATM and NDM Cc: jnc@ginger.lcs.mit.edu, yakov@watson.ibm.com You all might be interested in taking a look at a new I-D from Yakov, "draft-rekhter-ip-atm-architecture-00.txt", which talks about some basic changes to the internetwork architectural model to work bettter with ATM. It's very reminiscent of the New Datagram Mode in Nimrod, in that it uses pre-setup VC's through routers for datagram applications, but sets up separate, more direct, VC's for long-lived applications. The interesting difference is that it extends the basic model to say that hosts which do not appear (from their addresses) to be directly connected, but do in fact share a common ATM substrate, can communicate directly. It doesn't directly solve the issue of a general mechanism that two hosts can use to discover that they share a common substrate. I'm sitting here musing, trying to make sure that Nimrod can provide this capability from scratch, and I think it can. I think what we'd have to do is model the LIS's as separate nodes, all connected to a node which represents the complete ATM mesh, but without going through routers. That way, if you emit a datagram to your nearest router (as you would normally do in NDM), it can go down the pre-setup DMF's as usual, but you can still tell, from looking at the map, that you can get directly from your host to another without going through a router, and so can set up a direct VC for longer-lived applications. On a more architectural level, I've said for a long time that we should get rid of the simple "match-and-mask" algorithm for deciding whether something is local or distant, and instead let the routers handle this. I.e. you'd always send the first packet to a router, and it would send you a redirect if the destination was directly reachable. (If your net was disjoint, and had no routers, you would always try going direct, since you couldn't get to any non-directly-connected destination anyway.) The intent here was laudable, in that I wanted to get hosts out of the business of trying to discover whether some destination was local or not. Doing this by use of some simple local algorithm in the host, based on the addresses, was inflexible. Taking this part of the problem, and putting it in the routers, seemed to be more flexible. However, now that I think about it, there is an aspect of it that we do need to be careful of, which is that the old model of "put the intelligence in the routers" is going against the thrust of the "devolution" principle, which says to get the routers out of making decisions on other people's behalf, since they won't always get it right. I'm not quite sure what this means for us here. I suspect that perhaps my initial idea, getting rid of the match-and-mask is in fact the right "next step" for IPv4 (and similar systems, such as SIPP), in that it does get rid of that inflexibility. However, in the long run, we need to do something more subtle than simply always have the router send a redirect, and the host always obey it. This would do the wrong thing on an ATM net, if, for instance, an application wanted to send two datagrams. Under a simple model of how to proceed, it sends the first packet to the router, which sends a redirect, and before the the second packet can go, a VC is set up directly to the destination. Not too swift... So an intermediate first step would be to have the router send a redirect, but for the host to be able to ignore it. (Having the router not send a second redirect probably requires more state, and mechanism, in the router that seems worth it.) The host gets the redirect, which tells it something is directly reachable (a key part of the mechanism that's missing now), and then, on an ATM or similar WAN network, it can make up its own mind as to whether this warrants a VC or not. (Obviously, some mechanism is needed to get the MAC address, but that's a different problem.) This is however, still working within a basic model where the routers are making decisions on paths, and the primary information channel back to the hosts is redirects. So while this may the right thing for a non-Nimrod environment, I'm not sure it applies here. I guess that in Nimrod we can dispense with a lot of this. The host can simply examine the map, to determine whether the destination is local or not, in those cases where it cares. Since the destinations MAC address is part of the Nimrod locator, that problem doesn't exist either. Does this all seem reasonable? Noel   Received: from PIZZA.BBN.COM by BBN.COM id aa12452; 13 Feb 95 16:18 EST Received: from pizza by PIZZA.BBN.COM id aa08426; 13 Feb 95 15:58 EST Received: from BBN.COM by PIZZA.BBN.COM id aa08422; 13 Feb 95 15:54 EST Received: from ietf.cnri.reston.va.us by BBN.COM id ab07462; 13 Feb 95 15:37 EST Received: from [127.0.0.1] by IETF.CNRI.Reston.VA.US id aa06884; 13 Feb 95 14:12 EST Mime-Version: 1.0 Content-Type: Multipart/Mixed; Boundary="NextPart" To: IETF-Announce: ; cc: nimrod-wg@BBN.COM From: Internet-Drafts@cnri.reston.va.us Reply-to: Internet-Drafts@cnri.reston.va.us Subject: I-D ACTION:draft-ietf-nimrod-multicast-00.txt, .ps Date: Mon, 13 Feb 95 14:12:10 -0500 Sender: cclark@cnri.reston.va.us Message-ID: <9502131412.aa06884@IETF.CNRI.Reston.VA.US> --NextPart A New Internet-Draft is available from the on-line Internet-Drafts directories. This draft is a work item of the New Internet Routing and Addressing Architecture Working Group of the IETF. Title : Multicast Support for Nimrod : Requirements and Solution Approaches Author(s) : R. Ramanathan Filename : draft-ietf-nimrod-multicast-00.txt, .ps Pages : 20 Date : 02/10/1995 We discuss the issue of multicasting in Nimrod. We identify the requirements that Nimrod has of any solution for multicast support. We compare existing approaches for multicasting within an internetwork and discuss their advantages and disadvantages. Finally, as an example, we outline the mechanisms to support multicast in Nimrod using the scheme currently being developed within the IETF - namely, the Protocol Indpendent Multicast (PIM) protocol. Internet-Drafts are available by anonymous FTP. Login with the username "anonymous" and a password of your e-mail address. After logging in, type "cd internet-drafts" and then "get draft-ietf-nimrod-multicast-00.txt". Or "get draft-ietf-nimrod-multicast-00.ps". A URL for the Internet-Draft is: ftp://ds.internic.net/internet-drafts/draft-ietf-nimrod-multicast-00.txt Internet-Drafts directories are located at: o Africa Address: ftp.is.co.za (196.4.160.2) o Europe Address: nic.nordu.net (192.36.148.17) o Pacific Rim Address: munnari.oz.au (128.250.1.21) o US East Coast Address: ds.internic.net (198.49.45.10) o US West Coast Address: ftp.isi.edu (128.9.0.32) Internet-Drafts are also available by mail. Send a message to: mailserv@ds.internic.net. In the body type: "FILE /internet-drafts/draft-ietf-nimrod-multicast-00.txt". Or "FILE /internet-drafts/draft-ietf-nimrod-multicast-00.ps". NOTE: The mail server at ds.internic.net can return the document in MIME-encoded form by using the "mpack" utility. To use this feature, insert the command "ENCODING mime" before the "FILE" command. To decode the response(s), you will need "munpack" or a MIME-compliant mail reader. Different MIME-compliant mail readers exhibit different behavior, especially when dealing with "multipart" MIME messages (i.e., documents which have been split up into multiple messages), so check your local documentation on how to manipulate these messages. For questions, please mail to Internet-Drafts@cnri.reston.va.us. Below is the data which will enable a MIME compliant mail reader implementation to automatically retrieve the ASCII version of the Internet-Draft. --NextPart Content-Type: Multipart/Alternative; Boundary="OtherAccess" --OtherAccess Content-Type: Message/External-body; access-type="mail-server"; server="mailserv@ds.internic.net" Content-Type: text/plain Content-ID: <19950210115413.I-D@CNRI.Reston.VA.US> ENCODING mime FILE /internet-drafts/draft-ietf-nimrod-multicast-00.txt --OtherAccess Content-Type: Message/External-body; name="draft-ietf-nimrod-multicast-00.txt"; site="ds.internic.net"; access-type="anon-ftp"; directory="internet-drafts" Content-Type: text/plain Content-ID: <19950210115413.I-D@CNRI.Reston.VA.US> --OtherAccess-- --NextPart--   Received: from PIZZA.BBN.COM by BBN.COM id aa12495; 13 Feb 95 16:19 EST Received: from pizza by PIZZA.BBN.COM id aa08420; 13 Feb 95 15:58 EST Received: from BBN.COM by PIZZA.BBN.COM id aa08416; 13 Feb 95 15:53 EST Received: from ietf.cnri.reston.va.us by BBN.COM id aa07462; 13 Feb 95 15:37 EST Received: from [127.0.0.1] by IETF.CNRI.Reston.VA.US id aa06870; 13 Feb 95 14:12 EST Mime-Version: 1.0 Content-Type: Multipart/Mixed; Boundary="NextPart" To: IETF-Announce: ; cc: nimrod-wg@BBN.COM From: Internet-Drafts@cnri.reston.va.us Reply-to: Internet-Drafts@cnri.reston.va.us Subject: I-D ACTION:draft-ietf-nimrod-mobility-00.txt, .ps Date: Mon, 13 Feb 95 14:12:06 -0500 Sender: cclark@cnri.reston.va.us Message-ID: <9502131412.aa06870@IETF.CNRI.Reston.VA.US> --NextPart A New Internet-Draft is available from the on-line Internet-Drafts directories. This draft is a work item of the New Internet Routing and Addressing Architecture Working Group of the IETF. Title : Mobility Support for Nimrod : Requirements and Solution Approaches Author(s) : R. Ramanathan Filename : draft-ietf-nimrod-mobility-00.txt, .ps Pages : 15 Date : 02/10/1995 We discuss the issue of mobility in Nimrod. We identify the requirements that Nimrod has of any solution for mobility support. We also classify and compare existing approaches for supporting mobility within an internetwork and discuss their advantages and disadvantages. Finally, as an example, we outline the mechanisms to support mobility in Nimrod using the scheme currently being developed within the IETF - namely, the Mobile-IP protocol. Internet-Drafts are available by anonymous FTP. Login with the username "anonymous" and a password of your e-mail address. After logging in, type "cd internet-drafts" and then "get draft-ietf-nimrod-mobility-00.txt". Or "get draft-ietf-nimrod-mobility-00.ps". A URL for the Internet-Draft is: ftp://ds.internic.net/internet-drafts/draft-ietf-nimrod-mobility-00.txt Internet-Drafts directories are located at: o Africa Address: ftp.is.co.za (196.4.160.2) o Europe Address: nic.nordu.net (192.36.148.17) o Pacific Rim Address: munnari.oz.au (128.250.1.21) o US East Coast Address: ds.internic.net (198.49.45.10) o US West Coast Address: ftp.isi.edu (128.9.0.32) Internet-Drafts are also available by mail. Send a message to: mailserv@ds.internic.net. In the body type: "FILE /internet-drafts/draft-ietf-nimrod-mobility-00.txt". Or "FILE /internet-drafts/draft-ietf-nimrod-mobility-00.ps". NOTE: The mail server at ds.internic.net can return the document in MIME-encoded form by using the "mpack" utility. To use this feature, insert the command "ENCODING mime" before the "FILE" command. To decode the response(s), you will need "munpack" or a MIME-compliant mail reader. Different MIME-compliant mail readers exhibit different behavior, especially when dealing with "multipart" MIME messages (i.e., documents which have been split up into multiple messages), so check your local documentation on how to manipulate these messages. For questions, please mail to Internet-Drafts@cnri.reston.va.us. Below is the data which will enable a MIME compliant mail reader implementation to automatically retrieve the ASCII version of the Internet-Draft. --NextPart Content-Type: Multipart/Alternative; Boundary="OtherAccess" --OtherAccess Content-Type: Message/External-body; access-type="mail-server"; server="mailserv@ds.internic.net" Content-Type: text/plain Content-ID: <19950210114416.I-D@CNRI.Reston.VA.US> ENCODING mime FILE /internet-drafts/draft-ietf-nimrod-mobility-00.txt --OtherAccess Content-Type: Message/External-body; name="draft-ietf-nimrod-mobility-00.txt"; site="ds.internic.net"; access-type="anon-ftp"; directory="internet-drafts" Content-Type: text/plain Content-ID: <19950210114416.I-D@CNRI.Reston.VA.US> --OtherAccess-- --NextPart--   Received: from PIZZA.BBN.COM by BBN.COM id aa04780; 15 Feb 95 3:35 EST Received: from pizza by PIZZA.BBN.COM id aa20718; 15 Feb 95 0:03 EST Received: from BBN.COM by PIZZA.BBN.COM id aa20714; 15 Feb 95 0:00 EST Received: from [131.112.32.132] by BBN.COM id aa11961; 14 Feb 95 22:25 EST Received: by necom830.cc.titech.ac.jp (5.65+/necom-mx-rg); Fri, 10 Feb 95 00:14:02 +0900 From: Masataka Ohta Return-Path: Message-Id: <9502091514.AA01340@necom830.cc.titech.ac.jp> Subject: Re: The IP model, locality, ATM and NDM To: Noel Chiappa Date: Fri, 10 Feb 95 0:14:01 JST Cc: nimrod-wg@BBN.COM, jnc@ginger.lcs.mit.edu, yakov@watson.ibm.com In-Reply-To: <9502081826.AA27658@ginger.lcs.mit.edu>; from "Noel Chiappa" at Feb 8, 95 1:26 pm X-Mailer: ELM [version 2.3 PL11] > You all might be interested in taking a look at a new I-D from Yakov, > "draft-rekhter-ip-atm-architecture-00.txt", which talks about some basic > changes to the internetwork architectural model to work bettter with ATM. Unfortunately for you, it was just discussed in ATM WG ML that such changes are unnecessary. > It's very reminiscent of the New Datagram Mode in Nimrod, in that it > uses pre-setup VC's through routers for datagram applications, but sets up > separate, more direct, VC's for long-lived applications. It merely means that we should support flows or RSVP, which does not at all imply any architectural changes. > The interesting difference is that it extends the basic model to say > that hosts which do not appear (from their addresses) to be directly > connected, but do in fact share a common ATM substrate, can communicate > directly. ATM is OK. What was bad was LIS. > It doesn't directly solve the issue of a general mechanism that two > hosts can use to discover that they share a common substrate. As usual, you can use subnet mask. > I'm sitting here musing, trying to make sure that Nimrod can provide > this capability from scratch, and I think it can. I think what we'd have to do > is model the LIS's as separate nodes, all connected to a node which represents > the complete ATM mesh, but without going through routers. As LIS is NOT physically conteguous and a single LIS may possibly expand world wide over many routing domains, it is impossible to see it a node. To see something a node, you must make it physically conteguous (that is, NOT LIS (*LOGICAL* IP Subnet)). Then, you don't need any IP architecture extension regardless of whether you use NIMROD or not. Masataka Ohta   Received: from PIZZA.BBN.COM by BBN.COM id aa11515; 28 Feb 95 19:52 EST Received: from pizza by PIZZA.BBN.COM id aa25160; 28 Feb 95 19:38 EST Received: from BBN.COM by PIZZA.BBN.COM id aa25156; 28 Feb 95 19:36 EST Received: from ietf.cnri.reston.va.us by BBN.COM id ab10313; 28 Feb 95 19:22 EST Received: from [127.0.0.1] by IETF.CNRI.Reston.VA.US id aa10780; 28 Feb 95 15:52 EST Mime-Version: 1.0 Content-Type: Multipart/Mixed; Boundary="NextPart" To: IETF-Announce: ; cc: nimrod-wg@BBN.COM From: Internet-Drafts@cnri.reston.va.us Reply-to: Internet-Drafts@cnri.reston.va.us Subject: I-D ACTION:draft-ietf-nimrod-mobility-01.txt, .ps Date: Tue, 28 Feb 95 15:52:42 -0500 Sender: cclark@cnri.reston.va.us Message-ID: <9502281552.aa10780@IETF.CNRI.Reston.VA.US> --NextPart A Revised Internet-Draft is available from the on-line Internet-Drafts directories. This draft is a work item of the New Internet Routing and Addressing Architecture Working Group of the IETF. Title : Mobility Support for Nimrod : Requirements and Solution Approaches Author(s) : R. Ramanathan Filename : draft-ietf-nimrod-mobility-01.txt, .ps Pages : 16 Date : 02/27/1995 We discuss the issue of mobility in Nimrod. We identify the requirements that Nimrod has of any solution for mobility support. We also classify and compare existing approaches for supporting mobility within an internetwork and discuss their advantages and disadvantages. Finally, as an example, we outline the mechanisms to support mobility in Nimrod using the scheme currently being developed within the IETF - namely, the Mobile-IP protocol. Internet-Drafts are available by anonymous FTP. Login with the username "anonymous" and a password of your e-mail address. After logging in, type "cd internet-drafts" and then "get draft-ietf-nimrod-mobility-01.txt". Or "get draft-ietf-nimrod-mobility-01.ps". A URL for the Internet-Draft is: ftp://ds.internic.net/internet-drafts/draft-ietf-nimrod-mobility-01.txt Internet-Drafts directories are located at: o Africa Address: ftp.is.co.za (196.4.160.2) o Europe Address: nic.nordu.net (192.36.148.17) o Pacific Rim Address: munnari.oz.au (128.250.1.21) o US East Coast Address: ds.internic.net (198.49.45.10) o US West Coast Address: ftp.isi.edu (128.9.0.32) Internet-Drafts are also available by mail. Send a message to: mailserv@ds.internic.net. In the body type: "FILE /internet-drafts/draft-ietf-nimrod-mobility-01.txt". Or "FILE /internet-drafts/draft-ietf-nimrod-mobility-01.ps". NOTE: The mail server at ds.internic.net can return the document in MIME-encoded form by using the "mpack" utility. To use this feature, insert the command "ENCODING mime" before the "FILE" command. To decode the response(s), you will need "munpack" or a MIME-compliant mail reader. Different MIME-compliant mail readers exhibit different behavior, especially when dealing with "multipart" MIME messages (i.e., documents which have been split up into multiple messages), so check your local documentation on how to manipulate these messages. For questions, please mail to Internet-Drafts@cnri.reston.va.us. Below is the data which will enable a MIME compliant mail reader implementation to automatically retrieve the ASCII version of the Internet-Draft. --NextPart Content-Type: Multipart/Alternative; Boundary="OtherAccess" --OtherAccess Content-Type: Message/External-body; access-type="mail-server"; server="mailserv@ds.internic.net" Content-Type: text/plain Content-ID: <19950227173159.I-D@CNRI.Reston.VA.US> ENCODING mime FILE /internet-drafts/draft-ietf-nimrod-mobility-01.txt --OtherAccess Content-Type: Message/External-body; name="draft-ietf-nimrod-mobility-01.txt"; site="ds.internic.net"; access-type="anon-ftp"; directory="internet-drafts" Content-Type: text/plain Content-ID: <19950227173159.I-D@CNRI.Reston.VA.US> --OtherAccess-- --NextPart--   Received: from PIZZA.BBN.COM by BBN.COM id aa11543; 28 Feb 95 19:53 EST Received: from pizza by PIZZA.BBN.COM id aa25132; 28 Feb 95 19:35 EST Received: from BBN.COM by PIZZA.BBN.COM id aa25128; 28 Feb 95 19:32 EST Received: from ietf.cnri.reston.va.us by BBN.COM id aa10313; 28 Feb 95 19:22 EST Received: from [127.0.0.1] by IETF.CNRI.Reston.VA.US id aa10746; 28 Feb 95 15:52 EST Mime-Version: 1.0 Content-Type: Multipart/Mixed; Boundary="NextPart" To: IETF-Announce: ; cc: nimrod-wg@BBN.COM From: Internet-Drafts@cnri.reston.va.us Reply-to: Internet-Drafts@cnri.reston.va.us Subject: I-D ACTION:draft-ietf-nimrod-multicast-01.txt, .ps Date: Tue, 28 Feb 95 15:51:58 -0500 Sender: cclark@cnri.reston.va.us Message-ID: <9502281552.aa10746@IETF.CNRI.Reston.VA.US> --NextPart A Revised Internet-Draft is available from the on-line Internet-Drafts directories. This draft is a work item of the New Internet Routing and Addressing Architecture Working Group of the IETF. Title : Multicast Support for Nimrod : Requirements and Solution Approaches Author(s) : R. Ramanathan Filename : draft-ietf-nimrod-multicast-01.txt, .ps Pages : 20 Date : 02/27/1995 We discuss the issue of multicasting in Nimrod. We identify the requirements that Nimrod has of any solution for multicast support. We compare existing approaches for multicasting within an internetwork and discuss their advantages and disadvantages. Finally, as an example, we outline the mechanisms to support multicast in Nimrod using the scheme currently being developed within the IETF - namely, the Protocol Indpendent Multicast (PIM) protocol. Internet-Drafts are available by anonymous FTP. Login with the username "anonymous" and a password of your e-mail address. After logging in, type "cd internet-drafts" and then "get draft-ietf-nimrod-multicast-01.txt". Or "get draft-ietf-nimrod-multicast-01.ps". A URL for the Internet-Draft is: ftp://ds.internic.net/internet-drafts/draft-ietf-nimrod-multicast-01.txt Internet-Drafts directories are located at: o Africa Address: ftp.is.co.za (196.4.160.2) o Europe Address: nic.nordu.net (192.36.148.17) o Pacific Rim Address: munnari.oz.au (128.250.1.21) o US East Coast Address: ds.internic.net (198.49.45.10) o US West Coast Address: ftp.isi.edu (128.9.0.32) Internet-Drafts are also available by mail. Send a message to: mailserv@ds.internic.net. In the body type: "FILE /internet-drafts/draft-ietf-nimrod-multicast-01.txt". Or "FILE /internet-drafts/draft-ietf-nimrod-multicast-01.ps". NOTE: The mail server at ds.internic.net can return the document in MIME-encoded form by using the "mpack" utility. To use this feature, insert the command "ENCODING mime" before the "FILE" command. To decode the response(s), you will need "munpack" or a MIME-compliant mail reader. Different MIME-compliant mail readers exhibit different behavior, especially when dealing with "multipart" MIME messages (i.e., documents which have been split up into multiple messages), so check your local documentation on how to manipulate these messages. For questions, please mail to Internet-Drafts@cnri.reston.va.us. Below is the data which will enable a MIME compliant mail reader implementation to automatically retrieve the ASCII version of the Internet-Draft. --NextPart Content-Type: Multipart/Alternative; Boundary="OtherAccess" --OtherAccess Content-Type: Message/External-body; access-type="mail-server"; server="mailserv@ds.internic.net" Content-Type: text/plain Content-ID: <19950227173509.I-D@CNRI.Reston.VA.US> ENCODING mime FILE /internet-drafts/draft-ietf-nimrod-multicast-01.txt --OtherAccess Content-Type: Message/External-body; name="draft-ietf-nimrod-multicast-01.txt"; site="ds.internic.net"; access-type="anon-ftp"; directory="internet-drafts" Content-Type: text/plain Content-ID: <19950227173509.I-D@CNRI.Reston.VA.US> --OtherAccess-- --NextPart--   Received: from PIZZA.BBN.COM by BBN.COM id aa08658; 1 Mar 95 19:04 EST Received: from pizza by PIZZA.BBN.COM id aa01753; 1 Mar 95 18:42 EST Received: from BBN.COM by PIZZA.BBN.COM id aa01746; 1 Mar 95 18:39 EST Received: from ietf.cnri.reston.va.us by BBN.COM id ab06895; 1 Mar 95 18:33 EST Received: from [127.0.0.1] by IETF.CNRI.Reston.VA.US id aa11664; 1 Mar 95 17:38 EST Mime-Version: 1.0 Content-Type: Multipart/Mixed; Boundary="NextPart" To: IETF-Announce: ; cc: nimrod-wg@BBN.COM From: Internet-Drafts@cnri.reston.va.us Reply-to: Internet-Drafts@cnri.reston.va.us Subject: I-D ACTION:draft-ietf-nimrod-routing-arch-00.txt Date: Wed, 01 Mar 95 17:38:25 -0500 Sender: cclark@cnri.reston.va.us Message-ID: <9503011738.aa11664@IETF.CNRI.Reston.VA.US> --NextPart A New Internet-Draft is available from the on-line Internet-Drafts directories. This draft is a work item of the New Internet Routing and Addressing Architecture Working Group of the IETF. Title : The Nimrod Routing Architecture Author(s) : I. Castineyra, J. Chiappa, M. Steenstrup Filename : draft-ietf-nimrod-routing-arch-00.txt Pages : 29 Date : 02/28/1995 We present a scalable internetwork routing architecture, called Nimrod. The Nimrod architecture is designed to accommodate a dynamic internetwork of arbitrary size with heterogeneous service requirements and restrictions and to admit incremental deployment throughout an internetwork. The key to Nimrod's scalability is its ability to represent and manipulate routing-related information at multiple levels of abstraction. Internet-Drafts are available by anonymous FTP. Login with the username "anonymous" and a password of your e-mail address. After logging in, type "cd internet-drafts" and then "get draft-ietf-nimrod-routing-arch-00.txt". A URL for the Internet-Draft is: ftp://ds.internic.net/internet-drafts/draft-ietf-nimrod-routing-arch-00.txt Internet-Drafts directories are located at: o Africa Address: ftp.is.co.za (196.4.160.2) o Europe Address: nic.nordu.net (192.36.148.17) o Pacific Rim Address: munnari.oz.au (128.250.1.21) o US East Coast Address: ds.internic.net (198.49.45.10) o US West Coast Address: ftp.isi.edu (128.9.0.32) Internet-Drafts are also available by mail. Send a message to: mailserv@ds.internic.net. In the body type: "FILE /internet-drafts/draft-ietf-nimrod-routing-arch-00.txt". NOTE: The mail server at ds.internic.net can return the document in MIME-encoded form by using the "mpack" utility. To use this feature, insert the command "ENCODING mime" before the "FILE" command. To decode the response(s), you will need "munpack" or a MIME-compliant mail reader. Different MIME-compliant mail readers exhibit different behavior, especially when dealing with "multipart" MIME messages (i.e., documents which have been split up into multiple messages), so check your local documentation on how to manipulate these messages. For questions, please mail to Internet-Drafts@cnri.reston.va.us. Below is the data which will enable a MIME compliant mail reader implementation to automatically retrieve the ASCII version of the Internet-Draft. --NextPart Content-Type: Multipart/Alternative; Boundary="OtherAccess" --OtherAccess Content-Type: Message/External-body; access-type="mail-server"; server="mailserv@ds.internic.net" Content-Type: text/plain Content-ID: <19950228160149.I-D@CNRI.Reston.VA.US> ENCODING mime FILE /internet-drafts/draft-ietf-nimrod-routing-arch-00.txt --OtherAccess Content-Type: Message/External-body; name="draft-ietf-nimrod-routing-arch-00.txt"; site="ds.internic.net"; access-type="anon-ftp"; directory="internet-drafts" Content-Type: text/plain Content-ID: <19950228160149.I-D@CNRI.Reston.VA.US> --OtherAccess-- --NextPart--   Received: from PIZZA.BBN.COM by BBN.COM id aa03854; 2 Mar 95 12:33 EST Received: from pizza by PIZZA.BBN.COM id aa06027; 2 Mar 95 12:06 EST Received: from BBN.COM by PIZZA.BBN.COM id aa06023; 2 Mar 95 12:02 EST Received: from ietf.cnri.reston.va.us by BBN.COM id aa29420; 2 Mar 95 11:46 EST Received: from [127.0.0.1] by IETF.CNRI.Reston.VA.US id aa07079; 2 Mar 95 11:20 EST Mime-Version: 1.0 Content-Type: Multipart/Mixed; Boundary="NextPart" To: IETF-Announce: ; cc: nimrod-wg@BBN.COM From: Internet-Drafts@cnri.reston.va.us Reply-to: Internet-Drafts@cnri.reston.va.us Subject: I-D ACTION:draft-ietf-nimrod-multicast-01.txt, .ps Date: Thu, 02 Mar 95 11:20:11 -0500 Sender: cclark@cnri.reston.va.us Message-ID: <9503021120.aa07079@IETF.CNRI.Reston.VA.US> --NextPart A Revised Internet-Draft is available from the on-line Internet-Drafts directories. This draft is a work item of the New Internet Routing and Addressing Architecture Working Group of the IETF. Title : Multicast Support for Nimrod : Requirements and Solution Approaches Author(s) : R. Ramanathan Filename : draft-ietf-nimrod-multicast-01.txt, .ps Pages : 20 Date : 02/27/1995 We discuss the issue of multicasting in Nimrod. We identify the requirements that Nimrod has of any solution for multicast support. We compare existing approaches for multicasting within an internetwork and discuss their advantages and disadvantages. Finally, as an example, we outline the mechanisms to support multicast in Nimrod using the scheme currently being developed within the IETF - namely, the Protocol Indpendent Multicast (PIM) protocol. Internet-Drafts are available by anonymous FTP. Login with the username "anonymous" and a password of your e-mail address. After logging in, type "cd internet-drafts" and then "get draft-ietf-nimrod-multicast-01.txt". Or "get draft-ietf-nimrod-multicast-01.ps". A URL for the Internet-Draft is: ftp://ds.internic.net/internet-drafts/draft-ietf-nimrod-multicast-01.txt Internet-Drafts directories are located at: o Africa Address: ftp.is.co.za (196.4.160.2) o Europe Address: nic.nordu.net (192.36.148.17) o Pacific Rim Address: munnari.oz.au (128.250.1.21) o US East Coast Address: ds.internic.net (198.49.45.10) o US West Coast Address: ftp.isi.edu (128.9.0.32) Internet-Drafts are also available by mail. Send a message to: mailserv@ds.internic.net. In the body type: "FILE /internet-drafts/draft-ietf-nimrod-multicast-01.txt". Or "FILE /internet-drafts/draft-ietf-nimrod-multicast-01.ps". NOTE: The mail server at ds.internic.net can return the document in MIME-encoded form by using the "mpack" utility. To use this feature, insert the command "ENCODING mime" before the "FILE" command. To decode the response(s), you will need "munpack" or a MIME-compliant mail reader. Different MIME-compliant mail readers exhibit different behavior, especially when dealing with "multipart" MIME messages (i.e., documents which have been split up into multiple messages), so check your local documentation on how to manipulate these messages. For questions, please mail to Internet-Drafts@cnri.reston.va.us. Below is the data which will enable a MIME compliant mail reader implementation to automatically retrieve the ASCII version of the Internet-Draft. --NextPart Content-Type: Multipart/Alternative; Boundary="OtherAccess" --OtherAccess Content-Type: Message/External-body; access-type="mail-server"; server="mailserv@ds.internic.net" Content-Type: text/plain Content-ID: <19950227173509.I-D@CNRI.Reston.VA.US> ENCODING mime FILE /internet-drafts/draft-ietf-nimrod-multicast-01.txt --OtherAccess Content-Type: Message/External-body; name="draft-ietf-nimrod-multicast-01.txt"; site="ds.internic.net"; access-type="anon-ftp"; directory="internet-drafts" Content-Type: text/plain Content-ID: <19950227173509.I-D@CNRI.Reston.VA.US> --OtherAccess-- --NextPart--   Received: from PIZZA.BBN.COM by BBN.COM id aa05321; 2 Mar 95 12:49 EST Received: from pizza by PIZZA.BBN.COM id aa06165; 2 Mar 95 12:22 EST Received: from BBN.COM by PIZZA.BBN.COM id aa06161; 2 Mar 95 12:21 EST Received: from ietf.cnri.reston.va.us by BBN.COM id aa02573; 2 Mar 95 12:20 EST Received: from [127.0.0.1] by IETF.CNRI.Reston.VA.US id aa07212; 2 Mar 95 11:30 EST Mime-Version: 1.0 Content-Type: Multipart/Mixed; Boundary="NextPart" To: IETF-Announce: ; cc: nimrod-wg@BBN.COM From: Internet-Drafts@cnri.reston.va.us Reply-to: Internet-Drafts@cnri.reston.va.us Subject: I-D ACTION:draft-ietf-nimrod-mobility-01.txt, .ps Date: Thu, 02 Mar 95 11:30:12 -0500 Sender: cclark@cnri.reston.va.us Message-ID: <9503021130.aa07212@IETF.CNRI.Reston.VA.US> --NextPart A Revised Internet-Draft is available from the on-line Internet-Drafts directories. This draft is a work item of the New Internet Routing and Addressing Architecture Working Group of the IETF. Title : Mobility Support for Nimrod : Requirements and Solution Approaches Author(s) : R. Ramanathan Filename : draft-ietf-nimrod-mobility-01.txt, .ps Pages : 16 Date : 02/27/1995 We discuss the issue of mobility in Nimrod. We identify the requirements that Nimrod has of any solution for mobility support. We also classify and compare existing approaches for supporting mobility within an internetwork and discuss their advantages and disadvantages. Finally, as an example, we outline the mechanisms to support mobility in Nimrod using the scheme currently being developed within the IETF - namely, the Mobile-IP protocol. Internet-Drafts are available by anonymous FTP. Login with the username "anonymous" and a password of your e-mail address. After logging in, type "cd internet-drafts" and then "get draft-ietf-nimrod-mobility-01.txt". Or "get draft-ietf-nimrod-mobility-01.ps". A URL for the Internet-Draft is: ftp://ds.internic.net/internet-drafts/draft-ietf-nimrod-mobility-01.txt Internet-Drafts directories are located at: o Africa Address: ftp.is.co.za (196.4.160.2) o Europe Address: nic.nordu.net (192.36.148.17) o Pacific Rim Address: munnari.oz.au (128.250.1.21) o US East Coast Address: ds.internic.net (198.49.45.10) o US West Coast Address: ftp.isi.edu (128.9.0.32) Internet-Drafts are also available by mail. Send a message to: mailserv@ds.internic.net. In the body type: "FILE /internet-drafts/draft-ietf-nimrod-mobility-01.txt". Or "FILE /internet-drafts/draft-ietf-nimrod-mobility-01.ps". NOTE: The mail server at ds.internic.net can return the document in MIME-encoded form by using the "mpack" utility. To use this feature, insert the command "ENCODING mime" before the "FILE" command. To decode the response(s), you will need "munpack" or a MIME-compliant mail reader. Different MIME-compliant mail readers exhibit different behavior, especially when dealing with "multipart" MIME messages (i.e., documents which have been split up into multiple messages), so check your local documentation on how to manipulate these messages. For questions, please mail to Internet-Drafts@cnri.reston.va.us. Below is the data which will enable a MIME compliant mail reader implementation to automatically retrieve the ASCII version of the Internet-Draft. --NextPart Content-Type: Multipart/Alternative; Boundary="OtherAccess" --OtherAccess Content-Type: Message/External-body; access-type="mail-server"; server="mailserv@ds.internic.net" Content-Type: text/plain Content-ID: <19950227173159.I-D@CNRI.Reston.VA.US> ENCODING mime FILE /internet-drafts/draft-ietf-nimrod-mobility-01.txt --OtherAccess Content-Type: Message/External-body; name="draft-ietf-nimrod-mobility-01.txt"; site="ds.internic.net"; access-type="anon-ftp"; directory="internet-drafts" Content-Type: text/plain Content-ID: <19950227173159.I-D@CNRI.Reston.VA.US> --OtherAccess-- --NextPart--   Received: from PIZZA.BBN.COM by BBN.COM id aa05294; 3 Mar 95 20:41 EST Received: from pizza by PIZZA.BBN.COM id aa16131; 3 Mar 95 20:27 EST Received: from CLynn.BBN.COM by PIZZA.BBN.COM id aa16126; 3 Mar 95 20:24 EST Date: Fri, 3 Mar 95 20:25:23 EST From: Charles Lynn To: Nimrod-WG@BBN.COM Subject: Comments on Deployment Document Folks, Does anyone have any comments on the Nimrod Deployment Document? It is available via anonymous ftp from the Nimrod Archive on BBN.Com in the pub/nimrod-wg/NimrodDeploy.txt.950113 file. Thanks, Charlie   Received: from PIZZA.BBN.COM by BBN.COM id aa28595; 8 Mar 95 17:25 EST Received: from pizza by PIZZA.BBN.COM id aa15479; 8 Mar 95 17:08 EST Received: from BBN.COM by PIZZA.BBN.COM id aa15475; 8 Mar 95 17:04 EST Received: from GAAK.BBN.COM by BBN.COM id aa26437; 8 Mar 95 16:55 EST Date: Wed, 8 Mar 1995 16:55:39 EST Message-ID: To: Nimrod-WG@BBN.COM In-reply-to: message from Charles Lynn on Fri, 3 Mar 95 20:25:23 EST Subject: deployment to a core network? (was: Comments on Deployment Document) From: "Michael A. Patton" Reply-To: "Michael A. Patton, NIMROD mail" Date: Fri, 3 Mar 95 20:25:23 EST From: Charles Lynn Does anyone have any comments on the Nimrod Deployment Document? One area that I didn't see addressed in your document was how to transition a core network to using NIMROD, independent of its connections to other major networks and/or customer nets. I think this area may be where our best leverage for getting NIMROD into the field may lie. The major networks of the Internet today are suffering from problems with routing table overflow (just come to any CIDRd meeting). If we can offer them a solution they can deploy incrementally in their backbone net and without requiring customer changes, they would jump at the chance. I think if we can get NIMROD to fly on two or more core networks as an independent setup and then merge their NIMROD deployments into a larger NIMROD setup, we could be well on the way to a network primarily using NIMROD for routing. I think exploring how this might be done would be a really useful a productive area for discussion on the list. We might be able to get NIMROD to the point that BGP4 has now reached, if you're presently not speaking BGP4 to all the other BGP4-core nets (to which you connect), you aren't a BGP4-core net yourself, and are relegated to second tier status default routing to one of the BGP4-core. There are many problems that need to be addressed in such a deployment, and they differ in significant ways from the other scenarios. Being a core network, there's no chance of intercepting significantly all DNS requests. Instead, a different scheme has to be devised for splicing this NIMROD core and the traditional edges together... I expect there are probably many ways to address this, here's one that just occurred to me: Around the edges, you run hybrid NIMROD/GateD boxes to use GateD to exchange routing in a more traditional way with the client net (remembering that some of these "client" nets are other major network providers) and to then import everything reachable by that connection into the NIMROD cloud as a (nearly trivial) map. I think these boxes need to talk to one another (over the NIMROD cloud), but I'm not sure if it's with BGP4 or normal NIMROD communications (I hope the later). The first possible reason is to simplify export at the far side. By simply carrying routes through, this will cause the NIMROD core cloud to appear as a single NBMA network hop to traditional routing tools (but traditional routing tools will traverse it). Although if you actually import to NIMROD, transport the routing across the cloud as NIMROD, and then translate again for export, you may be able to get some policies that current routing does not allow. While this later gives more of the NIMROD flexibility, it lacks the transparency (or at least translucency) to existing tools. Another reason the boxes need to talk is to coordinate when something shows up at more than one (you need a slightly less trivial map for this case :-) interconnect point. It may be that this is handled as part of the regular NIMROD interaction of the NIMROD side of these boxes, that may take some additional exploration. I haven't thought about this in massive detail, yet, but I believe it would be a really useful avenue to explore. It is an area that already is in need of one part of the NIMROD feature set, and which can give enormous leverage to getting it even wider deployment. -MAP   Received: from PIZZA.BBN.COM by BBN.COM id aa13796; 13 Mar 95 18:25 EST Received: from pizza by PIZZA.BBN.COM id aa11267; 13 Mar 95 18:09 EST Received: from BBN.COM by PIZZA.BBN.COM id aa11263; 13 Mar 95 18:05 EST Received: from GAAK.BBN.COM by BBN.COM id aa12447; 13 Mar 95 18:00 EST Date: Mon, 13 Mar 1995 18:00:36 EST Message-ID: To: Isidro@BBN.COM Cc: NIMROD-WG@BBN.COM Subject: Bugs in Architecture draft From: "Michael A. Patton" Reply-To: "Michael A. Patton, NIMROD mail" I've noticed a couple of bugs so far in my reading of the latest NIMROD Architecture draft...dated March 1995. In comparing Figure 2 and Figure 3, and by reference to the text, I don't think the mapping between those representations works. The Physical network has router RD at locator b2:r1 and network EC at locator b2:e1 that are not in any part of the logical map on the next page. I expect that there was some purpose to having different levels of locators here, but there's some loss in the logical mapping between the two figures. Also, Section 4.3 still seems to be confusing in the fact that there are THREE things we are mapping in NIMROD, physical networks, and advertised connectivity. Also, it covers new territory not previously covered and not solely germaine to the heading topic. Perhaps an additional section describing many maps for one physical realization is needed here before launching into the multiple locators examples. The last bug I noticed is in the Authors' Addresses section (which, as an aside got badly split by a figure), you have Noel's address wrong, he's JNC@Ginger.LCS.MIT.edu ... -MAP P.S. Also as a general readability comment, I find the diagrams are way too far away from the text that describes them...   Received: from PIZZA.BBN.COM by BBN.COM id aa23982; 2 Apr 95 16:02 EDT Received: from pizza by PIZZA.BBN.COM id aa26158; 2 Apr 95 15:50 EDT Received: from KARIBA.BBN.COM by PIZZA.BBN.COM id aa26152; 2 Apr 95 15:47 EDT To: nimrod-wg@BBN.COM, msteenst@BBN.COM, clynn@BBN.COM Subject: Nimrod WG Agenda Date: Sun, 02 Apr 95 15:50:51 -0400 From: Isidro Castineyra Group Name: Nimrod - The New Internet Routing and Addressing Architecture IETF Area: Routing Date/Time: Tuesday, April 4, 1995 0930-1200 Wednesday, April 5, 1995 0930-1200 Proposed Agenda -- First Session 1. Agenda bashing/Announcements 5min 2. Overview of the Deployment Document 45min (Charlie Lynn) 3. Configuration vs. Discovery 30min (Martha Steenstrup) 4. Discussion Proposed Agenda -- Second Session 5. What is in the Nimrod Model 45min (Martha Steenstrup and Isidro Castineyra) 6. Software Architecture 30min (Charlie Lynn) 7. Discussion 8. Open Issues and Work Plan 15min   Received: from PIZZA.BBN.COM by BBN.COM id aa11233; 21 Apr 95 9:46 EDT Received: from pizza by PIZZA.BBN.COM id aa10457; 21 Apr 95 9:10 EDT Received: from KARIBA.BBN.COM by PIZZA.BBN.COM id aa10451; 21 Apr 95 9:06 EDT To: minutes@cnri.reston.va.us cc: msteenst@BBN.COM, nimrod-wg@BBN.COM Subject: Nimrod WG minutes ---- 32nd IETF Date: Fri, 21 Apr 95 09:09:40 -0400 From: Isidro Castineyra Nimrod WG Minutes, IETF 32, Danvers Isidro Castineyra, BBN April 6, 1995 1 Preface The Nimrod WG met on Tuesday April 4, 1995 from 0930 to 1200 and on Wednesday April 5 from 0930 to 1200. The agenda for the meeting was: o Tuesday, April 4, 1995---0930-1200 1. Agenda bashing/Announcements---5min 2. Overview of the Deployment Document---45min (Charlie Lynn) 3. Configuration vs. Discovery---30min (Martha Steenstrup) 4. Discussion o Wednesday, April 5, 1995---0930-1200 1. What is in the Nimrod Model---45min (Martha Steenstrup and Isidro Castineyra) 2. Software Architecture---30min (Charlie Lynn) 3. Discussion 4. Open Issues and Work Plan---15min 1 2 Deployment Document Charlie Lynn gave an overview of the Deployment Document. He discussed strategies for the gradual integration of Nimrod in the Internet. 3 Configuration vs. Discovery Martha Steenstrup presented a list of information elements that could be obtained by either configuration or discovery. For each element, Martha discussed the trade-offs and the current thoughts on what to do with that element. Highlights of her presentation follow. o The goal is to make both a ``plug-and-play'' system and to make everythin configurable o Configured items: -- At Node Representatives: adjancecy formation constraints, association constraints, set of locator elements for component nodes. -- At Endpoint Representatives: EIDs and names of endpoints, association constraints, multicast group membership of endpoints. -- At Forwarding Agents: traffic restrictions. -- At Agents: type of agent, EID of agnet, nodes on showe behalf the agent acts (configured). Martha will be posting the slides she used to the working group mailing list. 4 Nimrod Model/Bootstrap I Isidro Castineyra described a bootstrap model for Nimrod. Highlights of his talk follow: o Nimrod specifies only what happens between nodes. o The internal operation of an ``atomic'' node is not Nimrod's concern. 2 o There are two kinds of locators: flat and hierarchical. o The flat locator of a node is used in Basic Routing (later) to do flat routing within the components node of nodes. This mode of routing is used to bootstrap hierarchical routing. o The Nimrod part of a hierarchical locator is a sequence of up to 256 locator elements, where a locator element is a 16-bit strings. o Hierarchical locator is ``inside'' a node if it's Nimrod part is both prefixed by the node's locator and longer than the node's locator. o For a given node and for a given hierarchical locator inside the node, the first element following the original node's locator identifies a component node. We refer to this 16 bit string as the node's ``local element.'' Therefore, nodes are limited to having no more than 216 component nodes. o For a given node, the assignment of the values of local element to component nodes is independent both of assignment of local elements inside the node's subnode and in nodes that subsum the given node. o Basic routing is based only on connectivity---i.e., it does not take into account considerations of quality of service or service restrictions. o Basic routing is used for agent discovery and to enable communication between agents that reside in different nodes. The advanced routing capabilities of Nimrod are built over basic routing. o Basic routing is very much like a one-level OSPF. Basic routing is built over a flooding protocol which works between the set of nodes. When a message is flooded, every node in the set receives a copy of the message which is delivered to the node's representative(s). o Information flooded includes: identity of neighbouring component nodes, what agents the node includes. Slides from this presentation will be posted to the mailing list. 5 Nimrod Model/Bootstrap II Martha Steenstrup described an alternative bootstrap model. Highlights of her presentation follow: 3 o Besides interaction between nodes, Nimrod specifies interaction between agents within a node. These agents mights reside in separate ``boxes'' and be connected via IP. o Agents need not reside in the node on whose behalf they act. o Agents advertise their presence and characteristics using a reliable hop-by-hop flooding protocol. This flooding is used to construct a next-hop agent forwarding table using an algorithm similar (but not identical) to standar distance vector algorithms. The slides for this presentation will be sent to the mailing list. 6 Software Architecture Charlie Lynn presented the current software architecture for the BBN implementation of Nimrod. 7 Path Management Issues Martha Steenstrup listed alternatives for path setup. o Should path labels be globally unique or path unique. o Path constructions: should we use hierarchical routes or hierarchical paths. o Path repair: should it be done at any node; at initiator or target; between succesive hops? 4   Received: from PIZZA.BBN.COM by BBN.COM id ab07411; 25 Apr 95 17:53 EDT Received: from pizza by PIZZA.BBN.COM id aa02372; 25 Apr 95 17:11 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa02368; 25 Apr 95 17:08 EDT Received: from GAAK.BBN.COM by BBN.COM id aa04109; 25 Apr 95 17:05 EDT Date: Tue, 25 Apr 1995 17:05:22 EDT Message-ID: To: Nimrod-WG@BBN.COM, Namedroppers@internic.net Subject: First draft DNS RRs for Nimrod From: "Michael A. Patton" Attached is the first draft of the document on the two new RRs that Nimrod will require in the DNS. I would appreciate if people on these two lists could give it a review and send me their comments (it's only about 5 pages including all the boilerplate and diagrams :-). I will be getting RR numbers assigned and submitting it as a Nimrod WG Internet-draft shortly, but thought I'd get some quick feedback from these two lists first. The only open issue *I* have is whether there's a better mnemonic for the "Locator" RR (LOC being taken, I used NL for "Nimrod Locator" :-). -MAP ---------------------------------------------------------------- INTERNET DRAFT M. A. Patton Expiration Date: October 1995 BBN April 1995 DNS Resource Records for Nimrod Routing Architecture 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). This Internet Draft expires October 1995. Abstract This document describes two additional RR types for the Domain Name System[7,8] required to implement the Nimrod Routing Architecture[1]. These RRs record the Nimrod Locator and an Endpoint Identifier (EID) associated with a given Domain Name. Introduction Nimrod is a scalable internetwork routing architecture. The Nimrod architecture is designed to accommodate an internetwork of arbitrary size and with heterogeneous service requirements and restrictions and to admit incremental deployment throughout an internetwork. The key to Nimrod's scalability is its ability to represent and manipulate routing-related information at multiple levels of abstraction. To do this efficiently, Nimrod separates the identification of communicating entities (Endpoints) from any topological information. Endpoint Identifiers (EIDs) are used to specify and uniquely identify entities connected to the network. Information about the topological location of an endpoint in the network is given by a Locator, which may change as the network topology changes. During the initial deployment of the Nimrod system the mapping will be stored in the existing DNS system as two additional RRs on the Domain Name of the Endpoint. This document describes the two new RR types required to record this information. Nimrod uses a heirarchy of abstract maps of (parts of) the network. Locators are topologically significant "names" for a node, indicating where in the map heirarchy it can be found. Because they reflect location in the network, Locators will change when a nodes location changes. EIDs are short identifiers for the endpoint of a communication (e.g. a host system) and have no structure or significance other than global uniqueness. An endpoint can retain the same EID forever, no matter where in the network it is located. Updates of the EID and (particularly) the Locator information will almost always be done through a Dynamic Update[2] protocol, and not by manual editing of a master file, which means that human readability is not a major concern. Due to the dynamicity of the updates to the Locator information, specifically the need to update large quantities at once, efficiency may require additional update support or a Nimrod Association Agent to back-end the DNS. 1. definition of the RR types Both of the RR types described in this document encode numbers whose structure (if any) is not meaningfully interpreted by the DNS system. Thus each is encoded as an uninterpreted string of octets, with the attribution of any meaning left up to the system which retrieves these values. 1.1. The EID (Endpoint Identifier) RR The EID (Endpoint IDentifier) RR is defined with mnemonic "EID" and TYPE code [[[TBD]]] (decimal) and is used to map from domain names to EIDs. The EIDs declared in this RR may be used by any system that uses Endpoint Identifiers, but the initial use is intended for the Nimrod Routing system. EIDs are short, usually fixed length strings of octets whose content is only meaningful to the Nimrod routing system. Since the top level RR format and semantics as defined in Section 3.2.1 of RFC 1035 include a length indicator, the Domain Name System is not required to understand any internal structure. The format of an Endpoint IDentifier (EID) RR is: 1 1 1 1 1 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | | / / / NAME / | | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | TYPE = EID | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | CLASS = IN | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | TTL | | | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | RDLENGTH | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ / RDATA / / / +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ where: * NAME: an owner name, i.e., the name of the node to which this resource record pertains. * TYPE: two octets containing the EID RR TYPE code of [[[TBD]]] (decimal). * CLASS: two octets containing the RR IN CLASS code of 1. * TTL: a 32 bit signed integer that specifies the time interval in seconds that the resource record may be cached before the source of the information should again be consulted. * RDLENGTH: an unsigned 16 bit integer that specifies the length in octets of the RDATA field. * RDATA: a string of octets containing the Endpoint Identifier. The value is the binary encoding of the Identifier, meaningful only to the system utilizing it. 1.2. The NL (Nimrod Locator) RR [[[ I don't like any of the options I came up with for naming this... ]]] The NL (Nimrod Locator) RR is defined with mnemonic "NL" and TYPE code [[[TBD]]] (decimal) and is used to map from domain names to Nimrod Locators. Nimrod Locators are possibly variable length strings of octets whose content is only meaningful to the Nimrod routing system. Since the top level RR format and semantics as defined in Section 3.2.1 of RFC 1035 include a length indicator, the Domain Name System is not required to understand any internal structure. The format of a Nimrod Locator (NL) RR is: 1 1 1 1 1 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | | / / / NAME / | | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | TYPE = NL | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | CLASS = IN | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | TTL | | | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | RDLENGTH | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ / RDATA / / / +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ where: * NAME: an owner name, i.e., the name of the node to which this resource record pertains. * TYPE: two octets containing the NL RR TYPE code of [[[TBD]]] (decimal). * CLASS: two octets containing the RR IN CLASS code of 1. * TTL: a 32 bit signed integer that specifies the time interval in seconds that the resource record may be cached before the source of the information should again be consulted. * RDLENGTH: an unsigned 16 bit integer that specifies the length in octets of the RDATA field. * RDATA: a variable length string of octets containing the Nimrod Locator. The value is the binary encoding of the Locator specified in the Nimrod protocol[[[ref to be supplied]]]. 2. Additional Section Processing DNS servers cognizant of EID and NL type RRs should return these records in the Additional Section of any response including an A or AAAA type RR. These could be in response to either A or AAAA type queries, or some other query (e.g. NS) that specifies A and/or AAAA records in the Additional Section. This is not required for operation of the Nimrod system, as additional queries can always be made, but, in general, any time an A or AAAA RR will be used by a Nimrod agent, it will also need the EID and Locator info. 3. Master File Format The format of NL and EID RRs follows all the rules of RFC 1035, Section 5, "Master Files." The RDATA portion of both the NL and EID records contains uninterpreted binary data. The representation in the text master file is an even number of hex characters (0 to 9, a to f), case is not significant. Example master file with NL and EID RRs (based on the example in RFC1035): @ IN SOA VENERA Action\.domains ( 20 ; SERIAL 7200 ; REFRESH 600 ; RETRY 3600000; EXPIRE 60) ; MINIMUM NS A.ISI.EDU. NS VENERA NS VAXA MX 10 VENERA MX 20 VAXA A A 26.3.0.103 EID E32C6F78163A9348 NL 32251A030067 VENERA A 10.1.0.52 A 128.9.0.32 EID 813F4B7CDAB34217 NL 3227450A010034 NL 75234159EAC457800920 VAXA A 10.2.0.27 A 128.9.0.33 EID 3141592653589793 NL 75234159EAC457800921 4. Acknowledgements I'd like to thank the members of the DNS and Nimrod mailing lists for their comments and suggestions, and to the Nimrod Architects for the documents on which this is based. I'd also like to thank Arnt Gulbrandsen for his collected list of DNS RFCs and permission to use it as the basis for the References section and Bill Manning, the author of RFC1348, for unwittingly supplying the boilerplate and diagrams I used as a basis for this document. [[[ more? ]]]. 5. Security Considerations Security issues are not discussed in this memo. 6. References [1] draft-ietf-nimrod-routing-arch-00.txt: I. Castineyra, J. N. Chiappa, M. Steenstrup, "The Nimrod Routing Architecture", March 1995 [2] draft-ietf-dnsind-dynDNS-01.txt: S. Thomson, Y. Rekhter, J. Bound, "Dynamic Updates in the Domain Name System", March 1995 [3] RFC 1536: A. Kumar, J. Postel, C. Neuman, P. Danzig, S. Miller, "Common DNS Implementation Errors and Suggested Fixes.", 10/06/1993. [4] RFC 1348: B. Manning, "DNS NSAP RRs", 07/01/1992. [5] RFC 1183: R. Ullman, P. Mockapetris, L. Mamakos, C. Everhart, "New DNS RR Definitions", 10/08/1990. [6] RFC 1101: P. Mockapetris, "DNS encoding of network names and other types", 04/01/1989. [7] RFC 1035: P. Mockapetris, "Domain names - implementation and specification", 11/01/1987. [8] RFC 1034: P. Mockapetris, "Domain names - concepts and facilities", 11/01/1987. [9] RFC 1033: M. Lottor, "Domain administrators operations guide", 11/01/1987. [10] RFC 1032: M. Stahl, "Domain administrators guide", 11/01/1987. [11] RFC 974: C. Partridge, "Mail routing and the domain system", 01/01/1986. 7. Authors' Address: Michael A. Patton Bolt Beranek and Newman 10 Moulton Street Cambridge, MA, 02138 Phone: (617) 873 2737 FAX: (617) 873 3457 Email: map@bbn.com This Internet Draft expires October 1995   Received: from PIZZA.BBN.COM by BBN.COM id aa16953; 26 Apr 95 0:43 EDT Received: from pizza by PIZZA.BBN.COM id aa04272; 26 Apr 95 0:20 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa04263; 26 Apr 95 0:19 EDT Received: from munnari.OZ.AU by BBN.COM id aa10855; 26 Apr 95 0:12 EDT Received: from mundamutti.cs.mu.OZ.AU by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA04941; Wed, 26 Apr 1995 14:11:55 +1000 (from kre@munnari.OZ.AU) To: "Michael A. Patton" Cc: Nimrod-WG@BBN.COM, Namedroppers@internic.net Subject: Re: First draft DNS RRs for Nimrod In-Reply-To: Your message of "Tue, 25 Apr 1995 17:05:22 EDT." Date: Wed, 26 Apr 1995 14:11:25 +1000 Message-Id: <3813.798869485@munnari.OZ.AU> From: Robert Elz Date: Tue, 25 Apr 1995 17:05:22 EDT From: "Michael A. Patton" Message-ID: 1. definition of the RR types Both of the RR types described in this document encode numbers whose structure (if any) is not meaningfully interpreted by the DNS system. Thus each is encoded as an uninterpreted string of octets, with the attribution of any meaning left up to the system which retrieves these values. I don't much like this language. I think I understand what you're trying to say, which is that the DNS doesn't need to know anything about the internal format of the data part of these RR's, which is probably true, and consequently you don't want to attempt to define it here. But leaving the meaning up to the system that retrieves the values is not really very useful. That means that if I retrieve the value I can interpret however I like, and what's more, I'm right, however I interpret the value (I could treat the first octet as a length field, then delete the data if the remainder isn't consistent, and I'm correct in doing that). I think it would be more constructive to indicate that the interpretation of the data will be defined in another document, yet to be produced, but which is immaterial to the DNS. I suspect though that the DNS needs a little more help in processing these records than is given here. For example, is it legal for a node in the DNS tree to have more than one EID or NL RR - usually that's legal, but isn't for all records (two SOA's is meaningless for example). Then, assuming that multiple records are legal, are two RR's with exactly the same data two distinct RR's, or are they the same RR encountered twice? Eg: it makes no sense to have two identical A records for a node, but it does to have two identical TXT records. kre   Received: from PIZZA.BBN.COM by BBN.COM id aa23764; 26 Apr 95 4:15 EDT Received: from pizza by PIZZA.BBN.COM id aa05111; 26 Apr 95 3:46 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa05107; 26 Apr 95 3:43 EDT Received: from necom830.cc.titech.ac.jp by BBN.COM id aa16941; 26 Apr 95 3:41 EDT Received: by necom830.cc.titech.ac.jp (8.6.11/necom-mx-rg); Wed, 26 Apr 1995 16:39:11 +0900 From: Masataka Ohta Return-Path: Message-Id: <199504260739.QAA24110@necom830.cc.titech.ac.jp> Subject: Re: First draft DNS RRs for Nimrod To: "Michael A. Patton" Date: Wed, 26 Apr 95 16:39:10 JST Cc: Nimrod-WG@BBN.COM, Namedroppers@internic.net In-Reply-To: ; from "Michael A. Patton" at Apr 25, 95 5:05 pm X-Mailer: ELM [version 2.3 PL11] Seemingly because of the fundamental impossiblity of automatic renumbering involving namer servers themselves, or, whatever the reason is, draft-ietf-nimrod-routing-arch-00.txt says: :However, because renumbering will, most likely, be infrequent and carefully :planned, we expect that the load on this updating mechanism should be :manageable. So, you don't have to say: > Due to the dynamicity of the > updates to the Locator information, specifically the need to update > large quantities at once, efficiency may require additional update > support or a Nimrod Association Agent to back-end the DNS. Of course, requesting "carefully planned" update involves human effort which is often a lot more than that of manual DNS update. So, it's better, I think, to make locator node indirectly referenced and shared by multiple end points of the same site like PREFIX RR proposed in IPng ML, which I explained in DNS WG meeting at Danvers. Masataka Ohta   Received: from PIZZA.BBN.COM by BBN.COM id aa23417; 27 Apr 95 21:22 EDT Received: from pizza by PIZZA.BBN.COM id aa18218; 27 Apr 95 21:00 EDT Received: from KARIBA.BBN.COM by PIZZA.BBN.COM id aa18214; 27 Apr 95 20:57 EDT To: nimrod-wg@BBN.COM Subject: slides Date: Thu, 27 Apr 95 21:00:50 -0400 From: Martha Steenstrup Here is a configuration slide set from IETF meeting: ---------------- Nimrod (Auto)Configuration Goals: - Plug and play - Everything is configurable Initialization: - Clustering physical entities into nodes - Abstraction of topological and service information for nodes - Formation of adjacencies between nodes - Formation of associations between endpoints and nodes - Locator acquisition - Database maintenance - Agent discovery ---------------- Nimrod Databases - Node specific - Endpoint specific - Agent specific - Routes - Associations - Forwarding information ---------------- Information Maintained by a Node Representative - Adjacency constraints (must be configured) - Association constraints (must be configured) - Set of locator elements for component nodes (must be configured) - Maps for the node For each connectivity specification: - Label - Service offerings - Service restrictions - Entry and exit points - Distribution restrictions For each adjacency: - Locator of adjacent node - Component lower-level adjancencies - Participating forwarding agents - Locator of node ---------------- Information Maintained by an Endpoint Representative - EIDs and names of endpoint (must be configured) - Association constraints (must be configured) - Multicast group membership of endpoint (must be configured) - Locator(s) of endpoint - Service requirements for endpoint traffic - From source and destination perspective - Service requests - Service restrictions ---------------- Information Maintained by a Route Agent - Map cache - Route cache For each route: - Locators of constituent nodes - Labels of connectivity specifications for constituent nodes - Service offerings and restrictions ---------------- Information Maintained by an Association Agent - Endpoint/locator cache For each endpoint: - EID and name(s) - Locator(s) - EID and locator of endpoint representative (if different from endpoint) ---------------- Information Maintained by a Forwarding Agent - Traffic handling restrictions (must be configured) - Route cache - Path cache - Forwarding information For each incoming path: - Incoming path label - Previous hop EID and location information - Outgoing path label - Next hop EID and location information ---------------- Information Maintained by each Agent - Type of agent (must be configured) - EID of agent (must be configured) - Nodes on whose behalf the agent acts, called "scopes" (must be configured) - Locator of agent - Other location information for agent (e.g., IP address) - Neighbor agents - EIDs - Locators - Other location information - Agents of the same type and scope - EIDs - Locators - Other location information - Forwarding agents maintain information about all of the following agents sharing their scope: - Node representatives - Boundary forwarding agents - Route agents - Association agents ----------------   Received: from PIZZA.BBN.COM by BBN.COM id aa24315; 27 Apr 95 21:41 EDT Received: from pizza by PIZZA.BBN.COM id aa18344; 27 Apr 95 21:20 EDT Received: from KARIBA.BBN.COM by PIZZA.BBN.COM id aa18340; 27 Apr 95 21:18 EDT To: nimrod-wg@BBN.COM Subject: more slides Date: Thu, 27 Apr 95 21:22:19 -0400 From: Martha Steenstrup Here are some slides about bootstrapping: ---------------- What is a Node? - Physical entities are path-connected - Locator is relative to the clustering hierarchy - May appear in a Nimrod route - Has an abstract map - Sense of node interior and exterior There must be: - At least one node representative - Boundary forwarding agents at node entry/exit points ---------------- Examples of Nodes: - Individual routers - IP "clouds" - Collections of such nodes ---------------- Agents - Need not reside in the node on whose behalf they act - but strongly recommended - Must handle node: - Formation - Reconfiguration - Movement - In a node, all agents need not be activated simultaneously - Discovery of immediate neighbor agents, inside or outside the node - Discovery of all agents within a node - Acquisition of node locators - Formation of adjacencies between nodes - Association of nodes and endpoints ---------------- Discovery - Agent advertisements contain: - Type of agent - Locator of agent - EID of agent - Scope(s) of agent - Reliable hop-by-hop flooding of advertisements, periodically - Distributed algorithm to construct next-hop agent forwarding table - Forwarding agents know how to reach all other types of agents in the node - Interior forwarding agents do not advertise themselves - Each node requires a globally unique label independent of locator, which it may not yet have acquired - Agents require a "key", not exact location information, to forward a query for database information to an appropriate responder ---------------- Locator Acquisition - Based on: - Configured "prefix" of locator - Longest element match of locators of all exterior neighboring forwarding agents - Controlled by node representatives according to adjacency constraints - "Route collection" in forward query so that response can return, required when traversing nodes in the process of forming - Multiple locators acquired by a partitioned node are resolved to a single locator when the partition disappears - Locator information propagates to all agents in a node and hence trickles down to component nodes ---------------- Endpoint Associations - Based one: - Configured prefix of locator - Differing locators of each neighboring forwarding agent of the endpoint representative - Controlled by node representative and endpoint representative according to association constraints - Locator information percolates up to assocation agents ---------------- Adjacency Formation - Based on: - Discovered external neighbors - Existing lower-level adjacencies - Controlled by the node representatives according to the adjacency constraints - Adjacency information propagates to all node representative (for use in map construction) and to all boundary forwarding agents (for use in packet forwarding) ----------------   Received: from PIZZA.BBN.COM by BBN.COM id aa11821; 4 May 95 11:30 EDT Received: from pizza by PIZZA.BBN.COM id aa26927; 4 May 95 10:52 EDT Received: from KARIBA.BBN.COM by PIZZA.BBN.COM id aa26923; 4 May 95 10:47 EDT To: nimrod-wg@BBN.COM Subject: nimrod information Date: Thu, 04 May 95 10:51:16 -0400 From: Martha Steenstrup Hello, As several of you know, the public nimrod directory at BBN has been unreachable for a week or so. I apologize for the inconvenience this has caused some of you. BBN is in the process of setting up new FTP and WWW capabilities, and as a result there have been interruptions in access. To retrieve Nimrod documents and mail archives from BBN, please anonymous FTP to the place called ftp.nimrod.bbn.com. (This replaces the old place called bbn.com.) Nimrod information is contained in the directory pub/nimrod-wg. There is also an incoming directory within the above directory, which allows you to deposit information for dissemination. In the short term, you will not yet be able to obtain "recently" archived mail from ftp.nimrod.bbn.com. Over the next couple of weeks, if you need recently archived mail, please send your request to nimrod-request@bbn.com. I will let you know when recently archived mail will be automatically available. The new web site is called www.nimrod.bbn.com. (This might not be set up yet but will be shortly.) m   Received: from PIZZA.BBN.COM by BBN.COM id aa20364; 4 May 95 19:21 EDT Received: from pizza by PIZZA.BBN.COM id aa00278; 4 May 95 18:50 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa00274; 4 May 95 18:49 EDT Received: from GAAK.BBN.COM by BBN.COM id aa18811; 4 May 95 18:51 EDT Date: Thu, 4 May 1995 18:50:57 EDT Message-ID: To: Nimrod-WG@BBN.COM Subject: Nimrod on the Web From: "Michael A. Patton" Reply-To: "Michael A. Patton, Nimrod mail" There is a World Wide Web page for Nimrod, those of you at the Danvers meeting saw an early announcement, a few minor things have changed, so this is a replacement... The "Nimrod Front Page" is That's presently the only page on the Web server, but collects all the pointers to other Nimrod related info on the net that I know about, including on the IETF Web server and the FTP server. If you have any comments, suggestions, additional pointers, etc., feel free to let me know. The IETF Web page for the Working Group has a pointer to this page so you can always find it from there (thanks to Debra Legare for setting that part up). -MAP   Received: from PIZZA.BBN.COM by BBN.COM id aa05571; 27 Jun 95 17:04 EDT Received: from pizza by PIZZA.BBN.COM id aa14838; 27 Jun 95 16:26 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa14834; 27 Jun 95 16:21 EDT Received: from ietf.cnri.reston.va.us by BBN.COM id aa01231; 27 Jun 95 16:23 EDT Received: from [127.0.0.1] by IETF.CNRI.Reston.VA.US id aa11700; 27 Jun 95 14:51 EDT Mime-Version: 1.0 Content-Type: Multipart/Mixed; Boundary="NextPart" To: IETF-Announce: ; cc: nimrod-wg@BBN.COM, namedroppers@internic.net From: Internet-Drafts@cnri.reston.va.us Reply-to: Internet-Drafts@cnri.reston.va.us Subject: I-D ACTION:draft-ietf-nimrod-dns-00.txt Date: Tue, 27 Jun 95 14:18:05 -0400 Sender: cclark@cnri.reston.va.us Message-ID: <9506271451.aa11700@IETF.CNRI.Reston.VA.US> --NextPart A New Internet-Draft is available from the on-line Internet-Drafts directories. This draft is a work item of the New Internet Routing and Addressing Architecture Working Group of the IETF. Title : DNS Resource Records for Nimrod Routing Architecture Author(s) : M. Patton Filename : draft-ietf-nimrod-dns-00.txt Pages : 5 Date : 06/26/1995 This document describes two additional RR types for the Domain Name System[7,8] required to implement the Nimrod Routing Architecture[1]. These RRs record the Nimrod Locator and an Endpoint Identifier (EID) associated with a given Domain Name. Internet-Drafts are available by anonymous FTP. Login with the username "anonymous" and a password of your e-mail address. After logging in, type "cd internet-drafts" and then "get draft-ietf-nimrod-dns-00.txt". A URL for the Internet-Draft is: ftp://ds.internic.net/internet-drafts/draft-ietf-nimrod-dns-00.txt Internet-Drafts directories are located at: o Africa Address: ftp.is.co.za (196.4.160.2) o Europe Address: nic.nordu.net (192.36.148.17) Address: ftp.nis.garr.it (192.12.192.10) o Pacific Rim Address: munnari.oz.au (128.250.1.21) o US East Coast Address: ds.internic.net (198.49.45.10) o US West Coast Address: ftp.isi.edu (128.9.0.32) Internet-Drafts are also available by mail. Send a message to: mailserv@ds.internic.net. In the body type: "FILE /internet-drafts/draft-ietf-nimrod-dns-00.txt". NOTE: The mail server at ds.internic.net can return the document in MIME-encoded form by using the "mpack" utility. To use this feature, insert the command "ENCODING mime" before the "FILE" command. To decode the response(s), you will need "munpack" or a MIME-compliant mail reader. Different MIME-compliant mail readers exhibit different behavior, especially when dealing with "multipart" MIME messages (i.e., documents which have been split up into multiple messages), so check your local documentation on how to manipulate these messages. For questions, please mail to Internet-Drafts@cnri.reston.va.us. Below is the data which will enable a MIME compliant mail reader implementation to automatically retrieve the ASCII version of the Internet-Draft. --NextPart Content-Type: Multipart/Alternative; Boundary="OtherAccess" --OtherAccess Content-Type: Message/External-body; access-type="mail-server"; server="mailserv@ds.internic.net" Content-Type: text/plain Content-ID: <19950626103241.I-D@CNRI.Reston.VA.US> ENCODING mime FILE /internet-drafts/draft-ietf-nimrod-dns-00.txt --OtherAccess Content-Type: Message/External-body; name="draft-ietf-nimrod-dns-00.txt"; site="ds.internic.net"; access-type="anon-ftp"; directory="internet-drafts" Content-Type: text/plain Content-ID: <19950626103241.I-D@CNRI.Reston.VA.US> --OtherAccess-- --NextPart--