Received: from PIZZA.BBN.COM by BBN.COM id aa29250; 7 Jul 94 12:53 EDT Received: from pizza by PIZZA.BBN.COM id aa28396; 7 Jul 94 12:35 EDT Received: from KARIBA.BBN.COM by PIZZA.BBN.COM id aa28392; 7 Jul 94 12:32 EDT To: nimrod-wg@BBN.COM Subject: Nodes and Arcs Date: Thu, 07 Jul 94 12:27:10 -0400 From: Isidro Castineyra The questions is: "Should arcs have attributes?". Obviously both approaches, arcs-with-attributes and arcs-without-attributes are equivalent: i.e., one can translate one kind of map to the other kind without loss of information. Two cases: 1. Arcs-With-Attributes to Arcs-Without-Attributes: substitute each attribute-full arc -> with two attribute-less arcs and a node: arc->node->arc, put the properties of the orignal arc in the extra node. 2. Arcs-Without-Attributes to Arcs-With-Attributes: one does not have to use attributes even if the model allows it. The question is therefore "purely cosmetical", but wars have started over smaller matters. Think of the physical internet. It is composed of hosts, routers, point-to-point links (e.g., T1 links) and networks (ethernets, X.25 nets, etc.). These elements connect to each other at interfaces. For example, we can identify an interface between a router and a T1 link, and an interface between a host and an ethernet. Interfaces are not like hosts, routers, networks and links in that they are logical constructs; the others are physical devices. A node is defined by a set of interfaces. The set of interfaces that defines a node is such that when the connections at these interfaces are broken, the network is partitioned in two. One of these parts is the node, the other is the rest of the network. Arcs represent interfaces between nodes. The thing is that interfaces *have* properties. For example, the interface between a host and an ethernet can transmit at a maximum rate, etc. How should these properties be represented: A few approaches: 1. Bestow attributes on Arcs; represent an interface's properties as arcs attributes. 2. Arcs have no attributes; represent an interface as an arc->node->arc combination, the properties of the interface appear as attributes of the node. 3. Create an interface construct at the map level: the node connecting point of the first Nimrod architecture draft. (So far, interfaces have shown up on physical networks, not on maps). Make these connecting points be attributes of the nodes, and make the connecting points have their own attributes, these represent the properties of the physical interfaces. 4. Bury the properties of the interface in the transit connectivity specification of the node. 5. What am I missing? These approaches are not exclusive: in a Nimrod without arc attributes one could use a combination 2, 3, and 4. Approach 2 is a little bit of a kludge. One would have to open a node to first level to see these node->arc->node combination. Approach 3 re-creates the "node connection point" we had got rid off. Approach 4 might be an inefficient representation. The current draft architecture uses 1. That was my mistake as I forgot that we had agreed not to have attributes associated with arcs. Let me know what you think about our choices. Thanks, Isidro   Received: from PIZZA.BBN.COM by BBN.COM id aa05671; 7 Jul 94 14:36 EDT Received: from pizza by PIZZA.BBN.COM id aa28984; 7 Jul 94 14:19 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa28980; 7 Jul 94 14:17 EDT Received: from quern.epilogue.com by BBN.COM id aa04188; 7 Jul 94 14:14 EDT From: Dave Bridgham Sender: dab@epilogue.com To: nimrod-wg@BBN.COM In-reply-to: Isidro Castineyra's message of Thu, 07 Jul 94 12:27:10 -0400 <9407071243.aa09577@quern.epilogue.com> Subject: Nodes and Arcs Date: Thu, 7 Jul 94 14:13:18 -0400 Message-ID: <9407071413.aa10119@quern.epilogue.com> Date: Thu, 07 Jul 94 12:27:10 -0400 From: Isidro Castineyra I think you use terms in a confusing manner. In particular the term "interface" though it took me about five minutes to figure out which word was confusing me. Arcs represent interfaces between nodes. The thing is that interfaces *have* properties. Draw a map with three nodes, a host, an interface, and a network. Draw arcs connecting the three nodes in the obvious way (the host connects to the interface which connects to the network). If I call those arcs "interfaces" as you have in the excerpt above, I'm now using the term "interface" to mean two different things. I suggest therefore that we should not say arcs represent interfaces between nodes because it's too easy to confuse that use of the word interface with say an ethernet interface. One is a concept having to do with relationships between abstract objects; the nodes in the graph are just abstract objects which may or may not have physical realizations. The other is electronics in your computer. 2. Arcs have no attributes; represent an interface as an arc->node->arc combination, the properties of the interface appear as attributes of the node. I prefer this I think. 1. Bestow attributes on Arcs; represent an interface's properties as arcs attributes. I'd accept this as a second choice. Any implementation I did would probably use approach 2 as its internal representation so I'd prefer the map description language to match so I don't have to convert. Answers 1 and 2 seem to me the most clean. All the others sound like we're doing special cases because we know what the maps will look like. I'd argue against either 3 or 4. I prefer a more general map language so when we find out we really want differnet maps we're more likely to be able to just field them. Approach 2 is a little bit of a kludge. One would have to open a node to first level to see these node->arc->node combination. I guess I don't quite understand the objection. Maybe that's just because of my opinion, expressed in a previous message, that I'd build the first level map to include an entire site anyway so of course people would be looking at my first level map. Or they wouldn't in which case they're probably not trying to look at my node->arc->node combinations anyway. Dave   Received: from PIZZA.BBN.COM by BBN.COM id aa06326; 7 Jul 94 14:46 EDT Received: from pizza by PIZZA.BBN.COM id aa29075; 7 Jul 94 14:30 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa29071; 7 Jul 94 14:28 EDT Received: from wd40.ftp.com by BBN.COM id aa05012; 7 Jul 94 14:26 EDT Received: from ftp.com by ftp.com ; Thu, 7 Jul 1994 14:26:55 -0400 Received: from mailserv-D.ftp.com by ftp.com ; Thu, 7 Jul 1994 14:26:55 -0400 Received: by mailserv-D.ftp.com (5.0/SMI-SVR4) id AA09174; Thu, 7 Jul 94 14:24:54 EDT Date: Thu, 7 Jul 94 14:24:54 EDT Message-Id: <9407071824.AA09174@mailserv-D.ftp.com> To: isidro@BBN.COM Subject: Re: Nodes and Arcs From: Frank Kastenholz Reply-To: kasten@ftp.com Cc: nimrod-wg@BBN.COM Content-Length: 5175 > The questions is: "Should arcs have attributes?"... > ...The question is therefore "purely cosmetical", No it's not. There are implementation concerns. If arcs do not have attributes, I might chose an implementation strategy that uses datastructures to represent the nodes, and an array of pointers within that node/datastructure to represent the arcs which originate at the node. If arcs have attributes then they will require more than just a pointer. Also, if arcs have attributes then those attributes will need to be carried around in the protocols (increasing the bandwidth required to carry the routing traffic, increasing the complexity of the protocols, and therefore the likelyhood of implementation errors, decreasing the likelihood of interoperability, etc etc etc). There's also the increased configuration burden on the operators. And of course, there are costs for arcs-without-attributes as well. If ther should be an attribute associated with an arc, that arc would need to be replaced with two arcs, and a 'virtual node' where the attributes can be hung -- and this will increase the number of arcs and nodes that need to be dealt with. I'm not arguing for or against arcs with attributes. I am merely pointing out that the issue is not merely cosmetic. > Think of the physical internet. It is composed of hosts, routers, > point-to-point links (e.g., T1 links) and networks (ethernets, X.25 > nets, etc.). These elements connect to each other at interfaces. For > example, we can identify an interface between a router and a T1 link, > and an interface between a host and an ethernet. Interfaces are not > like hosts, routers, networks and links in that they are logical > constructs; the others are physical devices. > > A node is defined by a set of interfaces. The set of interfaces that > defines a node is such that when the connections at these interfaces > are broken, the network is partitioned in two. One of these parts is > the node, the other is the rest of the network. Arcs represent > interfaces between nodes. > > The thing is that interfaces *have* properties. For example, the > interface between a host and an ethernet can transmit at a maximum > rate, etc. How should these properties be represented: To be honest, I've not yet completely read through the latest drafts -- pressure of other matters -- so I might be 'a bit confused'. Let's see if I basically understand things here. Basically, the map-nodes represent things like individual networks (such as ethernets, X.25 clouds, PPP links and the like) and hosts/routers. The interface between a host/router and a network medium is the map-arc. Is this right? (ignoring the fact that we can aggregate piles of map-nodes and map-arcs down into a single map-node and all that...) Assuming that I understand things... So, between any two physical, network nodes A and B, (hosts/routers, etc) there will be an interface on net-node A, an interface on net-node B and a bit of network-medium (a hunk of ethernet cable, a WAN link, whatever). Yes? The graph would look like: +------------+ +------------------+ +------------+ | Host A +----------+ Network Medium M +-------+ Host B | +------------+ ^ +------------------+ ^ +------------+ | | Host A's Interface Host B's Interface We could just tag the 'Network Medium' Map-Node with the attributes. This would imply that all attributes are the same for all map-nodes that connect to a 'network-medium' map-node (that is, if hosts C through Q also connected to Network Medium M the attributes of Network Medium M would apply to ALL communications between any pair of hosts A-M). However, if different attributes are required, this could be modelled as using multiple 'network-medium' map-nodes to model a single physical medium. Each of these 'network-medium' map-nodes would represent a single set of attributes and the 'network-node' map-nodes that are connected to the 'network-medium' map-node are the only network-nodes to which those attributes apply. For example, suppose I had some 'allocatable-bandwidth' medium and I have a bunch of hosts and routers, A...Q. Suppose that I wish to allocate 100mbits/sec to A, B and C, and 50mb/sec to all A...Q. There would be 2 'network-medium' map-nodes, lets call them Y and Z. Y might have an attribute of 50mbits/sec and Z an attribute of 100mbits/sec. So, all the nodes, A...Q, would have connections to node Y (i.e., there would be arcs A-Y, B-Y, C-Y, D-Y, E-Y, F-Y,... Q-Y) and only nodes A, B and C would have connections to node Z (arcs A-Z, B-Z, C-Z). Are attributes symmetric? That is, could a given map-node use different attributes when passing data TO an adjacent map-node as opposed to when receiving data FROM the adjacent map-node (i.e. the adjacent map-node is sending to the local map-node). If this can occur then it would seem that arcs must have attributes, or there must be something like the node-connecting-point. -- Frank Kastenholz FTP Software 2 High Street North Andover, Mass. USA 01845 (508)685-4000   Received: from PIZZA.BBN.COM by BBN.COM id aa07077; 7 Jul 94 14:58 EDT Received: from pizza by PIZZA.BBN.COM id aa29235; 7 Jul 94 14:43 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa29231; 7 Jul 94 14:41 EDT Received: from wd40.ftp.com by BBN.COM id aa05858; 7 Jul 94 14:40 EDT Received: from ftp.com by ftp.com ; Thu, 7 Jul 1994 14:39:55 -0400 Received: from mailserv-D.ftp.com by ftp.com ; Thu, 7 Jul 1994 14:39:55 -0400 Received: by mailserv-D.ftp.com (5.0/SMI-SVR4) id AA09319; Thu, 7 Jul 94 14:37:54 EDT Date: Thu, 7 Jul 94 14:37:54 EDT Message-Id: <9407071837.AA09319@mailserv-D.ftp.com> To: nimrod-wg@BBN.COM Subject: Forwarded: IPng ADs Wish to Gauge Consensus on Address Length Requirements From: Frank Kastenholz Reply-To: kasten@ftp.com Content-Length: 3098 This came out on the TUBA, etc, mailing lists. I'm sure that there will be some people in nimrod-land who will want to comment.... Return-Path: Date: Thu, 7 Jul 1994 14:07:19 -0400 From: IPng Area Directors Reply-To: big-internet@munnari.oz.au Subject: IPng ADs Wish to Gauge Consensus on Address Length Requirements Status: R Apparently-To: tuba@Lanl.GOV Content-Type: text Content-Length: 2630 Hi, TUBA, SIPP, CATNIP, BIG-INTERNET, and IETF: This message is one last pre-Toronto recommendation attempt to gauge the extent of consensus on one of the IPng issues. We apologize for duplications. We wanted to reach a wide audience. Steve Deering's message "Chicago Meeting -- Possible Changes to SIPP" to the SIPP list a while back elicited quite a bit of discussion on various lists (both SIPP and big-internet and in other venues) about the length of "address" required for an IPng. We have also had considerable discussion within the directorate. At this time it would appear to us that there is considerable consensus that a fixed length, topologically structured, hierarchical address 16 bytes in length is reasonable for an IPng (that is meets the needs of the very very large-scale Internet). We understand that we are being a bit vague in using the term "address" in light of the question we asked two weeks ago. For the purposes of this request, please assume that the transport level and internet level names are the same. Some hold the view that 16 bytes is larger than would be required for any imaginable Internet structure in the future and that an 8 byte address is all that is required. There seems to be a stronger, but still minority, view that, for various reasons, a variable length address, one that could be smaller or larger than 16 bytes, would meet the needs better for the future of the Internet. Much of the discussion on the lists has revolved around the relative efficiency of processing fixed and variable length addresses. We would like to assess the consensus just on the length for the future Internet, instead of discussing efficiency any more at this time. We want to make sure that we have understood consensus on meeting the needs of the very very large Internet. Therefore, this message is to ask people what present or future rationale they see for one of: 8 byte fixed length address. 16 byte fixed length address. longer than 16 byte fixed length address now. only 16 byte length addresses now but ability to lengthen the address later. To amplify a bit more, we are especially interested in your views on the address length's ability to offer: routing aggregation power topological flexibility adminstrative manageability At this point the consensus among the IPng directorate and on several of the mailing lists seems fairly clear (a 16 byte length address is good for those things). This is a good time to bring forward your remaining views about the requirements for address length for IPng. Thank you, Scott and Allison   Received: from PIZZA.BBN.COM by BBN.COM id aa09108; 7 Jul 94 15:23 EDT Received: from pizza by PIZZA.BBN.COM id aa29530; 7 Jul 94 15:09 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa29526; 7 Jul 94 15:07 EDT Received: from quern.epilogue.com by BBN.COM id aa07524; 7 Jul 94 15:04 EDT From: Dave Bridgham Sender: dab@epilogue.com To: nimrod-wg@BBN.COM In-reply-to: Frank Kastenholz's message of Thu, 7 Jul 94 14:24:54 EDT <9407071824.AA09174@mailserv-D.ftp.com> Subject: Nodes and Arcs Date: Thu, 7 Jul 94 15:04:27 -0400 Message-ID: <9407071504.aa10502@quern.epilogue.com> Date: Thu, 7 Jul 94 14:24:54 EDT From: Frank Kastenholz I'm not arguing for or against arcs with attributes. I am merely pointing out that the issue is not merely cosmetic. It's like saying that all turing complete languages have merely cosmetic differences. On the other hand, since the conversion is pretty straightforward in this case, "merely cosmetic" seems appropriate. Are attributes symmetric? That is, could a given map-node use different attributes when passing data TO an adjacent map-node as opposed to when receiving data FROM the adjacent map-node (i.e. the adjacent map-node is sending to the local map-node). Arcs are unidirectional. Therefore attributes on arcs are asymmetric whereas attributes on nodes are symmetric. If you want asymmetric attributes when you don't have attributes on arcs, the normal translation of replacing each attributed arc with an arc->node->arc combination works. With symmetric attributes you might want to be clever and try to notice that the attributes for the two directions are identical and build a single node with two arcs out each side. If symmetric attributes on arcs are going to be common then if we're not careful you end up storing that same attribute information twice for each arc pair. On the other hand, I have map language ideas that can fix this. It's a useful way of reducing the redundency I think even if you don't have attributes on arcs, I suspect maps will tend to repeat the same attributes many times. (Since you've heard me talk about this before, Frank, I bet you can guess my approach). If this can occur then it would seem that arcs must have attributes, or there must be something like the node-connecting-point. No, you just run the inbound and outbound arcs through nodes with different attributes. Dave   Received: from PIZZA.BBN.COM by BBN.COM id aa11654; 7 Jul 94 15:54 EDT Received: from pizza by PIZZA.BBN.COM id aa29741; 7 Jul 94 15:41 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa29737; 7 Jul 94 15:39 EDT Received: from wd40.ftp.com by BBN.COM id aa10794; 7 Jul 94 15:37 EDT Received: from ftp.com by ftp.com ; Thu, 7 Jul 1994 15:37:12 -0400 Received: from mailserv-D.ftp.com by ftp.com ; Thu, 7 Jul 1994 15:37:12 -0400 Received: by mailserv-D.ftp.com (5.0/SMI-SVR4) id AA10227; Thu, 7 Jul 94 15:35:07 EDT Date: Thu, 7 Jul 94 15:35:07 EDT Message-Id: <9407071935.AA10227@mailserv-D.ftp.com> To: dab@epilogue.com Subject: Re: Nodes and Arcs From: Frank Kastenholz Reply-To: kasten@ftp.com Cc: nimrod-wg@BBN.COM Content-Length: 669 > > I'm not arguing for or against arcs with attributes. I am merely > pointing out that the issue is not merely cosmetic. > > It's like saying that all turing complete languages have merely > cosmetic differences. On the other hand, since the conversion is > pretty straightforward in this case, "merely cosmetic" seems > appropriate. So, "merely cosmetic" implies (to me) "no fundamental architectural differences, or concerns", eh? If so, then the decision would be based on other concerns such as ease of administration, implementability, and so on. -- Frank Kastenholz FTP Software 2 High Street North Andover, Mass. USA 01845 (508)685-4000   Received: from PIZZA.BBN.COM by BBN.COM id aa12551; 7 Jul 94 16:09 EDT Received: from pizza by PIZZA.BBN.COM id aa29829; 7 Jul 94 15:54 EDT Received: from TTL.BBN.COM by PIZZA.BBN.COM id aa29825; 7 Jul 94 15:51 EDT To: kasten@ftp.com cc: nimrod-wg@BBN.COM Subject: Re: Nodes and Arcs In-reply-to: Your message of Thu, 07 Jul 94 14:24:54 -0400. <9407071824.AA09174@mailserv-D.ftp.com> Date: Thu, 07 Jul 94 15:48:12 -0400 From: Ram Ramanathan >at the node. If arcs have attributes then they will require more than >just a pointer. Also, if arcs have attributes then those attributes >will need to be carried around in the protocols (increasing the >bandwidth required to carry the routing traffic, increasing the ^^^^^^^^^ >complexity of the protocols, and therefore the likelyhood of >implementation errors, decreasing the likelihood of interoperability, >etc etc etc). There's also the increased configuration burden on the >operators. I don't think that the bandwidth required to carry routing traffic changes depending on whether arcs have attributes or not. You have a certain set of attributes that need to be transported anyway. Whether they are transported from arcs or from nodes does not affect the total quantity of information that is/needs to be transported. If anything, the amount of map information for the arcs-without- attributes model is higher as you also pointed out. The additional information is the extra arc and node that you create. For a map with N nodes (with attributes) and E arcs (with attributes) it seems to me that with the arcs-without-attributes model, you would need N+E nodes (with attributes) and 2E arcs (without attributes). Note that the attributes themselves do not go away, they simply move to a different place. > > Are attributes symmetric? That is, could a given map-node use > different attributes when passing data TO an adjacent map-node as > opposed to when receiving data FROM the adjacent map-node (i.e. the > adjacent map-node is sending to the local map-node). If this can > occur then it would seem that arcs must have attributes, or there > must be something like the node-connecting-point. > I don't think that we want to assume that attributes are symmetric. Except at the bottommost level, attributes like bandwidth/delay/jitter etc. are "virtual" attributes composed of many physical segments. Thus, the attributes could be assymetric (different congestion levels in either direction etc.). Policies may also be assymetric. Arcs-with-attributes is at least as powerful as arcs-without-attributes in terms of representation. Even if we can draw our current day maps so that arcs have no attributes, not prohibiting arcs to have attributes gives us "future-proofing" which is a design plus. Yes? Cheers, - Ram. -------------------------------------------------------------- Ram Ramanathan Advanced Networking R & D BBN Systems and Technologies 10 Moulton Street, Cambridge, MA 02138 Phone : (617) 873-2736 INTERNET : ramanath@bbn.com   Received: from PIZZA.BBN.COM by BBN.COM id aa13575; 7 Jul 94 16:28 EDT Received: from pizza by PIZZA.BBN.COM id aa00131; 7 Jul 94 16:13 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa00123; 7 Jul 94 16:11 EDT Received: from quern.epilogue.com by BBN.COM id aa12438; 7 Jul 94 16:06 EDT From: Dave Bridgham Sender: dab@epilogue.com To: nimrod-wg@BBN.COM In-reply-to: Ram Ramanathan's message of Thu, 07 Jul 94 15:48:12 -0400 <9407071602.aa10917@quern.epilogue.com> Subject: Nodes and Arcs Date: Thu, 7 Jul 94 16:06:13 -0400 Message-ID: <9407071606.aa10951@quern.epilogue.com> Date: Thu, 07 Jul 94 15:48:12 -0400 From: Ram Ramanathan Arcs-with-attributes is at least as powerful as arcs-without-attributes in terms of representation. Even if we can draw our current day maps so that arcs have no attributes, not prohibiting arcs to have attributes gives us "future-proofing" which is a design plus. Yes? No. The two are computationally identical. You can not represent anything with one that you can not also represent with the other. Dave   Received: from PIZZA.BBN.COM by BBN.COM id aa13651; 7 Jul 94 16:29 EDT Received: from pizza by PIZZA.BBN.COM id aa00121; 7 Jul 94 16:12 EDT Received: from KARIBA.BBN.COM by PIZZA.BBN.COM id aa00114; 7 Jul 94 16:10 EDT To: kasten@ftp.com cc: dab@epilogue.com, nimrod-wg@BBN.COM Subject: Re: Nodes and Arcs In-reply-to: Your message of Thu, 07 Jul 94 15:35:07 -0400. <9407071935.AA10227@mailserv-D.ftp.com> Date: Thu, 07 Jul 94 16:06:43 -0400 From: Isidro Castineyra >> > >> > I'm not arguing for or against arcs with attributes. I am merely >> > pointing out that the issue is not merely cosmetic. >> > >> > It's like saying that all turing complete languages have merely >> > cosmetic differences. On the other hand, since the conversion is >> > pretty straightforward in this case, "merely cosmetic" seems >> > appropriate. >> >>So, "merely cosmetic" implies (to me) "no fundamental architectural >>differences, or concerns", eh? If so, then the decision would be >>based on other concerns such as ease of administration, >>implementability, and so on. >> >> My feelings exactly. Please let me know your preferences. Isidro Isidro Castineyra (isidro@bbn.com) Bolt Beranek and Newman, Incorporated (617) 873-6233 10 Moulton Street, Cambridge, MA 02138 USA   Received: from PIZZA.BBN.COM by BBN.COM id aa13836; 7 Jul 94 16:32 EDT Received: from pizza by PIZZA.BBN.COM id aa00200; 7 Jul 94 16:16 EDT Received: from BBN.COM by PIZZA.BBN.COM id ab00193; 7 Jul 94 16:14 EDT Received: from quern.epilogue.com by BBN.COM id aa12695; 7 Jul 94 16:11 EDT From: Dave Bridgham Sender: dab@epilogue.com To: nimrod-wg@BBN.COM In-reply-to: Frank Kastenholz's message of Thu, 7 Jul 94 15:35:07 EDT <9407071935.AA10227@mailserv-D.ftp.com> Subject: Nodes and Arcs Date: Thu, 7 Jul 94 16:11:18 -0400 Message-ID: <9407071611.aa10990@quern.epilogue.com> Date: Thu, 7 Jul 94 15:35:07 EDT From: Frank Kastenholz So, "merely cosmetic" implies (to me) "no fundamental architectural differences, or concerns", eh? If so, then the decision would be based on other concerns such as ease of administration, implementability, and so on. Gee, I hate to agree with you. It's so much more fun to be contrary. Oh well. I agree. Dave   Received: from PIZZA.BBN.COM by BBN.COM id aa14033; 7 Jul 94 16:36 EDT Received: from pizza by PIZZA.BBN.COM id aa00254; 7 Jul 94 16:23 EDT Received: from TTL.BBN.COM by PIZZA.BBN.COM id aa00250; 7 Jul 94 16:21 EDT To: nimrod-wg@BBN.COM Subject: Re: Nodes and Arcs In-reply-to: Your message of Thu, 07 Jul 94 12:27:10 -0400. Date: Thu, 07 Jul 94 16:22:53 -0400 From: Ram Ramanathan > > A few approaches: > > 1. Bestow attributes on Arcs; represent an interface's properties as > arcs attributes. > > 2. Arcs have no attributes; represent an interface as an > arc->node->arc combination, the properties of the interface appear as > attributes of the node. > > 3. Create an interface construct at the map level: the node connecting > point of the first Nimrod architecture draft. (So far, interfaces have > shown up on physical networks, not on maps). Make these connecting > points be attributes of the nodes, and make the connecting points have > their own attributes, these represent the properties of the physical > interfaces. > > 4. Bury the properties of the interface in the transit connectivity > specification of the node. > > 5. What am I missing? ^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^^ #2 represents the case when only nodes have attributes. #1 represents the case when both arcs and nodes have attributes. How about the natural question : Only arcs have attributes, nodes do not? Note that to squeeze out attributes from a node, we may replace that node by a complete graph of D nodes (D = degree of the node) with the attributes on the arcs and none on the node. Example with one attribute A : A ------O------- | | becomes A -----*----*---- \ / A \ /A \/ * | | The *'s are the nodes. They have no attributes. Abstraction now occurs in terms of arcs and not nodes. However, I do not wish to throw another fish in the basket. I am happy with attributes on arcs and nodes or on nodes alone. Simply wanted to bring out the possibility. Cheers, - Ram. -------------------------------------------------------------- Ram Ramanathan Advanced Networking R & D BBN Systems and Technologies 10 Moulton Street, Cambridge, MA 02138 Phone : (617) 873-2736 INTERNET : ramanath@bbn.com   Received: from PIZZA.BBN.COM by BBN.COM id aa14497; 7 Jul 94 16:43 EDT Received: from pizza by PIZZA.BBN.COM id aa00315; 7 Jul 94 16:29 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa00311; 7 Jul 94 16:27 EDT Received: from quern.epilogue.com by BBN.COM id aa13488; 7 Jul 94 16:25 EDT From: Dave Bridgham Sender: dab@epilogue.com To: Ram Ramanathan Cc: nimrod-wg@BBN.COM Subject: do I need to apologize Date: Thu, 7 Jul 94 16:25:28 -0400 Message-ID: <9407071625.aa11086@quern.epilogue.com> I am realizing that the message I just send in response to Ram's message to nimrod-wg might be read as being a bit sharp. I didn't intend for it to come out that way and apologize to Ram if that's how I sounded. I'll attempt to think through my responses a little better in the future. Dave   Received: from PIZZA.BBN.COM by BBN.COM id aa18404; 7 Jul 94 17:58 EDT Received: from pizza by PIZZA.BBN.COM id aa00673; 7 Jul 94 17:43 EDT Received: from TTL.BBN.COM by PIZZA.BBN.COM id aa00669; 7 Jul 94 17:41 EDT To: Dave Bridgham cc: nimrod-wg@BBN.COM Subject: Re: Nodes and Arcs In-reply-to: Your message of Thu, 07 Jul 94 16:06:13 -0400. <9407071606.aa10951@quern.epilogue.com> Date: Thu, 07 Jul 94 17:39:11 -0400 From: Ram Ramanathan > From: Dave Bridgham > Sender: dab@epilogue.com > To: nimrod-wg@BBN.COM > In-reply-to: Ram Ramanathan's message of Thu, 07 Jul 94 15:48:12 -0400 <9407071602.aa10917@quern.epilogue.com> > Subject: Nodes and Arcs > Date: Thu, 7 Jul 94 16:06:13 -0400 > Message-ID: <9407071606.aa10951@quern.epilogue.com> > > Date: Thu, 07 Jul 94 15:48:12 -0400 > From: Ram Ramanathan > > Arcs-with-attributes is at least as powerful as arcs-without-attributes > in terms of representation. Even if we can draw our current day maps > so that arcs have no attributes, not prohibiting arcs to have attributes > gives us "future-proofing" which is a design plus. Yes? > > No. The two are computationally identical. You can not represent > anything with one that you can not also represent with the other. > > Dave I am not arguing the point about their computational power. One can easily prove that they are computationally identical. The fact that they are computationally identical, however, does not mean that it does not matter what method I use. To cite an extreme analogy, I would not like to write my programs using a Turing Machine even though it is computationally as powerful as any programming language. My comment on future proofing is in regard to giving the *option* to implementors. You say you would probably write your implementation with attributes on nodes only. Suppose Amanda prefers to use attributes both on arcs and nodes or even just on arcs (see my message on this possibility). Or you for some unknown reason have a change of mind in the future? Should we preclude that from happening? I think you answered No to the wrong question, but let me know if I am wrong. Cheers, - Ram.   Received: from PIZZA.BBN.COM by BBN.COM id aa18795; 7 Jul 94 18:08 EDT Received: from pizza by PIZZA.BBN.COM id aa00755; 7 Jul 94 17:53 EDT Received: from TTL.BBN.COM by PIZZA.BBN.COM id aa00751; 7 Jul 94 17:51 EDT To: Dave Bridgham cc: nimrod-wg@BBN.COM Subject: Re: do I need to apologize In-reply-to: Your message of Thu, 07 Jul 94 16:25:28 -0400. <9407071625.aa11086@quern.epilogue.com> Date: Thu, 07 Jul 94 17:48:16 -0400 From: Ram Ramanathan Dave, > From: Dave Bridgham > Sender: dab@epilogue.com > To: Ram Ramanathan > Cc: nimrod-wg@BBN.COM > Subject: do I need to apologize > Date: Thu, 7 Jul 94 16:25:28 -0400 > Message-ID: <9407071625.aa11086@quern.epilogue.com> > > I am realizing that the message I just send in response to Ram's > message to nimrod-wg might be read as being a bit sharp. I didn't > intend for it to come out that way and apologize to Ram if that's how > I sounded. I'll attempt to think through my responses a little better > in the future. > > Dave No offence taken, but thanks for making it clear how you meant it. Cheers, - Ram.   Received: from PIZZA.BBN.COM by BBN.COM id aa21413; 7 Jul 94 19:16 EDT Received: from pizza by PIZZA.BBN.COM id aa01174; 7 Jul 94 19:02 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa01167; 7 Jul 94 19:00 EDT Received: from quern.epilogue.com by BBN.COM id aa20770; 7 Jul 94 18:58 EDT From: Dave Bridgham Sender: dab@epilogue.com To: nimrod-wg@BBN.COM In-reply-to: Ram Ramanathan's message of Thu, 07 Jul 94 17:39:11 -0400 <9407071742.aa11604@quern.epilogue.com> Subject: Nodes and Arcs Date: Thu, 7 Jul 94 18:57:26 -0400 Message-ID: <9407071857.aa11957@quern.epilogue.com> Date: Thu, 07 Jul 94 17:39:11 -0400 From: Ram Ramanathan I get the feeling we're talking at cross purposes but I can't figure out why. The fact that they are computationally identical, however, does not mean that it does not matter what method I use. To cite an extreme analogy, I would not like to write my programs using a Turing Machine even though it is computationally as powerful as any programming language. Right. This I take as being in agreement then with Frank's comment that the decision is based then on which is easier to deal with for implementation or administration reasons. My comment on future proofing is in regard to giving the *option* to implementors. You say you would probably write your implementation with attributes on nodes only. Suppose Amanda prefers to use attributes both on arcs and nodes or even just on arcs (see my message on this possibility). Or you for some unknown reason have a change of mind in the future? Should we preclude that from happening? We have to either allow attributes on arcs or not. Whichever we do, if an implementation does the other then it will have to convert the language to its internal representation. Isidro enumerated the conversion both ways neither of which is terribly tedious. (I'm sure the conversion to and from only arcs have attributes is equally straightforward.) [Warning! In the following I use nodes and arcs two different ways. Sometimes I'm talking about the nodes and arcs of the network map and sometimes I'm talking about the nodes and arcs in a graph that's in the memory of an imagined implementation. I try to be explicit about which I mean.] In my mind I reasoned thusly about how an implementation would go: in memory I'll have structures and pointers. Those structures and pointers make a graph where the structures are the nodes of the graph and the pointers the arcs. Since no language I work with lets me put extra information on pointers, anything with attributes must have a structure therefore it will be a node in the graph in my implementation. If arcs in the network graph have attributes my implementation will have to convert them to nodes for the internal representation. I'm not quite so bold as to claim that all implementations will have to do this conversion, but I'm fairly sure that's how I'd do it. Since, as Frank pointed out, we need to make the decision based on what's easier, I concluded that my preference was no attributes on arcs since that would make it easier for me to implement since I wouldn't have to do the conversion. Since I believe I know how to do the conversion (except maybe for the optimization of bidirectional links to one node instead of two which I know how to do but might just decide it's too much work) I can accept either answer. That's the implementation reason why I prefer no attributes on arcs. I can also talk about the administrative reasons I think that but perhaps in a separate message if anyone cares. I think you answered No to the wrong question, but let me know if I am wrong. You suggested that we not preclude attributes on arcs in case we someday want them. If so, then any implementation that works as I described above MUST implement the conversion. You seemed to be saying you wanted to allow this flexibility. I meant to answer that it provably gives no more flexibility and I thought it did cost some in the implementation. Now, what about an implementation that allows attributes on arcs too. If we don't allow this in the language then when it reads a map it'll just never get any attributes to put on its arcs. No big deal. The one hairy part is that I think, in this discussion, no attributes also means no locator. If an implementation needs a locator for its arcs too and we don't have them in the map language then things might get difficult. I suppose there's the question of why would anyone do such an implementation if the map language meant it wouldn't work. Dave   Received: from PIZZA.BBN.COM by BBN.COM id aa28281; 7 Jul 94 22:26 EDT Received: from pizza by PIZZA.BBN.COM id aa02022; 7 Jul 94 21:55 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa02018; 7 Jul 94 21:52 EDT Received: from vinegar.sesqui.net by BBN.COM id aa26338; 7 Jul 94 21:53 EDT Received: by vinegar.sesqui.net (4.1/SMI-4.1 Jun93 - wcm) id AA19618; Thu, 7 Jul 94 20:54:06 CDT From: William Manning Message-Id: <9407080154.AA19618@vinegar.sesqui.net> Subject: Re: Nodes and Arcs To: Isidro Castineyra Date: Thu, 7 Jul 1994 20:54:05 -0500 (CDT) Cc: kasten@ftp.com, dab@epilogue.com, nimrod-wg@BBN.COM In-Reply-To: <9407072026.AA08219@is.rice.edu> from "Isidro Castineyra" at Jul 7, 94 04:06:43 pm X-Mailer: ELM [version 2.4 PL22] Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Content-Length: 318 Par'm me, but I am having a bit of difficulty here. Having waded through the drafts I am left with the impression that "node" is an instantiation of a common locator applied to one or more EIDS. If this is correct, then the only basic building blocks for nimrod are EIDS and arcs. Or am I out in the weeds? -bill   Received: from PIZZA.BBN.COM by BBN.COM id aa12408; 8 Jul 94 9:25 EDT Received: from pizza by PIZZA.BBN.COM id aa04311; 8 Jul 94 9:14 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa04303; 8 Jul 94 9:11 EDT Received: from wd40.ftp.com by BBN.COM id aa11162; 8 Jul 94 9:09 EDT Received: from ftp.com by ftp.com ; Fri, 8 Jul 1994 09:09:23 -0400 Received: from mailserv-D.ftp.com by ftp.com ; Fri, 8 Jul 1994 09:09:23 -0400 Received: by mailserv-D.ftp.com (5.0/SMI-SVR4) id AA16360; Fri, 8 Jul 94 09:07:21 EDT Date: Fri, 8 Jul 94 09:07:21 EDT Message-Id: <9407081307.AA16360@mailserv-D.ftp.com> To: ramanath@BBN.COM Subject: Re: Nodes and Arcs From: Frank Kastenholz Reply-To: kasten@ftp.com Cc: dab@epilogue.com, nimrod-wg@BBN.COM Content-Length: 774 > From: Ram Ramanathan > > My comment on future proofing is in regard to giving the *option* to > implementors. You say you would probably write your implementation > with attributes on nodes only. Suppose Amanda prefers to use attributes both > on arcs and nodes or even just on arcs (see my message on this possibility). > Or you for some unknown reason have a change of mind in the future? > Should we preclude that from happening? Let's not forget interoperability here. If implementation A allows for attributes on nodes only, and implementation B allows for attributes on both nodes and arcs, how will the two implementations interoperate? -- Frank Kastenholz FTP Software 2 High Street North Andover, Mass. USA 01845 (508)685-4000   Received: from PIZZA.BBN.COM by BBN.COM id aa12574; 8 Jul 94 9:27 EDT Received: from pizza by PIZZA.BBN.COM id aa04299; 8 Jul 94 9:14 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa04295; 8 Jul 94 9:11 EDT Received: from wd40.ftp.com by BBN.COM id aa11153; 8 Jul 94 9:09 EDT Received: from ftp.com by ftp.com ; Fri, 8 Jul 1994 09:09:21 -0400 Received: from mailserv-D.ftp.com by ftp.com ; Fri, 8 Jul 1994 09:09:21 -0400 Received: by mailserv-D.ftp.com (5.0/SMI-SVR4) id AA16354; Fri, 8 Jul 94 09:07:19 EDT Date: Fri, 8 Jul 94 09:07:19 EDT Message-Id: <9407081307.AA16354@mailserv-D.ftp.com> To: ramanath@BBN.COM Subject: Re: Nodes and Arcs From: Frank Kastenholz Reply-To: kasten@ftp.com Cc: nimrod-wg@BBN.COM Content-Length: 3464 > I don't think that the bandwidth required to carry routing traffic changes > depending on whether arcs have attributes or not. You have a certain > set of attributes that need to be transported anyway. Whether they are > transported from arcs or from nodes does not affect the total quantity > of information that is/needs to be transported. It does, slightly. You are right as far as the bandwidth to actually carry the attributes -- that won't really change. However, the bandwidth to carry the 'arc' will grow slightly because there will need to be an additional field that says how many attributes are associated with the arc. If arcs do not have attributes then they won't need this field. Granted, this is a small growth (and probably not really worth talking about :-). > If anything, the amount of map information for the arcs-without- > attributes model is higher as you also pointed out. The additional > information is the extra arc and node that you create. For a map with > N nodes (with attributes) and E arcs (with attributes) it seems to me > that with the arcs-without-attributes model, you would need > N+E nodes (with attributes) and 2E arcs (without attributes). Note > that the attributes themselves do not go away, they simply move to > a different place. This is not quite what I ( think I ) was saying. later on in my note I started talking about how we actually model a physical network. If the network is modelled so that the actual network media (ethernets, PPP links, etc) are modeled as map-nodes then the attributes could be associated with these map-nodes(*). They have to exist in the system anyway, along with their map-arcs, so there is no increase in overhead for carrying them, and I think that all attributes that we care about can be placed there. (* and due to other work, I've not had the opportunity to fully read the latest drafts - if this modelling is wrong, tell me.) > > Are attributes symmetric? That is, could a given map-node use... > > I don't think that we want to assume that attributes are symmetric... My brain had gone to a cool-climate for a few minutes. Forget what I said... > Arcs-with-attributes is at least as powerful as arcs-without-attributes > in terms of representation. Even if we can draw our current day maps > so that arcs have no attributes, not prohibiting arcs to have attributes > gives us "future-proofing" which is a design plus. Yes? Usually I am fully for leaving as many options as I can in a design in order to deal with future, unseen, possibilities and needs. Therefore I normally would want arcs with attributes. However, I am not sure that I see the possibility that arcs-with-attributes could give us a real benefit in the future at a reasonable implementation cost today. These are 'risk-benefit' analyses. The benefit is that at some unknown time in the future, arcs-with-attributes _may_ let us do something (which we can not forsee today) which we want/need to do that we can't do any other way. The cost is additional architectural, implementation and administrative complexity, more possibility for making non-interoperable implementations, and so on. Since we can always model an arc-with-attributes as an arc-node-arc, I am not sure that there is a benefit in supporting arcs-with-attributes, and the cost seems to be non-trivial. -- Frank Kastenholz FTP Software 2 High Street North Andover, Mass. USA 01845 (508)685-4000   Received: from PIZZA.BBN.COM by BBN.COM id aa12725; 8 Jul 94 9:29 EDT Received: from pizza by PIZZA.BBN.COM id aa04310; 8 Jul 94 9:14 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa04301; 8 Jul 94 9:11 EDT Received: from wd40.ftp.com by BBN.COM id aa11157; 8 Jul 94 9:09 EDT Received: from ftp.com by ftp.com ; Fri, 8 Jul 1994 09:09:22 -0400 Received: from mailserv-D.ftp.com by ftp.com ; Fri, 8 Jul 1994 09:09:22 -0400 Received: by mailserv-D.ftp.com (5.0/SMI-SVR4) id AA16357; Fri, 8 Jul 94 09:07:20 EDT Date: Fri, 8 Jul 94 09:07:20 EDT Message-Id: <9407081307.AA16357@mailserv-D.ftp.com> To: isidro@BBN.COM Subject: Re: Nodes and Arcs From: Frank Kastenholz Reply-To: kasten@ftp.com Cc: dab@epilogue.com, nimrod-wg@BBN.COM Content-Length: 678 > >>So, "merely cosmetic" implies (to me) "no fundamental architectural > >>differences, or concerns", eh? If so, then the decision would be > >>based on other concerns such as ease of administration, > >>implementability, and so on. > > My feelings exactly. Please let me know your preferences. So, assuming that there is no massive explosion in bandwidth required in order to turn the arc-with-attributes into an attributeless_arc-node-attributeless_arc (and I feel that there will not be such an explosion) then I'd suggest that we do not allow for attributes on arcs. -- Frank Kastenholz FTP Software 2 High Street North Andover, Mass. USA 01845 (508)685-4000   Received: from PIZZA.BBN.COM by BBN.COM id aa16622; 8 Jul 94 10:30 EDT Received: from pizza by PIZZA.BBN.COM id aa04728; 8 Jul 94 10:16 EDT Received: from KARIBA.BBN.COM by PIZZA.BBN.COM id aa04724; 8 Jul 94 10:14 EDT To: William Manning cc: kasten@ftp.com, dab@epilogue.com, nimrod-wg@BBN.COM Subject: Re: Nodes and Arcs In-reply-to: Your message of Thu, 07 Jul 94 20:54:05 -0500. <9407080154.AA19618@vinegar.sesqui.net> Date: Fri, 08 Jul 94 10:10:27 -0400 From: Isidro Castineyra Bill, You say, >> >>Par'm me, but I am having a bit of difficulty here. Having waded through >>the drafts I am left with the impression that "node" is an instantiation >>of a common locator applied to one or more EIDS. If this is correct, >>then the only basic building blocks for nimrod are EIDS and arcs. >> Given a map, which represents an internetwork at some level of detail, one can visualize an endpoint as residing in one or more of the map's nodes (an endpoint can have more than one locators); and, therefore, I believe one can think of a node, as you write, as a "common locator applied to one or more EIDs". But I think that node is more than that. A node can have an internal map that represents with more detail the same region of the internetwork represented by the original node. Each of the nodes in this internal map can itself have its own internal map, and so son recursively. The more detailed map presumably has a more accurate description of the connectivity between, and to, endpoints. Thus, using your words, a node is not just a locator applied to a set of EIDS, but a more complex structure. This hierarchical organization of topological information is at the core of nimrod, and, therefore, I believe nodes should be considered as basic building blocks for nimrod. We could make the distinction between a "building block" and "entity". Would you agree to say that arcs and EIDs are "basic entities", while nodes are "basic building blocks" (being made out of the other two)? Thanks, Isidro Isidro Castineyra (isidro@bbn.com) Bolt Beranek and Newman, Incorporated (617) 873-6233 10 Moulton Street, Cambridge, MA 02138 USA   Received: from PIZZA.BBN.COM by BBN.COM id aa20305; 8 Jul 94 11:30 EDT Received: from pizza by PIZZA.BBN.COM id aa05084; 8 Jul 94 11:14 EDT Received: from KARIBA.BBN.COM by PIZZA.BBN.COM id aa05080; 8 Jul 94 11:12 EDT To: kasten@ftp.com cc: nimrod-wg@BBN.COM Subject: Re: Nodes and Arcs In-reply-to: Your message of Fri, 08 Jul 94 09:07:20 -0400. <9407081307.AA16357@mailserv-D.ftp.com> Date: Fri, 08 Jul 94 11:09:05 -0400 From: Isidro Castineyra Frank, >>So, assuming that there is no massive explosion in bandwidth required >>in order to turn the arc-with-attributes into an >>attributeless_arc-node-attributeless_arc (and I feel that there will >>not be such an explosion) then I'd suggest that we >>do not allow for attributes on arcs. >> One more comment. I just realized a reason why I think that the arc->node->arc (where the arcs have no attributes) is a kludge: that node will have a locator that will never be the destination of a packet. In my mental model, nodes have always been places where endpoints "reside". Here we are creating a node for the sole purpose of holding the bag, I mean, the attributes. This bugs me. But I do not think that this is a killer argument. Isidro   Received: from PIZZA.BBN.COM by BBN.COM id aa21811; 8 Jul 94 11:52 EDT Received: from pizza by PIZZA.BBN.COM id aa05282; 8 Jul 94 11:39 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa05278; 8 Jul 94 11:37 EDT Received: from quern.epilogue.com by BBN.COM id aa20711; 8 Jul 94 11:34 EDT From: Dave Bridgham Sender: dab@epilogue.com To: nimrod-wg@BBN.COM In-reply-to: Isidro Castineyra's message of Fri, 08 Jul 94 11:09:05 -0400 <9407081123.aa17294@quern.epilogue.com> Subject: Nodes and Arcs Date: Fri, 8 Jul 94 11:33:51 -0400 Message-ID: <9407081133.aa17325@quern.epilogue.com> What about network nodes? They don't contain endpoints. Their purpose is to reduce the number of arcs from O(N^2) to O(N) and also collapse the redundent attributes from all those arcs which are common to the network. In the architecture document didn't you give locators to arcs which also will never be the destination of a packet? I think a better way of thinking about it is that we have to give a locator to anything in the map we need to name. We might not name it as a destination but only as a hop in a route. Dave   Received: from PIZZA.BBN.COM by BBN.COM id aa23448; 8 Jul 94 12:22 EDT Received: from pizza by PIZZA.BBN.COM id aa05509; 8 Jul 94 12:06 EDT Received: from KARIBA.BBN.COM by PIZZA.BBN.COM id aa05503; 8 Jul 94 12:04 EDT To: kasten@ftp.com cc: ramanath@BBN.COM, dab@epilogue.com, nimrod-wg@BBN.COM Subject: Re: Nodes and Arcs In-reply-to: Your message of Fri, 08 Jul 94 09:07:21 -0400. <9407081307.AA16360@mailserv-D.ftp.com> Date: Fri, 08 Jul 94 12:00:11 -0400 From: Isidro Castineyra Frank, >> >>Let's not forget interoperability here. If implementation A allows >>for attributes on nodes only, and implementation B allows for >>attributes on both nodes and arcs, how will the two implementations >>interoperate? >> I think implementations will interoperate as long as Nimrod-itself (das Ding als sich) allows only one way. Implementors can do anything they want inside their boxes. Nimrod will allow only one way. That is, when moving around maps, the protocols will be able to speak only in terms of one of the two models. It is the burden of the implementor to translate back and forth. I imagine that Nimrod's choice will bias how the implementor will do it. I find it hard to believe that an implementor would insist on doing arcs-with-attributes if Nimrod does not. (How would one know what combination of arc->node->arc was an arc with attributes. Does that question even make sense?). Isidro   Received: from PIZZA.BBN.COM by BBN.COM id aa01028; 8 Jul 94 14:27 EDT Received: from pizza by PIZZA.BBN.COM id aa06167; 8 Jul 94 14:03 EDT Received: from KARIBA.BBN.COM by PIZZA.BBN.COM id aa06163; 8 Jul 94 13:59 EDT To: Dave Bridgham cc: nimrod-wg@BBN.COM, isidro@BBN.COM Subject: Re: Nodes and Arcs In-reply-to: Your message of Fri, 08 Jul 94 11:33:51 -0400. <9407081133.aa17325@quern.epilogue.com> Date: Fri, 08 Jul 94 13:55:04 -0400 From: Isidro Castineyra (Sorry if you see this twice, having problems with the mailer) >>What about network nodes? They don't contain endpoints. Their >>purpose is to reduce the number of arcs from O(N^2) to O(N) and also >>collapse the redundent attributes from all those arcs which are common >>to the network. >> That was the purpose of multipoint arcs, but we got rid off them. >>In the architecture document didn't you give locators to arcs which >>also will never be the destination of a packet? I think a better way >>of thinking about it is that we have to give a locator to anything in >>the map we need to name. We might not name it as a destination but >>only as a hop in a route. I agree that we have to give a locator to anything in the map that we need to name. You are also right that we have alread introduced nodes that will not be the destination of any packets. Isidro   Received: from PIZZA.BBN.COM by BBN.COM id aa01154; 8 Jul 94 14:29 EDT Received: from pizza by PIZZA.BBN.COM id aa06265; 8 Jul 94 14:09 EDT Received: from KARIBA.BBN.COM by PIZZA.BBN.COM id aa06261; 8 Jul 94 14:07 EDT To: nimrod-wg@BBN.COM Subject: [Dave Bridgham: Nodes and Arcs ] Date: Fri, 08 Jul 94 14:04:01 -0400 From: Isidro Castineyra ------- Forwarded Message Received: from BBN.COM by LISA.BBN.COM id aa00769; 8 Jul 94 12:21 EDT Received: from quern.epilogue.com by BBN.COM id aa23418; 8 Jul 94 12:21 EDT From: Dave Bridgham Sender: dab@epilogue.com To: isidro@BBN.COM In-reply-to: Isidro Castineyra's message of Fri, 08 Jul 94 12:03:27 -0400 <9407081209.aa17497@quern.epilogue.com> Subject: Nodes and Arcs Date: Fri, 8 Jul 94 12:20:54 -0400 Message-ID: <9407081220.aa17598@quern.epilogue.com> I don't recall ever hearing about multipoint arcs. An interesting idea though. Nodes which are agrregates also can't really be destinations. They sort of have locators, depending on what locators look like they may be distinguishable from locators that can be destinations just by examining the locator. There's also the possibility of having nodes that don't have locators. I don't know if this is a good idea but I keep thinking it anyway. Originally Noel had only interfaces and aggregations of interfaces as things with locators. EIDs might be affiliated with interfaces but were not inside interfaces. Maybe multipoint arcs are a good idea. What were the arguments that made them go away? They might be considered confusing I suppose but there's nothing that stops a decent user interface from simply displaying them as nodes with no locator. Dave ------- End of Forwarded Message   Received: from PIZZA.BBN.COM by BBN.COM id aa01596; 8 Jul 94 14:36 EDT Received: from pizza by PIZZA.BBN.COM id aa06393; 8 Jul 94 14:22 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa06389; 8 Jul 94 14:20 EDT Received: from clark.net by BBN.COM id aa00562; 8 Jul 94 14:19 EDT Received: (from hcb@localhost) by clark.net (8.6.9/8.6.9) id OAA03352; Fri, 8 Jul 1994 14:19:27 -0400 From: Howard Berkowitz Message-Id: <199407081819.OAA03352@clark.net> Subject: Re: Nodes and Arcs To: Dave Bridgham Date: Fri, 8 Jul 1994 14:19:26 -0400 (EDT) Cc: nimrod-wg@BBN.COM, "Howard Berkowitz, PSC International" In-Reply-To: <9407081133.aa17325@quern.epilogue.com> from "Dave Bridgham" at Jul 8, 94 11:33:51 am X-Mailer: ELM [version 2.4 PL23] MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Content-Length: 1221 > > What about network nodes? They don't contain endpoints. Their > purpose is to reduce the number of arcs from O(N^2) to O(N) and also > collapse the redundent attributes from all those arcs which are common > to the network. While they may not contain user endpoints, is it not likely that the network node, or cluster if you will, will need to have some sort of identifier for management? Will there not be an arc from the network node to the SNMPng manager? > > In the architecture document didn't you give locators to arcs which > also will never be the destination of a packet? I think a better way > of thinking about it is that we have to give a locator to anything in > the map we need to name. We might not name it as a destination but > only as a hop in a route. > > Dave > Again thinking from an operational standpoint, it is a very useful thing to identify arcs used for specific traffic. Yes, in principle, they might be identified by their terminating nodes, but I have a sense that there may be a need for transient arc identifiers to identify a path between two nodes at a given point in time, using a particular access subnetwork, etc. Howard   Received: from PIZZA.BBN.COM by BBN.COM id aa01855; 8 Jul 94 14:39 EDT Received: from pizza by PIZZA.BBN.COM id aa06422; 8 Jul 94 14:24 EDT Received: from TTL.BBN.COM by PIZZA.BBN.COM id aa06418; 8 Jul 94 14:22 EDT To: nimrod-wg@BBN.COM Subject: Re: Nodes and Arcs In-reply-to: Your message of Fri, 08 Jul 94 12:00:11 -0400. Date: Fri, 08 Jul 94 14:23:14 -0400 From: Ram Ramanathan Frank, Dave, Isidro, I agree with Frank that the implementation complexity of arcs with attributes is higher. More important than the fact that we now have to deal only with attributes on one data type is the following point - when you have attributes on arcs, the representation has to be an equivalent of a "multigraph" (a graph that may have more than one arc between two nodes), whereas in the attributeless-arc model, we can get away with a "normal graph". Because, since arcs represent only connectivity, multiple arcs between nodes are redundant. Multigraphs are a pain in the neck and I like the fact that the attributeless-arcs model gets rid of them. However, I agree with Isidro's initial comment about attributeless-arc model being somewhat of a kludge. For instance, take BBN, MIT and the microwave link between them. I find it more natural to make BBN a node, MIT a node and the microwave link an arc and assign it attributes like bandwidth, bit-error-rate instead of making a node for the link. Perhaps I am prejudiced by the fact that most work on network modelling as graphs uses edge-weighted graphs. So it is a tradeoff (in my mind) for naturalness of representation and implementation complexity. We could go on and on arguing about this. The former is subjective and the latter objective. So I would not be unhappy at all if we go with attribute-less arcs. Cheers, - Ram. -------------------------------------------------------------- Ram Ramanathan Advanced Networking R & D BBN Systems and Technologies 10 Moulton Street, Cambridge, MA 02138 Phone : (617) 873-2736 INTERNET : ramanath@bbn.com   Received: from PIZZA.BBN.COM by BBN.COM id aa05029; 8 Jul 94 15:05 EDT Received: from pizza by PIZZA.BBN.COM id aa06594; 8 Jul 94 14:48 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa06590; 8 Jul 94 14:46 EDT Received: from quern.epilogue.com by BBN.COM id aa02025; 8 Jul 94 14:42 EDT From: Dave Bridgham Sender: dab@epilogue.com To: hcb@clark.net CC: nimrod-wg@BBN.COM In-reply-to: Howard Berkowitz's message of Fri, 8 Jul 1994 14:19:26 -0400 (EDT) <199407081819.OAA03352@clark.net> Subject: Nodes and Arcs Date: Fri, 8 Jul 94 14:40:45 -0400 Message-ID: <9407081440.aa18446@quern.epilogue.com> From: Howard Berkowitz Date: Fri, 8 Jul 1994 14:19:26 -0400 (EDT) While they may not contain user endpoints, is it not likely that the network node, or cluster if you will, will need to have some sort of identifier for management? Will there not be an arc from the network node to the SNMPng manager? I think I do not understand. When you use SNMP to manage your ethernet now, don't you connect to some host on that ethernet rather than the ethernet itself? The endpoint to which you communicate is in that host, the one running the SNMP agent, not in the ethernet. As for an identifier for the network, if all nodes in the graph must have locators what about the locator? One reason for a separate identifier space for endpoints is so that when they move they keep their name. Do we need that also for networks. If a network picks up and reconnects somewhere else, does it need an identifier that remains constant so it retrains its identity or is it sufficient that only the endpoints connected to that network retain their identifiers? Again thinking from an operational standpoint, it is a very useful thing to identify arcs used for specific traffic. Yes, in principle, they might be identified by their terminating nodes, but I have a sense that there may be a need for transient arc identifiers to identify a path between two nodes at a given point in time, using a particular access subnetwork, etc. If arcs don't have attributes then it should be never necessary to specify in preference to another. Remember, in that case arcs are only links on a conceptual graph. Anything that mattered would have attributes and therefore would get a node in the graph. Arcs do not necessarily map to network connections or any other physical reality. Obviously there is some physical mapping, but that mapping will be determined by whoever creates the map and map be different for each map in the wide Internet. Dave   Received: from PIZZA.BBN.COM by BBN.COM id aa05306; 8 Jul 94 15:11 EDT Received: from pizza by PIZZA.BBN.COM id aa06663; 8 Jul 94 14:55 EDT Received: from KARIBA.BBN.COM by PIZZA.BBN.COM id aa06659; 8 Jul 94 14:52 EDT To: nimrod-wg@BBN.COM Subject: Kissing Amoebas Date: Fri, 08 Jul 94 14:49:31 -0400 From: Isidro Castineyra If arcs have no attributes, you might get away with getting rid-off them completely. Maps would contain only nodes. Nodes would have connectivity specifications as attributes, which indicate the neighboring nodes. Source routes would be lists of connectivity specifications locators (these locators would be prefixed by the locator of the node they belong to). It could be hard to draw, though. Just nodes touching othe nodes. After playing with it a little bit, I think we can call this the "Kissing Amoebas" model (KAM). (Actually Ram just pointed out that we do not need nodes at all. We really only need bundles of connectivity specifications.) I am going to be re-writing the architecture draft during the weekend. I think I will leave vestigial arcs that indicate only which nodes can talk to which nodes. In this model, you will need at most one arc in each direction between any two nodes. I do not think one needs locators for the arcs. Let me know if you have any suggestions. Thanks, Isidro   Received: from PIZZA.BBN.COM by BBN.COM id aa06308; 8 Jul 94 15:27 EDT Received: from pizza by PIZZA.BBN.COM id aa06758; 8 Jul 94 15:07 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa06754; 8 Jul 94 15:04 EDT Received: from clark.net by BBN.COM id aa04891; 8 Jul 94 15:02 EDT Received: (from hcb@localhost) by clark.net (8.6.9/8.6.9) id PAA09100; Fri, 8 Jul 1994 15:02:51 -0400 From: Howard Berkowitz Message-Id: <199407081902.PAA09100@clark.net> Subject: Re: Nodes and Arcs To: Dave Bridgham Date: Fri, 8 Jul 1994 15:02:50 -0400 (EDT) Cc: hcb@clark.net, nimrod-wg@BBN.COM In-Reply-To: <9407081440.aa18446@quern.epilogue.com> from "Dave Bridgham" at Jul 8, 94 02:40:45 pm X-Mailer: ELM [version 2.4 PL23] MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Content-Length: 3073 > > From: Howard Berkowitz > Date: Fri, 8 Jul 1994 14:19:26 -0400 (EDT) > > While they may not contain user endpoints, is it not likely > that the network node, or cluster if you will, will need to > have some sort of identifier for management? Will there not > be an arc from the network node to the SNMPng manager? > > I think I do not understand. When you use SNMP to manage your > ethernet now, don't you connect to some host on that ethernet rather > than the ethernet itself? The endpoint to which you communicate is in > that host, the one running the SNMP agent, not in the ethernet. We may have gotten out of sync on the quoting here. My comment was directed to a statement referring to nodes that never themselves would be a destination (i.e., "network nodes.") I was not referring to the ethernet, but to the network node. Was the previous context referring to a "network node" not as any processing endpoint, but just a graph theory abstraction of a node that connects N other nodes? If so, then where did the arcs go? An intelligent network node, whether an end or an intermediate system, needs to be identified. > > As for an identifier for the network, if all nodes in the graph must > have locators what about the locator? One reason for a separate > identifier space for endpoints is so that when they move they keep > their name. Do we need that also for networks. If a network picks up > and reconnects somewhere else, does it need an identifier that remains > constant so it retrains its identity or is it sufficient that only the > endpoints connected to that network retain their identifiers? > > Again thinking from an operational standpoint, it is a very > useful thing to identify arcs used for specific traffic. > Yes, in principle, they might be identified by their terminating > nodes, but I have a sense that there may be a need for transient > arc identifiers to identify a path between two nodes at a given > point in time, using a particular access subnetwork, etc. > > If arcs don't have attributes then it should be never necessary to > specify in preference to another. Remember, in that case arcs are > only links on a conceptual graph. Anything that mattered would have > attributes and therefore would get a node in the graph. Arcs do not > necessarily map to network connections or any other physical reality. > Obviously there is some physical mapping, but that mapping will be > determined by whoever creates the map and map be different for each > map in the wide Internet. > > Dave > Again, perhaps there is a synchronization issue in the messages here -- are you talking about network nodes only in the context that arcs cannot have attributes, so if I need an attribute, I must have a node to contain it? I'm interpreting arc here in the sense of a potential connectivity relation; some subset of these might be the logical connections.   Received: from PIZZA.BBN.COM by BBN.COM id aa06808; 8 Jul 94 15:35 EDT Received: from pizza by PIZZA.BBN.COM id aa06870; 8 Jul 94 15:19 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa06866; 8 Jul 94 15:16 EDT Received: from clark.net by BBN.COM id aa05409; 8 Jul 94 15:13 EDT Received: (from hcb@localhost) by clark.net (8.6.9/8.6.9) id PAA10575; Fri, 8 Jul 1994 15:13:36 -0400 From: Howard Berkowitz Message-Id: <199407081913.PAA10575@clark.net> Subject: Re: Kissing Amoebas To: Isidro Castineyra Date: Fri, 8 Jul 1994 15:13:35 -0400 (EDT) Cc: nimrod-wg@BBN.COM In-Reply-To: <199407081858.OAA08433@clark.net> from "Isidro Castineyra" at Jul 8, 94 02:49:31 pm X-Mailer: ELM [version 2.4 PL23] MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Content-Length: 1793 > > If arcs have no attributes, you might get away with getting rid-off > them completely. Maps would contain only nodes. Nodes would have > connectivity specifications as attributes, which indicate the > neighboring nodes. Source routes would be lists of connectivity > specifications locators (these locators would be prefixed by the > locator of the node they belong to). > > It could be hard to draw, though. Just nodes touching othe nodes. > After playing with it a little bit, I think we can call this the > "Kissing Amoebas" model (KAM). (Actually Ram just pointed out that we > do not need nodes at all. We really only need bundles of connectivity > specifications.) As a proponent of using more biological models in networking, I think you have hit upon something. Part of the validation of the Kissing Amoeba Model would be to verify that its correctness holds if any of the nodes undergo fission. A related case might be the Conjugating Paramecia Model (CPM), in which the protozoa involved merge into one before fissioning. This has some relationship, although I'm not completely sure what, to validating IPng transition plans and multihoming. There might also be the Cyst Activation/Deactivation model for fault tolerance; it's something like Cisco's Hot Spare Router Protocol. Trying to decide if smileys are or are not relevant, Howard PS--I am not completely joking when I suggest validating potential network relationships against the types of relationships that can (and do) form in biological systems. In trying to predict where the technology and user requirements are going, I would not necessarily stop with addressability for every telephone and thermostat. The elements of distributed neural networks will need addressability.   Received: from PIZZA.BBN.COM by BBN.COM id aa08484; 8 Jul 94 16:01 EDT Received: from pizza by PIZZA.BBN.COM id aa07089; 8 Jul 94 15:44 EDT Received: from BBN.COM by PIZZA.BBN.COM id ab07081; 8 Jul 94 15:42 EDT Received: from nbkanata.Newbridge.COM by BBN.COM id aa07229; 8 Jul 94 15:42 EDT Received: from Newbridge.COM (thor.Newbridge.COM) by nbkanata.newbridge.com (4.1/SMI-4.1) id AA05660; Fri, 8 Jul 94 15:36:59 EDT Received: from mako.newbridge by Newbridge.COM (4.1/SMI-4.0) id AA13772; Fri, 8 Jul 94 15:36:55 EDT Received: from urchin.newbridge by mako.newbridge (4.1/SMI-4.1) id AA10635; Fri, 8 Jul 94 15:36:31 EDT Received: by urchin.newbridge (5.0/SMI-SVR4) id AA00968; Fri, 8 Jul 1994 15:38:51 +0500 Date: Fri, 8 Jul 1994 15:38:51 +0500 From: Joel Halpern Message-Id: <9407081938.AA00968@urchin.newbridge> To: nimrod-wg@BBN.COM Subject: Re: Nodes and Arcs X-Sun-Charset: US-ASCII Content-Length: 980 My initial reaction had been to prefer attribute-less arcs. However, if we assume that things like delay and throughput are improtant, then every "arc" has properties. Therefore, if we go with arcs without attributes, every "arc" consists of two arcs and a node with attributes. (No, the attributes are not distinct from those of a node. An aggregating node may well need the same attributes that a "link-middle" node would need.) While it is true that LANs already have their pseudo-nodes, I would prefer not to require that for ALL links. Note that this applies even in aggregated maps, as the node may still have different attributes in different directions. Thank you, Joel M. Halpern jhalpern@newbridge.com Newbridge Networks Inc. PS To put it another way, "links" have real properties. I tend to associate arcs with "links". One can obviously work around it, but one creates counter-intuitive maps. This stuff is messy enough already, without making it worse.   Received: from PIZZA.BBN.COM by BBN.COM id aa27914; 9 Jul 94 11:26 EDT Received: from pizza by PIZZA.BBN.COM id aa10791; 9 Jul 94 11:14 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa10787; 9 Jul 94 11:12 EDT Received: from vinegar.sesqui.net by BBN.COM id aa27638; 9 Jul 94 11:13 EDT Received: by vinegar.sesqui.net (4.1/SMI-4.1 Jun93 - wcm) id AA00919; Sat, 9 Jul 94 10:13:00 CDT From: William Manning Message-Id: <9407091513.AA00919@vinegar.sesqui.net> Subject: Re: Nodes and Arcs To: Dave Bridgham Date: Sat, 9 Jul 1994 10:12:59 -0500 (CDT) Cc: hcb@clark.net, nimrod-wg@BBN.COM In-Reply-To: <9407081440.aa18446@quern.epilogue.com> from "Dave Bridgham" at Jul 8, 94 02:40:45 pm X-Mailer: ELM [version 2.4 PL22] Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Content-Length: 2149 > As for an identifier for the network, if all nodes in the graph must > have locators what about the locator? One reason for a separate > identifier space for endpoints is so that when they move they keep > their name. Do we need that also for networks. If a network picks up > and reconnects somewhere else, does it need an identifier that remains > constant so it retrains its identity or is it sufficient that only the > endpoints connected to that network retain their identifiers? I thought these "identifiers" were locators and the "network" was simply an arc. When the machines/hosts attach to the "network", they pick up the locator associated w/ that "network" and then the EID+Locator is what gets used. Or am I all wet? > > Again thinking from an operational standpoint, it is a very > useful thing to identify arcs used for specific traffic. > Yes, in principle, they might be identified by their terminating > nodes, but I have a sense that there may be a need for transient > arc identifiers to identify a path between two nodes at a given > point in time, using a particular access subnetwork, etc. > > If arcs don't have attributes then it should be never necessary to > specify in preference to another. Remember, in that case arcs are > only links on a conceptual graph. Anything that mattered would have > attributes and therefore would get a node in the graph. Arcs do not > necessarily map to network connections or any other physical reality. > Obviously there is some physical mapping, but that mapping will be > determined by whoever creates the map and map be different for each > map in the wide Internet. > I get the impression that a common approch will be to map transit vias to arcs. It is then tempting to try and have some way to "tell" hosts (EIDS), the "size" of the transit via. These usually show up as a cost or weight parameter. Unfortunatly, setting these values in no way affects the actual "size" or capacity of the transit via. I think this is an argument for not allowing this particular attribute to be applied to arcs. -bill   Received: from PIZZA.BBN.COM by BBN.COM id aa25584; 12 Jul 94 4:31 EDT Received: from pizza by PIZZA.BBN.COM id aa24254; 12 Jul 94 4:22 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa24250; 12 Jul 94 4:19 EDT Received: from GINGER.LCS.MIT.EDU by BBN.COM id aa23957; 12 Jul 94 4:16 EDT Received: by ginger.lcs.mit.edu id AA23219; Tue, 12 Jul 94 04:16:06 -0400 Date: Tue, 12 Jul 94 04:16:06 -0400 From: Noel Chiappa Message-Id: <9407120816.AA23219@ginger.lcs.mit.edu> To: nimrod-wg@BBN.COM, ramanath@BBN.COM Subject: Re: Nodes and Arcs Cc: jnc@ginger.lcs.mit.edu From: Ram Ramanathan when you have attributes on arcs, the representation has to be an equivalent of a "multigraph" ... whereas in the attributeless-arc model, we can get away with a "normal graph" .... Multigraphs are a pain in the neck and I like the fact that the attributeless-arcs model gets rid of them. Yup. For instance, take BBN, MIT and the microwave link between them. I find it more natural to make BBN a node, MIT a node and the microwave link an arc and assign it attributes ... instead of making a node for the link. I agree. However, perhaps this is a user-interface issue, one we can hide? This kind of thing is part of why I like having "router", "network", etc attributes for nodes; it helps you turn the underlying representation into something that's easier and more natural for humans... Perhaps I am prejudiced by the fact that most work on network modelling as graphs uses edge-weighted graphs. Hmmm. Good point. I have to go think about that... Noel   Received: from PIZZA.BBN.COM by BBN.COM id aa26420; 12 Jul 94 4:42 EDT Received: from pizza by PIZZA.BBN.COM id aa24283; 12 Jul 94 4:24 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa24279; 12 Jul 94 4:23 EDT Received: from GINGER.LCS.MIT.EDU by BBN.COM id aa24645; 12 Jul 94 4:22 EDT Received: by ginger.lcs.mit.edu id AA23286; Tue, 12 Jul 94 04:22:33 -0400 Date: Tue, 12 Jul 94 04:22:33 -0400 From: Noel Chiappa Message-Id: <9407120822.AA23286@ginger.lcs.mit.edu> To: isidro@BBN.COM, nimrod-wg@BBN.COM Subject: Re: Kissing Amoebas Cc: jnc@ginger.lcs.mit.edu From: Isidro Castineyra If arcs have no attributes, you might get away with getting rid-off them completely. Maps would contain only nodes. Nodes would have connectivity specifications as attributes, which indicate the neighboring nodes. Perhaps I'm confused, but these "[indications of] neighbouring nodes" to me seem totally isomorphic to attribute-less connectivity arcs... I would imagine that in fact that's how they are *represented* when we ship the data around. I.e. a node lists the names of the nodes it is connected to. It's all the same, no? It's just that one's a picture, and one's bits. I think I will leave vestigial arcs that indicate only which nodes can talk to which nodes. Yup; that's easy to visualize. In this model, you will need at most one arc in each direction between any two nodes. Hmm. So this means that unidirectional physical links are shown by nodes which indicate connectivity in one direction, but not the other? I have to think about that... I do not think one needs locators for the arcs. Right. Since there's at most one between any pair of nodes, listing a node sequence specifies a unique path. Noel   Received: from PIZZA.BBN.COM by BBN.COM id aa11242; 12 Jul 94 9:45 EDT Received: from pizza by PIZZA.BBN.COM id aa25413; 12 Jul 94 9:32 EDT Received: from KARIBA.BBN.COM by PIZZA.BBN.COM id aa25409; 12 Jul 94 9:30 EDT To: Noel Chiappa cc: nimrod-wg@BBN.COM Subject: Re: Kissing Amoebas In-reply-to: Your message of Tue, 12 Jul 94 04:22:33 -0400. <9407120822.AA23286@ginger.lcs.mit.edu> Date: Tue, 12 Jul 94 09:27:30 -0400 From: Isidro Castineyra >> >> In this model, you will need at most one arc in each direction >> between any two nodes. >> >>Hmm. So this means that unidirectional physical links are shown by >>nodes which indicate connectivity in one direction, but not the >>other? I have to think about that... >> Unidirectional physical links would be shown by a combination of two unidirectional, attributeless arcs and a node: arc->node->arc the node holds the properties of the physical unidirectional link. This model is a consequence of arcs having no attributes. Isidro   Received: from PIZZA.BBN.COM by BBN.COM id aa22440; 12 Jul 94 12:22 EDT Received: from pizza by PIZZA.BBN.COM id aa26339; 12 Jul 94 12:09 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa26335; 12 Jul 94 12:05 EDT Received: from GINGER.LCS.MIT.EDU by BBN.COM id aa21392; 12 Jul 94 12:06 EDT Received: by ginger.lcs.mit.edu id AA25010; Tue, 12 Jul 94 12:06:17 -0400 Date: Tue, 12 Jul 94 12:06:17 -0400 From: Noel Chiappa Message-Id: <9407121606.AA25010@ginger.lcs.mit.edu> To: isidro@BBN.COM, jnc@ginger.lcs.mit.edu Subject: Re: Kissing Amoebas Cc: jnc@ginger.lcs.mit.edu, nimrod-wg@BBN.COM From: Isidro Castineyra Unidirectional physical links would be shown by a combination of two unidirectional, attributeless arcs and a node: arc->node->arc Ah, sorry, I was up too late reading mail; my brain wasn't functioning! Yes, this makes perfect sense. Are all our arcs unidirectional? This is fine with me. If you think about the data structure, you'd have to have a pointer in each node *anyway* for a birectional arc (so you can traverse it from either end), so the bits in memory look the same for i) two unidirectional arcs, or ii) a bi-directional arc. Having unidirectional arc just means it's legal to have a pointer in one direction, and nothing in the other. And once you've got unidirectional arcs, adding bidrectional arcs just makes things more complex (2 kinds of arc), and doesn't buy you anything (no space savings, etc). We might want to allow bidirectional arcs in the user interface, to avoid lots of ugly double arcs in the visual representation, but the underlying model can just have unidirectional. Noel   Received: from PIZZA.BBN.COM by BBN.COM id aa25145; 12 Jul 94 13:04 EDT Received: from pizza by PIZZA.BBN.COM id aa26595; 12 Jul 94 12:46 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa26591; 12 Jul 94 12:44 EDT Received: from databus.databus.com by BBN.COM id aa23855; 12 Jul 94 12:44 EDT Date: Tue, 12 Jul 94 12:46 EDT Message-ID: <9407121246.AA05678@databus.databus.com> From: Barney Wolff To: Noel Chiappa , isidro@BBN.COM Cc: nimrod-wg@BBN.COM Subject: Re: Kissing Amoebas Content-Length: 488 Content-Type: text > Date: Tue, 12 Jul 94 12:06:17 -0400 > From: Noel Chiappa > > ... Having unidirectional arc just means it's legal to have a pointer in one > direction, and nothing in the other. I suspect that the representation has to include "come-from" as well as "goto" information, whether the arc is uni- or bi-directional, because, as any maze addict knows, it's often easier to find the optimal route backwards from the destination. Barney Wolff   Received: from PIZZA.BBN.COM by BBN.COM id aa28556; 12 Jul 94 13:54 EDT Received: from pizza by PIZZA.BBN.COM id aa26951; 12 Jul 94 13:40 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa26947; 12 Jul 94 13:38 EDT Received: from GINGER.LCS.MIT.EDU by BBN.COM id aa27421; 12 Jul 94 13:37 EDT Received: by ginger.lcs.mit.edu id AA25542; Tue, 12 Jul 94 13:37:27 -0400 Date: Tue, 12 Jul 94 13:37:27 -0400 From: Noel Chiappa Message-Id: <9407121737.AA25542@ginger.lcs.mit.edu> To: barney@databus.com, jnc@ginger.lcs.mit.edu Subject: Re: Kissing Amoebas Cc: jnc@ginger.lcs.mit.edu, nimrod-wg@BBN.COM I suspect that the representation has to include "come-from" as well as "goto" information, whether the arc is uni- or bi-directional, because, as any maze addict knows, it's often easier to find the optimal route backwards from the destination. Oops, good point. So, in addition to the link, there's a bit for each direction which says whether or not traffic goes that way. Noel   Received: from PIZZA.BBN.COM by BBN.COM id aa02350; 12 Jul 94 14:43 EDT Received: from pizza by PIZZA.BBN.COM id aa27317; 12 Jul 94 14:24 EDT Received: from KARIBA.BBN.COM by PIZZA.BBN.COM id aa27313; 12 Jul 94 14:22 EDT To: Barney Wolff cc: Noel Chiappa , nimrod-wg@BBN.COM Subject: Re: Kissing Amoebas In-reply-to: Your message of Tue, 12 Jul 94 12:46:00 -0400. <9407121246.AA05678@databus.databus.com> Date: Tue, 12 Jul 94 14:18:41 -0400 From: Isidro Castineyra Noel, Barney, >>> Date: Tue, 12 Jul 94 12:06:17 -0400 >>> From: Noel Chiappa >>> >>> ... Having unidirectional arc just means it's legal to have a pointer in one >>> direction, and nothing in the other. >> >>I suspect that the representation has to include "come-from" as well as >>"goto" information, whether the arc is uni- or bi-directional, because, >>as any maze addict knows, it's often easier to find the optimal route >>backwards from the destination. >> This is a direction that worries me. I worry when implementation details want to start dictating the architecture. It is certainly true that we better have an architecture that can be implemented reasonably easily. But when, at this stage, people start talking pointers in the data structures I get the willies. Isidro   Received: from PIZZA.BBN.COM by BBN.COM id aa20364; 12 Jul 94 18:17 EDT Received: from pizza by PIZZA.BBN.COM id aa29047; 12 Jul 94 18:07 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa29043; 12 Jul 94 18:01 EDT Received: from databus.databus.com by BBN.COM id aa17828; 12 Jul 94 17:56 EDT Date: Tue, 12 Jul 94 17:58 EDT Message-ID: <9407121758.AA06650@databus.databus.com> From: Barney Wolff To: Isidro Castineyra , Barney Wolff Cc: Noel Chiappa , nimrod-wg@BBN.COM Subject: Re: Kissing Amoebas Content-Length: 758 Content-Type: text > Date: Tue, 12 Jul 94 14:18:41 -0400 > From: Isidro Castineyra > > This is a direction that worries me. I worry when implementation > details want to start dictating the architecture. It is certainly true > that we better have an architecture that can be implemented reasonably > easily. But when, at this stage, people start talking pointers in the > data structures I get the willies. While the tension between architects and builders will always be present, I would claim that it avoids a certain OSIsm to give occasional thought to instantiation. In the current case, the notion that a node should "know" which arcs come into it as well as which leave it is architecturally sound as well, imho. Barney Wolff   Received: from PIZZA.BBN.COM by BBN.COM id aa02034; 13 Jul 94 16:58 EDT Received: from pizza by PIZZA.BBN.COM id aa05392; 13 Jul 94 16:38 EDT Received: from KARIBA.BBN.COM by PIZZA.BBN.COM id aa05388; 13 Jul 94 16:35 EDT To: nimrod-wg@BBN.COM Subject: New Version of Nimrod Architecture Draft (attributeless arcs) Date: Wed, 13 Jul 94 16:32:29 -0400 From: Isidro Castineyra A new version of the Nimrod Architecture is on host bbn.com in file /pub/nimrod-wg/architecture.draft This version differs from the previous one in that arcs have no attributes. Isidro Isidro Castineyra (isidro@bbn.com) Bolt Beranek and Newman, Incorporated (617) 873-6233 10 Moulton Street, Cambridge, MA 02138 USA   Received: from PIZZA.BBN.COM by BBN.COM id aa07432; 18 Jul 94 12:41 EDT Received: from pizza by PIZZA.BBN.COM id aa06578; 18 Jul 94 12:11 EDT Received: from KARIBA.BBN.COM by PIZZA.BBN.COM id aa06573; 18 Jul 94 12:08 EDT To: nimrod-wg@BBN.COM Subject: documents Date: Mon, 18 Jul 94 12:09:27 -0400 From: Martha Steenstrup Hello, We are in the process of issuing a set of Nimrod documents as Internet Drafts. As Nimrod is not yet an official Working Group, none of these documents may carry a header containing the words Nimrod Working Group. Rumor has it that Working Group status is imminent. WHen this happens, we will reissue these drafts as documents of the Nimrod Working Group.   Received: from PIZZA.BBN.COM by BBN.COM id aa15775; 19 Jul 94 17:31 EDT Received: from pizza by PIZZA.BBN.COM id aa18868; 19 Jul 94 16:46 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa18864; 19 Jul 94 16:42 EDT Received: from ginger.lcs.mit.edu by BBN.COM id aa12897; 19 Jul 94 16:39 EDT Received: by ginger.lcs.mit.edu id AA13312; Tue, 19 Jul 94 16:38:56 -0400 Date: Tue, 19 Jul 94 16:38:56 -0400 From: Noel Chiappa Message-Id: <9407192038.AA13312@ginger.lcs.mit.edu> To: nimrod-wg@BBN.COM Subject: Updated Nimrod IPNG Rqmts doc Cc: jnc@ginger.lcs.mit.edu, mankin@hsdndev.harvard.edu, sob@harvard.edu I have finally succeeded in finding the time to update the Nimrod IPng requirements document. There are two main areas of change: i) the flow-identification bullet has been updated to include the potential requirement for aggregating flows, and the implications thereof, and ii) and the endpoint identification bullet has been updated to include the results of some of the recent discussion on Big-I. I have put it into I-D form (roughly), and am going to submit it "soon". So, if you want to comment *before* that happens, do so "soon". Also, it's still mostly in first-person, since i) I don't have the energy to change that, and ii) I didn't want to represent this as being an agreed upon WG view. Some people have reviewed earlier versions (for which I thank them, particularly the people at BBN who did a great job on early ones), but these later versions haven't been much reviewed. So. Anyway, there is is. It's in ipng_req.txt on research.ftp.com, in the Nimrod repository (pub/nimrod). Noel   Received: from PIZZA.BBN.COM by BBN.COM id aa16905; 21 Jul 94 13:11 EDT Received: from pizza by PIZZA.BBN.COM id aa05382; 21 Jul 94 12:54 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa05378; 21 Jul 94 12:51 EDT Received: from ginger.lcs.mit.edu by BBN.COM id aa15603; 21 Jul 94 12:50 EDT Received: by ginger.lcs.mit.edu id AA27759; Thu, 21 Jul 94 12:50:33 -0400 Date: Thu, 21 Jul 94 12:50:33 -0400 From: Noel Chiappa Message-Id: <9407211650.AA27759@ginger.lcs.mit.edu> To: nimrod-wg@BBN.COM Subject: IPng requirements Cc: jnc@ginger.lcs.mit.edu Having heard nothing, in it goes as an I-D. NOel   Received: from PIZZA.BBN.COM by BBN.COM id aa28013; 22 Jul 94 13:34 EDT Received: from pizza by PIZZA.BBN.COM id aa14754; 22 Jul 94 13:21 EDT Received: from BBN.COM by PIZZA.BBN.COM id ab14746; 22 Jul 94 13:17 EDT Received: from ginger.lcs.mit.edu by BBN.COM id aa27002; 22 Jul 94 13:14 EDT Received: by ginger.lcs.mit.edu id AA10827; Fri, 22 Jul 94 13:14:51 -0400 Date: Fri, 22 Jul 94 13:14:51 -0400 From: Noel Chiappa Message-Id: <9407221714.AA10827@ginger.lcs.mit.edu> To: nimrod-wg@BBN.COM Subject: Re: Nimrod and other flow-based systems Cc: jnc@ginger.lcs.mit.edu To restate the obvious, Nimrod has three main subsystems; viz. i) the map description and distribution, ii) the path selection (not that the details of path selection are part of Nimrod, other an providing some sample algorithms for this local issue, but having a separate path selection module is part of the overall architecture), and iii) the forwarding and flow setup. One comment I have about the recent documents, in reaction to other goings-on in the IETF, is to think that we should make sure that the clear separation of the three main subsystems of Nimrod is such as to admit eventual replacement of the mechanisms in the latter group, i.e. flow setup. I expect that the Nimrod mechanisms to do flow setup may be temporary, and will be replaced later on by a generic flow-setup which handles flow setup for a number of subsystems. For instance, RSVP is, when you look at it, basically an a protocol for installing flow-like state (albeit one which seems to be oriented toward setting up resource reservation state, and in a fairly routing-table oriented view of the world, although perhaps Lixia, Bob et al may feel that that characterization is lacking in understanding). It seems rather unneeded to have two separate flow-setup protocols, or rather N, one for each subsystem which wants to install state (accounting, access control, etc...) Should the flows vision of the world prove sucessful, we might want to replace all these separate flow-setup mechanisms with a single one. (I can see the value to having multiple ones for now, to allow experimentation.) Should Nimrod prove sucessful, we thus might wind up discarding the Nimrod flow-setup protocol, which is why I think we should get into the habit now of viewing it as less central and permanent than say, the map distribution part of the design. And no, I wouldn't like to try and make Nimrod flow-setup that generic, not without a lot of help from others, although I suppose it's possible. In fact, it may not be bad to experiment with yet another flow- setup protocol local to the Nimrod context, to better understand the needs of routing on such a setup protocol, before trying to do a generic flow-setup protocol. Noel   Received: from PIZZA.BBN.COM by BBN.COM id aa00447; 2 Aug 94 6:08 EDT Received: from pizza by PIZZA.BBN.COM id aa16573; 2 Aug 94 5:54 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa16567; 2 Aug 94 5:51 EDT Received: from cphkvx.cphk.hk by BBN.COM id aa02478; 2 Aug 94 5:41 EDT Received: from cphkvx.cphk.hk by cphkvx.cphk.hk (PMDF V4.2-14 #5105) id <01HFFXHCLG928ZDWBL@cphkvx.cphk.hk>; Tue, 2 Aug 1994 17:42:29 +0800 Date: Tue, 02 Aug 1994 17:42:29 +0800 From: EEACHENG@cphkvx.cphk.hk Subject: what-is-nimrod To: nimrod-wg@BBN.COM Message-id: <01HFFXHCLG948ZDWBL@cphkvx.cphk.hk> Organization: City Polytechnic of Hong Kong X-VMS-To: IN%"nimrod-wg@bbn.com" MIME-version: 1.0 Content-type: TEXT/PLAIN; CHARSET=US-ASCII Content-transfer-encoding: 7BIT Hi, would you please tell me the full name of nimrod? Since Nimrod is a working group, what is the working group doing? Thanks. Best regards, Tony Cheng (City Polytechnic of Hong Kong, Electronic Engineering Dept.)   Received: from PIZZA.BBN.COM by BBN.COM id aa29873; 3 Aug 94 7:00 EDT Received: from pizza by PIZZA.BBN.COM id aa22761; 3 Aug 94 6:51 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa22757; 3 Aug 94 6:48 EDT Received: from ginger.lcs.mit.edu by BBN.COM id aa29488; 3 Aug 94 6:45 EDT Received: by ginger.lcs.mit.edu id AA24171; Wed, 3 Aug 94 06:44:48 -0400 Date: Wed, 3 Aug 94 06:44:48 -0400 From: Noel Chiappa Message-Id: <9408031044.AA24171@ginger.lcs.mit.edu> To: EEACHENG@cphkvx.cphk.hk, nimrod-wg@BBN.COM Subject: Re: what-is-nimrod Cc: jnc@ginger.lcs.mit.edu Hi, would you please tell me the full name of nimrod? The name is not an acronym; it's a very complicated joke involving the Nimrod Moving+Storage Company.. Since Nimrod is a working group, what is the working group doing? I am informed that our WG charter has finally been OK'd, so we'll be official soon. (I'll send you a copy offline...) We're working on an advanced routing and adresing architecture, to be brief... Noel   Received: from PIZZA.BBN.COM by BBN.COM id aa25487; 4 Aug 94 5:17 EDT Received: from pizza by PIZZA.BBN.COM id aa29023; 4 Aug 94 5:08 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa29019; 4 Aug 94 5:06 EDT Received: from cphkvx.cphk.hk by BBN.COM id aa25016; 4 Aug 94 4:59 EDT Received: from cphkvx.cphk.hk by cphkvx.cphk.hk (PMDF V4.2-14 #5105) id <01HFIOH4298W8ZDXJP@cphkvx.cphk.hk>; Thu, 4 Aug 1994 17:00:26 +0800 Date: Thu, 04 Aug 1994 17:00:26 +0800 From: EEACHENG@cphkvx.cphk.hk Subject: mobile-computers To: nimrod-wg@BBN.COM Message-id: <01HFIOH43BTU8ZDXJP@cphkvx.cphk.hk> Organization: City Polytechnic of Hong Kong X-VMS-To: IN%"nimrod-wg@bbn.com" MIME-version: 1.0 Content-type: TEXT/PLAIN; CHARSET=US-ASCII Content-transfer-encoding: 7BIT Hi, I have found a file on bbn.com:/pub/nimrod-wg/ called /mobility.txt and I believe the file is talking about how to implement a protocol for mobile networks. Am I right? If the network is mobile, what kind of frequencies will be used for the mobile hosts or computers? Is the word "mobile" in this file means wireless? Please excluse my ignorance. Thanks. Tony Cheng   Received: from PIZZA.BBN.COM by BBN.COM id aa06407; 4 Aug 94 9:56 EDT Received: from pizza by PIZZA.BBN.COM id aa29983; 4 Aug 94 9:36 EDT Received: from TTL.BBN.COM by PIZZA.BBN.COM id aa29979; 4 Aug 94 9:33 EDT To: EEACHENG@cphkvx.cphk.hk cc: nimrod-wg@BBN.COM Subject: Re: mobile-computers In-reply-to: Your message of Thu, 04 Aug 94 17:00:26 +0800. <01HFIOH43BTU8ZDXJP@cphkvx.cphk.hk> Date: Thu, 04 Aug 94 09:29:08 -0400 From: Ram Ramanathan > Date: Thu, 04 Aug 1994 17:00:26 +0800 > From: EEACHENG@cphkvx.cphk.hk > Subject: mobile-computers > To: nimrod-wg@BBN.COM > Message-id: <01HFIOH43BTU8ZDXJP@cphkvx.cphk.hk> > Organization: City Polytechnic of Hong Kong > X-VMS-To: IN%"nimrod-wg@bbn.com" > MIME-version: 1.0 > Content-type: TEXT/PLAIN; CHARSET=US-ASCII > Content-transfer-encoding: 7BIT > > Hi, I have found a file on bbn.com:/pub/nimrod-wg/ called /mobility.txt > and I believe the file is talking about how to implement a protocol for > mobile networks. Am I right? If the network is mobile, what kind of > frequencies will be used for the mobile hosts or computers? Is the word > "mobile" in this file means wireless? Please excluse my ignorance. > > Thanks. > > Tony Cheng Tony, The file /pub/nimrod-wg/mobility.txt contains a discussion on how we are currently looking at the problem of mobility in Nimrod. Nimrod is a routing and addressing architecture and is not oblivious to mobility. However, Nimrod does not specify a *particular* mobility solution. In the document "mobility.txt", we have given the requirements that Nimrod has of a mobility solution and discussed possible approaches. There is an example of how we can adapt the protocol developed by the Mobile-IP working group of the IETF in Nimrod. You should not read that as a protocol specification though. The word "mobile" refers not only to wireless equipped terminals but also, for instance, when you take your portable laptop, disconnect it from one interface and connect it to another. Since Nimrod is a routing and addressing architecture, we don't worry about what frequencies are used, what channel access scheme is used etc. All that is a huge research topic by itself. The question that Nimrod is trying to address wrt mobility is : If a machine moves, how do I efficiently "track" it, and how to I route packets to it? I hope I have made things a little clearer. I suggest you read the document for further information. -Ram. -------------------------------------------------------------- Ram Ramanathan Advanced Networking R & D BBN Systems and Technologies 10 Moulton Street, Cambridge, MA 02138 Phone : (617) 873-2736 INTERNET : ramanath@bbn.com   Received: from PIZZA.BBN.COM by BBN.COM id aa08146; 4 Aug 94 10:24 EDT Received: from pizza by PIZZA.BBN.COM id aa00385; 4 Aug 94 10:13 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa00381; 4 Aug 94 10:08 EDT Received: from tieo.SAIC.COM by BBN.COM id aa06823; 4 Aug 94 10:03 EDT Received: by tieo.saic.com (4.1/1.34) id AA00745; Thu, 4 Aug 94 10:04:02 EDT Date: Thu, 4 Aug 94 10:04:02 EDT From: Kenneth Carlberg Message-Id: <9408041404.AA00745@tieo.saic.com> To: ramanath@BBN.COM Subject: Re: mobile-computers Cc: nimrod-wg@BBN.COM Ram, > The question that Nimrod is trying to address wrt mobility > is : If a machine moves, how do I efficiently "track" it, and how to > I route packets to it? Just to be a little more concise, I assume you mean "tracking" in regards to movement at the internetwork layer -- or rather when the machine moves from one network to another. Movement *within* a subnetwork (such as within the same ethernet or cellular/packet radio network) is not within the scope of Nimrod. -ken   Received: from PIZZA.BBN.COM by BBN.COM id aa17885; 4 Aug 94 13:00 EDT Received: from pizza by PIZZA.BBN.COM id aa01429; 4 Aug 94 12:41 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa01425; 4 Aug 94 12:39 EDT Received: from ginger.lcs.mit.edu by BBN.COM id aa16584; 4 Aug 94 12:37 EDT Received: by ginger.lcs.mit.edu id AA00998; Thu, 4 Aug 94 12:37:34 -0400 Date: Thu, 4 Aug 94 12:37:34 -0400 From: Noel Chiappa Message-Id: <9408041637.AA00998@ginger.lcs.mit.edu> To: carlberg@tieo.saic.com, ramanath@BBN.COM Subject: Re: mobile-computers Cc: jnc@ginger.lcs.mit.edu, nimrod-wg@BBN.COM From: Kenneth Carlberg I assume you mean "tracking" in regards to movement at the internetwork layer ... Movement *within* a subnetwork (such as within the same ethernet or cellular/packet radio network) is not within the scope of Nimrod. Yes and no. I'm interested in building an internetwork-level routing architecture, and not trying to take over cellular routing or ATM routing, but.. I have this theory that routing is a function which ought not to be split up, but should remain a unified whole. You may have areas of the mesh which, for various reasons, want to be more insulated from what's going on outside, or want to use a routing system which has different operational characteristics (because of a peculiar operating mode for that part of the mesh). However, I think taking that insulation to the point of doing a whole separate routing architecture, at a separate layer, inside them is harmful in the long run. By building such a hard wall between them you make it much harder to exchange information *should that become useful*. If you instead work within a unified framework, you have the easy option of tuning the amount of information excahnge across the barrier to achieve whatever routing goals you have. I'm much influenced in this thinking by having worked with the separate routing in the ARPAnet back in the late 70's, where the hard barrier between that and internetwork level routing made certain desirable things impossible. The implications of this for things like ATM are obvious. I'm not against ATM as a technology, but I think the attempt to make the ATM substrate a fully functional layer is a bit misguided, since we're replicating functionality that has to be present at the internetwork layer anyway. Of course, if ATM becomes the ubiquitous internetwork layer, that would be OK. However, let's not get into *that* rathole! Noel   Received: from PIZZA.BBN.COM by BBN.COM id aa00733; 12 Aug 94 16:32 EDT Received: from pizza by PIZZA.BBN.COM id aa24263; 12 Aug 94 16:18 EDT Received: from KARIBA.BBN.COM by PIZZA.BBN.COM id aa24259; 12 Aug 94 16:13 EDT To: minutes@cnri.reston.va.us cc: nimrod-wg@BBN.COM Subject: Nimrod BOF Minutes Date: Fri, 12 Aug 94 16:14:35 -0400 From: Isidro Castineyra IETF30 (Toronto) Meeting Proceedings Routing Area Nimrod BOF Current Meeting Report Reported by: Isidro Castineyra Minutes of The New Internet Routing And Addressing Architecture BOF (NIMROD) The objective of this BOF is to design NIMROD: a hierarchical, map-based, routing architecture. Nimrod's stated purpose is to manage in a scalable fashion the trade-off between amount of information about the network and route quality. Four documents were distributed to the group before this meeting: 1. A new Architecture Draft 2. A description of Nimrod's functionality 3. A description of Nimrod's approach to mobility, and 4. A description of Nimrod's approach to multicast. (They can be found in host bbn.com in directory /pub/nimrod-wg.) The main purpose of the meeting was to briefly present and review these documents. I. Architecture Draft Isidro Castineyra reported on the new Architecture Draft. The main differences between this draft and the previous one are two: first, arcs are always unidirectional; second, arcs have no attributes. These two points have as consequence that, between two given nodes, there can be only one arc in each direction, and that arcs always connect different nodes. The current Architecture Draft assigns locators to arcs. The question was raised if this was necessary, as an arc can now be identified by the locators of the two nodes it connects. The current draft also differs from the previous one in how connectivity through a node is represented. The draft specifies a "transit connectivity" attribute that consists of a list of connectivity specifications. Each connectivity specification qualified by a list of the neighboring nodes between which it is valid. This was thought to be too complex. An alternate representation was suggested: associate with each note one (or several) connectivity specifications which are valid between all neighboring nodes. More complex transit connectivity specifications would be represented by an "abstract" internal map. II. Nimrod Functionality Martha Steenstrup reported on the functionality document. This documents presents an overview of the routing functionality implied by the Nimrod routing architecture. The document presents a candidate set of routing mechanisms for Nimrod, illustrating how the Nimrod architecture might be realized. It is intended as a stepping stone on the way to a detailed protocol specification for Nimrod. Questions during this presentation were for clarification. III, IV Mobility and Multicas in Nimrod Ram Ramanathan presented the documents on mobility and multicast. Neither of these documents presents a specific Nimrod approach. They show how different approaches, including those currently being considered in the IETF WGs on mobility and multicast, can be co-opted by Nimrod. Questions during his presentation were for clarification. The next topic was how to approach the protocol and database specification. Ram Ramanathan made a brief presentation on what protocol mechanism would be necessary. I. Castineyra touched briefly on the database organization. A suggestion to use a mib-like approach was discussed. The group suggested looking at alternatives. Noel Chiappa made a brief presentation on his document on Nimrod requirements for IPng. Workplan: work on protocol an database specification with the objective to produce IDs on these subjects.   Received: from PIZZA.BBN.COM by BBN.COM id aa10585; 15 Aug 94 15:27 EDT Received: from pizza by PIZZA.BBN.COM id aa11788; 15 Aug 94 15:12 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa11783; 15 Aug 94 15:09 EDT Received: from wd40.ftp.com by BBN.COM id aa08774; 15 Aug 94 15:03 EDT Received: from ftp.com by ftp.com ; Mon, 15 Aug 1994 15:03:38 -0400 Received: from mailserv-D.ftp.com by ftp.com ; Mon, 15 Aug 1994 15:03:38 -0400 Received: by mailserv-D.ftp.com (5.0/SMI-SVR4) id AA18865; Mon, 15 Aug 94 15:01:07 EDT Date: Mon, 15 Aug 94 15:01:07 EDT Message-Id: <9408151901.AA18865@mailserv-D.ftp.com> To: nimrod-wg@BBN.COM Subject: [Forwarded: WG ACTION: New Internet Routing and Addressing Architecture (nimrod)] From: Frank Kastenholz Reply-To: kasten@ftp.com Content-Length: 405 This just came out in ietf-announce... crazy frank ===================================================================== A new working group has been created in the Routing Area of the IETF. Please contact the chairs or area director for more information. IESG Secretary New Internet Routing and Addressing Architecture (nimrod) --------------------------------------------------------- etc.....   Received: from PIZZA.BBN.COM by BBN.COM id aa26355; 10 Oct 94 16:15 EDT Received: from pizza by PIZZA.BBN.COM id aa11864; 10 Oct 94 15:52 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa11860; 10 Oct 94 15:49 EDT Received: from nbkanata.Newbridge.COM by BBN.COM id aa25611; 10 Oct 94 15:49 EDT Received: from Newbridge.COM ([138.120.100.14]) by nbkanata.Newbridge.COM (4.1/SMI-4.1) id AA12502; Mon, 10 Oct 94 15:43:52 EDT Received: from mako.newbridge by Newbridge.COM (4.1/SMI-4.0) id AA28570; Mon, 10 Oct 94 15:43:53 EDT Received: from lobster.Newbridge.COM by mako.newbridge (4.1/SMI-4.1) id AA06968; Mon, 10 Oct 94 15:49:48 EDT Received: by lobster.Newbridge.COM (5.0/SMI-SVR4) id AA01017; Mon, 10 Oct 1994 15:49:56 +0500 Date: Mon, 10 Oct 1994 15:49:56 +0500 From: Joel Halpern Message-Id: <9410101949.AA01017@lobster.Newbridge.COM> To: nimrod-wg@BBN.COM Subject: Complexity X-Sun-Charset: US-ASCII Content-Length: 1255 At the last IETF I listened to the presentation from Martha and other implementors within BBN working on Nimrod (my apologies for forgetting names). At the time I had some difficulty following all of the decisions. (And that is my problem, not the groups.) However, one aspect seemed clear to me. For reasons of generality, the design allowed for separating each of the components of the system from all other components. It seems to me that while this is necessary in the long run, in the short run it complicates life significantly. One needs protocol mechanisms for each piece to talk to each other pieces. It was not obvious to me that the "same" protocol would work for all pieces. I would like to suggest that we discuss this decomposition a bit with the goal of either: 1) Determining that only one protocol is needed, and therefore elementary decomposition is a good thing, or 2) That different protocols could be needed. If we conclude that different protocols could be needed, I would further suggest that the goal of implementable specifications for trial would indicate that such decomposition should be deferred while we find out how this thing works. Comments? Joel M. Halpern jhalpern@newbridge.com Newbridge Networks Inc.   Received: from PIZZA.BBN.COM by BBN.COM id aa23725; 11 Oct 94 18:16 EDT Received: from pizza by PIZZA.BBN.COM id aa19114; 11 Oct 94 17:59 EDT Received: from KARIBA.BBN.COM by PIZZA.BBN.COM id aa19110; 11 Oct 94 17:55 EDT To: jhalpern@newbridge.com cc: nimrod-wg@BBN.COM Subject: nimrod protocols Date: Tue, 11 Oct 94 17:56:51 -0400 From: Martha Steenstrup Hi Joel, As input to your discussion of Nimrod protocols, here is an offering from the perspective of the guys in the trenches at BBN. We would like each of the Nimrod protocols to be simple, and yet we would like there to be a small number of Nimrod protocols. This will make the implementation of Nimrod protocols quick and straightforward. As you mention, we definitely do not want to "shoe horn" diverse functionality into a single protocol. However, if practical, a single protocol should be able to handle more than one type of Nimrod routing information (e.g., maps and endpoint/locator assocations). Before the July IETF, we did some thinking about what the Nimrod protocols might look like. At the July IETF, we talked a little about these protocols, and as we hoped, that discussion has now provoked a discussion on this mailing list. As discussed at the last IETF, we've tentatively selected the following protocols for Nimrod: 1. Hierarchical update. This protocol will take care of automatic distribution of both maps and endpoint/locator associations. It is a form of flooding, limited to a particular portion of the clustering hierarchy. 2. Query/response. This protocol will be used both to obtain more detailed maps of a given node and to determine the locators for a particular endpoint. 3. Path setup. This protocol will be used to install packet forwarding information in routers, for both flow mode and datagram mode packet transport. 4. Discovery. These are the Nimrod bootstrapping mechanisms, including neighbor discovery as well as agent discovery. We have also thought about spreading this functionality between hierarchical update and query/response, instead of having a separate discovery protocol, because it could fit within these protocols. However, we also thought this might significantly complicate these protocols, and for now we have decided to keep the discovery mechanisms separate. 5. Reliable transport. This protocol will be used to carry all Nimrod control packets (such as maps and path setup information). It will include retransmission of packets perceived not to have been received successfully, integrity checking of packet contents, and authentication of packet sender. We may use functionality similar to that in the Control Message Transport Protocol (used to transmit IDPR control messages). Ram Ramanathan has done a lot of thinking about these candidate Nimrod protocols, particularly how they can be cast as finite state machines. I suspect that Ram will send a separate message about this in response to your message. His characterization of the proposed Nimrod protocols makes them appear pretty easy to fathom, which is definitely good news. I definitely agree that we will learn a lot about how these things behave during the initial implementation, and that the implementation may suggest several changes to these protocols or even changes to the decomposition of the Nimrod functionality into a set of protocols. m   Received: from PIZZA.BBN.COM by BBN.COM id aa24946; 11 Oct 94 18:50 EDT Received: from pizza by PIZZA.BBN.COM id aa19304; 11 Oct 94 18:34 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa19300; 11 Oct 94 18:32 EDT Received: from nbkanata.Newbridge.COM by BBN.COM id aa24368; 11 Oct 94 18:33 EDT Received: from Newbridge.COM ([138.120.100.14]) by nbkanata.Newbridge.COM (4.1/SMI-4.1) id AA17007; Tue, 11 Oct 94 18:28:08 EDT Received: from mako.newbridge by Newbridge.COM (4.1/SMI-4.0) id AA18476; Tue, 11 Oct 94 18:28:07 EDT Received: from lobster.Newbridge.COM by mako.newbridge (4.1/SMI-4.1) id AA14654; Tue, 11 Oct 94 18:34:01 EDT Received: by lobster.Newbridge.COM (5.0/SMI-SVR4) id AA01309; Tue, 11 Oct 1994 18:34:10 +0500 Date: Tue, 11 Oct 1994 18:34:10 +0500 From: Joel Halpern Message-Id: <9410112234.AA01309@lobster.Newbridge.COM> To: nimrod-wg@BBN.COM Subject: Re: nimrod protocols X-Sun-Charset: US-ASCII Content-Length: 1294 Martha's list of protocol components cleared up some of my remaining confusion from the July meeting. It is certainly hard to argue that any of those are not needed or could be eliminated by combining machinery. However, I have a couple of questions for clarification: 1) The description indicates that Hierarchcial update distributes maps and endpoint/locator associations. Then the Query/response says that it is used for both fetching more detailed maps, and for determining locators for an endpoint. If this is a different binding than that distributed by the hierarchical update process, what binding is it, and when is it used. (I think that these are actually two different findings, but...) 2) It would seem likely that we could prototype this without ever looking inside a map. This is particularly useful since the conditions under which one would look inside a map are ill-defined. Hence leaving that till later might help. (This is not that much help if we also need the query/response protocol for binding resolution.) 3) Why is Path setup needed for datagram mode? Is this intended to be a function performed by a group controller for a map section? Thank you, Joel M. Halpern jhalpern@newbridge.com Newbridge Networks Inc.   Received: from PIZZA.BBN.COM by BBN.COM id aa28223; 11 Oct 94 20:35 EDT Received: from pizza by PIZZA.BBN.COM id aa19893; 11 Oct 94 20:19 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa19889; 11 Oct 94 20:16 EDT Received: from quern.epilogue.com by BBN.COM id aa27694; 11 Oct 94 20:17 EDT From: Dave Bridgham Sender: dab@epilogue.com To: nimrod-wg@BBN.COM In-reply-to: Martha Steenstrup's message of Tue, 11 Oct 94 17:56:51 -0400 <9410111811.aa27145@quern.epilogue.com> Subject: nimrod protocols Date: Tue, 11 Oct 94 20:17:06 -0400 Message-ID: <9410112017.aa27483@quern.epilogue.com> Date: Tue, 11 Oct 94 17:56:51 -0400 From: Martha Steenstrup 5. Reliable transport. This protocol will be used to carry all Nimrod control packets (such as maps and path setup information). It will include retransmission of packets perceived not to have been received successfully, integrity checking of packet contents, and authentication of packet sender. We may use functionality similar to that in the Control Message Transport Protocol (used to transmit IDPR control messages). This is not just TCP? Why? Dave   Received: from PIZZA.BBN.COM by BBN.COM id aa03644; 12 Oct 94 9:59 EDT Received: from pizza by PIZZA.BBN.COM id aa23422; 12 Oct 94 9:46 EDT Received: from CLynn.BBN.COM by PIZZA.BBN.COM id aa23418; 12 Oct 94 9:43 EDT Date: Wed, 12 Oct 94 9:42:30 EDT From: Charles Lynn To: nimrod-wg@BBN.COM Subject: Re: nimrod protocols From Joel Halpern > 1) The description indicates that Hierarchcial update distributes maps and > endpoint/locator associations. Then the Query/response says that it > is used for both fetching more detailed maps, and for determining > locators for an endpoint. If this is a different binding than that > distributed by the hierarchical update process, what binding is it, > and when is it used. (I think that these are actually two different > findings, but...) I thought that one distinction was that query/response was point-to-point while Hierarchcial update would use some form of multicast. Is this correct? From Dave Bridgham > 5. Reliable transport. This protocol will be used to carry all > Nimrod control packets (such as maps and path setup information). > It will include retransmission of packets perceived not to have > been received successfully, integrity checking of packet contents, > and authentication of packet sender. We may use functionality > similar to that in the Control Message Transport Protocol (used to > transmit IDPR control messages). > >This is not just TCP? Why? I was thinking about using T/TCP (RFC 1644). It should be more efficient for transactions like query/response, and would fall back to TCP in the presence of errors. (Getting a transaction protocol deployed might be viewed as another carrot for deploying NIMROD.) Does anyone have any thoughts on the pluses or minuses of using T/TCP? Charlie   Received: from PIZZA.BBN.COM by BBN.COM id aa06953; 12 Oct 94 10:40 EDT Received: from pizza by PIZZA.BBN.COM id aa23718; 12 Oct 94 10:19 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa23712; 12 Oct 94 10:17 EDT Received: from wd40.ftp.com by BBN.COM id aa04701; 12 Oct 94 10:12 EDT Received: from ftp.com by ftp.com ; Wed, 12 Oct 1994 10:12:04 -0400 Received: from mailserv-D.ftp.com by ftp.com ; Wed, 12 Oct 1994 10:12:04 -0400 Received: by mailserv-D.ftp.com (5.0/SMI-SVR4) id AA01424; Wed, 12 Oct 94 10:08:49 EDT Date: Wed, 12 Oct 94 10:08:49 EDT Message-Id: <9410121408.AA01424@mailserv-D.ftp.com> To: msteenst@BBN.COM Subject: Re: nimrod protocols From: Frank Kastenholz Reply-To: kasten@ftp.com Cc: nimrod-wg@BBN.COM Content-Length: 2959 Martha, I have a couple of questions... > 1. Hierarchical update. This protocol will take care of automatic > distribution of both maps and endpoint/locator associations. It is a > form of flooding, limited to a particular portion of the clustering > hierarchy. > > 2. Query/response. This protocol will be used both to obtain more > detailed maps of a given node and to determine the locators for a > particular endpoint. These responses seem to be the same (or at least contain much the same information) as the Hierarchical Updates. Any thoughts on making the HU be the response to the query? (only difference (?) is that instead of flooding, you'd unicast it to the requestor). As I look at these two protocols I start wondering how one node will learn the locator of another node. The mechanism that I see is that when I type 'telnet foo.bar.com', the local node does a standard DNS lookup and gets the EID for 'foo.bar.com', yes? Now I have to translate the EID into a Locator. Using the Q/R protocol I ask my local routing agent "What's the locator for EID X?". Assuming that foo.bar.com is not local, how does the local routing agent know who to ask for the mapping? > 4. Discovery. These are the Nimrod bootstrapping mechanisms, > including neighbor discovery as well as agent discovery. We have also > thought about spreading this functionality between hierarchical update > and query/response, instead of having a separate discovery protocol, > because it could fit within these protocols. However, we also thought > this might significantly complicate these protocols, and for now we > have decided to keep the discovery mechanisms separate. Could some of this stuff be layered on top of BOOTP or DHCP (make it into DRCP?) or the new Service Location Protocol? > 5. Reliable transport. This protocol will be used to carry all Nimrod > control packets (such as maps and path setup information). It will > include retransmission of packets perceived not to have been received > successfully, integrity checking of packet contents, and > authentication of packet sender. We may use functionality similar to > that in the Control Message Transport Protocol (used to transmit IDPR > control messages). How would this be different from TCP? Because it is 'message' based rather than stream based? IP6 includes security stuff; primarily an authentication header. When running this protocol over IP6 it would make sense to use the security that's already there, so would your authentication functions be optional? > Ram Ramanathan has done a lot of thinking about these candidate Nimrod > protocols, particularly how they can be cast as finite state machines. I suggest that the complexity of the individual finite state machines be kept to a minimum, from a debug/implementation/interoperability perspective. I'd rather have more, simpler, machines than fewer, more complex, machines. -- Frank Kastenholz   Received: from PIZZA.BBN.COM by BBN.COM id aa07621; 12 Oct 94 10:50 EDT Received: from pizza by PIZZA.BBN.COM id aa23776; 12 Oct 94 10:23 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa23771; 12 Oct 94 10:21 EDT Received: from nbkanata.Newbridge.COM by BBN.COM id aa05031; 12 Oct 94 10:15 EDT Received: from Newbridge.COM ([138.120.100.14]) by nbkanata.Newbridge.COM (4.1/SMI-4.1) id AA04212; Wed, 12 Oct 94 10:10:27 EDT Received: from mako.newbridge by Newbridge.COM (4.1/SMI-4.0) id AA06732; Wed, 12 Oct 94 10:10:27 EDT Received: from lobster.Newbridge.COM by mako.newbridge (4.1/SMI-4.1) id AA19178; Wed, 12 Oct 94 10:16:21 EDT Received: by lobster.Newbridge.COM (5.0/SMI-SVR4) id AA01446; Wed, 12 Oct 1994 10:16:30 +0500 Date: Wed, 12 Oct 1994 10:16:30 +0500 From: Joel Halpern Message-Id: <9410121416.AA01446@lobster.Newbridge.COM> To: nimrod-wg@BBN.COM Subject: Re: nimrod protocols X-Sun-Charset: US-ASCII Content-Length: 1172 I am not current on the status of T/TCP. However, I will note that BGP has had one security problem with using TCP for transport. Due to the very weak security, there was nothing to prevent an attacker from sending a TCP FIN to every BGP machine in sight. BGP internal security will do nothing to prevent this. This might not be a problem worth fixing, but we should be aware of it. There may also be another matter. If we use TCP for reliable flooding, this generally means that TCP has a copy of each packet we are flooding, in addition to the copy routing machinery has. This could add significant memory consumption when a couple of neighbors start up. We are also restricted with regard to what we can know about when a neighboring Nimrod machine has usefully received a packet (eg Nimrod processed it) if TCP is our reliable transport. These issues were recently discussed in the ATM Forum PNNI group, and John Moy persuaded us to use native flooding instead of SSCOP (ATM's reliable transport). Again, we may find that these are not overwhelming, but they should be considered. Thank you, Joel M. Halpern jhalpern@newbridge.com Newbridge Networks Inc.   Received: from PIZZA.BBN.COM by BBN.COM id aa07686; 12 Oct 94 10:51 EDT Received: from pizza by PIZZA.BBN.COM id aa23730; 12 Oct 94 10:20 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa23726; 12 Oct 94 10:18 EDT Received: from wd40.ftp.com by BBN.COM id aa04870; 12 Oct 94 10:13 EDT Received: from ftp.com by ftp.com ; Wed, 12 Oct 1994 10:13:29 -0400 Received: from mailserv-D.ftp.com by ftp.com ; Wed, 12 Oct 1994 10:13:29 -0400 Received: by mailserv-D.ftp.com (5.0/SMI-SVR4) id AA01455; Wed, 12 Oct 94 10:10:12 EDT Date: Wed, 12 Oct 94 10:10:12 EDT Message-Id: <9410121410.AA01455@mailserv-D.ftp.com> To: nimrod-wg@BBN.COM Subject: re Nimrod Protocols From: Frank Kastenholz Reply-To: kasten@ftp.com Content-Length: 388 > I was thinking about using T/TCP (RFC 1644). It should be more efficient > for transactions like query/response, and would fall back to TCP in the > presence of errors. (Getting a transaction protocol deployed might be > viewed as another carrot for deploying NIMROD.) Does anyone have any > thoughts on the pluses or minuses of using T/TCP? or VMTP? -- Frank Kastenholz   Received: from PIZZA.BBN.COM by BBN.COM id aa10945; 12 Oct 94 11:37 EDT Received: from pizza by PIZZA.BBN.COM id aa24288; 12 Oct 94 11:12 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa24284; 12 Oct 94 11:10 EDT Received: from nsco.network.com by BBN.COM id aa08654; 12 Oct 94 11:04 EDT Received: from anubis.network.com by nsco.network.com (4.1/1.34) id AA28056; Wed, 12 Oct 94 10:06:16 CDT Received: from blefscu.network.com by anubis.network.com (4.1/SMI-4.1) id AA13706; Wed, 12 Oct 94 10:04:09 CDT Date: Wed, 12 Oct 94 10:04:09 CDT From: Andrew Molitor Message-Id: <9410121504.AA13706@anubis.network.com> To: nimrod-wg@BBN.COM Subject: Re: nimrod protocols Does nimrod's reliable transport protocol need to be congestion controlled, and all that other fun stuff TCP has? It's not terribly clear how large a transaction is going to be, in general. If we're talking about stuff that generally fits in a single frame, and which doesn't need to have multiple packets in flight for performance, it's possible to build protocols that are a bit lighter than TCP, and more message oriented so you don't need to go un-byte-streaming a TCP stream. On the other hand, if the data are large, so TCP-like stuff is necessary, it'd be best to build atop TCP. It's terribly easy to botch a non-trivial transport protocol. So, any back of the envelope guesses as to how large a typical map request/response thing is? Andrew   Received: from PIZZA.BBN.COM by BBN.COM id aa12826; 12 Oct 94 12:05 EDT Received: from pizza by PIZZA.BBN.COM id aa24527; 12 Oct 94 11:45 EDT Received: from CLynn.BBN.COM by PIZZA.BBN.COM id aa24523; 12 Oct 94 11:43 EDT Date: Wed, 12 Oct 94 11:37:05 EDT From: Charles Lynn To: nimrod-wg@BBN.COM Subject: Re: nimrod protocols Frank, You ask: > The mechanism that I see is that when I type 'telnet foo.bar.com', the > local node does a standard DNS lookup and gets the EID for > 'foo.bar.com', yes? Now I have to translate the EID into a Locator. > Using the Q/R protocol I ask my local routing agent "What's the > locator for EID X?". Assuming that foo.bar.com is not local, how does > the local routing agent know who to ask for the mapping? One of my assumptions is that there is NO GLOBAL database for which an EID is a key. I would like to see how far we can get (technically) before having to drop this assumption. Thus my model would be: The local node does a standard DNS lookup for 'foo.bar.com' and gets any A or AAAA records, which contain the locator, as well as the associated EID record. (Yes, a host may have multiple EIDs. But do they correspond to the host, or to an advertized service?) IPv6 is making it easy(ier) to renumber and consequently update the DNS AAAA entry(s), so I think we should just use it for NIMROD locator updates. Charlie   Received: from PIZZA.BBN.COM by BBN.COM id aa16329; 12 Oct 94 13:03 EDT Received: from pizza by PIZZA.BBN.COM id aa25058; 12 Oct 94 12:36 EDT Received: from TTL.BBN.COM by PIZZA.BBN.COM id aa25054; 12 Oct 94 12:35 EDT To: nimrod-wg@BBN.COM Subject: Re: nimrod protocols Date: Wed, 12 Oct 94 12:31:58 -0400 From: Ram Ramanathan Folks, My thoughts/comments on the ensuing discussion. On Joel's initial note wrt concern about decomposition and its complexities: J>However, one aspect seemed clear to me. For reasons of generality, the J>design allowed for separating each of the components of the system from J>all other components. J>It seems to me that while this is necessary in the long run, in the short J>run it complicates life significantly. One needs protocol mechanisms for J>each piece to talk to each other pieces. It was not obvious to me that J>the "same" protocol would work for all pieces. Yes, I agree that the "same" protocol will not work for all pieces. However, we may be able to get away with a small number of protocols, for instance, those mentioned by Martha. Joel, when you talked about "components" and "pieces" in the above message, were you referring to the functional decomposition or protocol decomposition? By your phrase "protocol mechanisms for each piece to talk to..." I assumed the former. If so, then I believe that if one can split the functionality into pieces that have minimal interaction, inter-piece communication is not very complex. For instance, association maintenance and map distribution do not interact very much. In any case, I think there are three "kinds" of decompositions. My description here also doubles as a summary of current thinking on Nimrod protocols for me and perhaps some of the BBN gang. Functional Decomposition. Or, how do we chop Nimrod functionality up? ------------------------ I talked about this a bit in the Toronto IETF (2nd session). The "components" are: 1. Neighbor Discovery 2. Agent Discovery 3. Association (endpoint-locator) Maintenance 4. Map distribution 5. Node, Arc, Endpoint Locator Acquisition 6. Path Setup & Teardown 7. Arc Formation (between nodes). Agent Decomposition. Or, what are the "components" that participate in ------------------ implementing the functionality? From Martha's "A Perspective on Nimrod Functionality", they are: 1. Forwarding Agents 2. Route Agents (handle maps) 3. Entity Representatives (Node/Arc/Endpoint Representatives) 4. Association Agents Now, here are "pieces" that talk with each other to achieve the functionality. Some pieces have little to do with each other. For instance Association Agents and Route Agents do not talk much. We need protocol mechanisms by which these pieces can talk in order to implement the Functionality. Thus we have Protocol Decomposition. An abstraction and modularization of the distributed ---------------------- mechanisms required between the Agent pieces to implement functionality pieces. As Martha mentioned, and restated here 1. Discovery Protocol 2. Update (Hierarchical) Protocol 3. Query/Response Protocol 4. Reliable Transport Protocol 5. Path handling Protocol A possible mapping between protocols and funcitonality is as follows: ------- Query-Response Protocol : Association Query, Map Query, Locator Acquisition Map formation. Update Protocol : Association Update, Map Update, Agent Discovery (*). Discovery Protocol : Neighbor Discovery, Agent Discovery (*). Path Protocol : Path Setup, Path Teardown. (*) Not clear which protocol Agent Discovery can be shoe-horned into best... Any ideas would be great! A protocol is characterized by a FSM and a 3-dimensional table. The FSM is greatly simplified if we decide to have a Reliable Transport protocol of some sort. The 3 dimensions of the table are: Receiving Agent, Received Message (Database), Sending Agent. Each entry in the table is an action to be performed. With this characterization, the details of mapping functionality is reduced to filling the table entries. I have worked out a possible draft of FSM and table entries using the mechanisms described in Martha's Functionality document, for the Update and Q/R protocols and the functionalities they implement. I will be glad to discuss this with anyone interested. On hierarchical Updates vs Query/Response, Joel writes > 1) The description indicates that Hierarchcial update distributes maps and > endpoint/locator associations. Then the Query/response says that it > is used for both fetching more detailed maps, and for determining > locators for an endpoint. If this is a different binding than that > distributed by the hierarchical update process, what binding is it, > and when is it used. (I think that these are actually two different > findings, but...) I believe they are the same bindings, but not everybody receives the bindings by virtue of updates alone. Hierarchical update distributes maps to some portions of the network, not all. Nodes to which maps are not (automatically) distributed using the update mechanism may get these maps by querying for it. A somewhat similar situation exists for association updates/query. I may be reading your question completely wrong here. Charlie says, on the same topic >I thought that one distinction was that query/response was point-to-point >while Hierarchcial update would use some form of multicast. Is this >correct? Yes, typically it would be "some" form of multicast. In my mind I see update as a WRITE operation on a distributed database and Q/R as a READ operation. If in a distributed database information is replicated, as Nimrod is designed to have, there has to be some kind of multicasting in a WRITE operation - although, whether or not that is part of the update prot. itself is not clear. That is I could have one authoritative guy get the update and have a "database consistency" mechanism that simply ensures that all the replicated pieces are up-to-date. Cheers, -Ram. -------------------------------------------------------------- Ram Ramanathan Advanced Networking R & D BBN Systems and Technologies 10 Moulton Street, Cambridge, MA 02138 Phone : (617) 873-2736 INTERNET : ramanath@bbn.com   Received: from PIZZA.BBN.COM by BBN.COM id aa20546; 12 Oct 94 14:11 EDT Received: from pizza by PIZZA.BBN.COM id aa25727; 12 Oct 94 13:54 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa25723; 12 Oct 94 13:52 EDT Received: from ginger.lcs.mit.edu by BBN.COM id aa19271; 12 Oct 94 13:49 EDT Received: by ginger.lcs.mit.edu id AA21235; Wed, 12 Oct 94 13:49:40 -0400 Date: Wed, 12 Oct 94 13:49:40 -0400 From: Noel Chiappa Message-Id: <9410121749.AA21235@ginger.lcs.mit.edu> To: kasten@ftp.com, nimrod-wg@BBN.COM Subject: Re: nimrod protocols Cc: jnc@ginger.lcs.mit.edu From: Frank Kastenholz when I type 'telnet foo.bar.com', the local node does a standard DNS lookup and gets the EID for 'foo.bar.com', yes? Now I have to translate the EID into a Locator. Using the Q/R protocol I ask my local routing agent "What's the locator for EID X?". NOT! You should get the current locator from the DNS at the same time that you get the EID. ("Current", except in special circumstance like a very mobile host, in which case you should get a locator for a base station, or something.) (You might need that mapping as an IPv4 transition hack, but that's not architecture.) Also: I'm not sure we should have EID's (as in shortish, fixed-length, binary names for endpoints). I think we should have a separate, non-topological, namespace for endpoints (I call them TLEN's, alternatives gladly accepted), but I have been persuaded by arguments on Big-I that the management of such another namespace, above and beyond the existing ones, would be sufficiently painful that it might not be worth it. Historical sidenote: EID's came from two places. One was IPv4 compatability; reinterpreting the 32-bit field as an EID maximized the lifetime of IPv4. The second was for globally-unique (GU) flow identifiers. My thinking was that you needed them (to prevent hassles with collisions), and the best way was to tack a local flow-id onto a GU EID, which you had in the packet anyway (see point one). That way, you got twice the bang for bits in the header used to hold the EID; once as an EID, and again as part of the flow-id. However, for a variety of reasons (such as NDM), it doesn't seem like it will be possible to overload the EID, as the whole flow-id will need to be bashable. If you have to have a whole separate field for flow-id's, I currently think making them "path-unique" (i.e. not local, like X.25, or global, but something in between) is good, then you can get away with a nice short length like 16 or 32 bits. So, if that use for EID's is gone, EID's as a whole look less attractive. One good option is to use DNS names as TLEN's. Of course, since DNS names can be arbitrary strings, provision of locally-created globally-unique names (for things like mobile entities) is now trivial; you append a process id, date-time-stamp, whatever, to your DNS name. We also don't have to worry about getting the size right, or running out of them! The exact mechanics of when these TLEN's get carried in packets, etc, is all up in the air. The "Nimrod IPng Requirements" document touches on this; you could use ESEL's in packets, or associate endpoints with flows, in which case the flow-id alone would do it. (This would, of course, give you a blindingly short packet for packets which belong to flows; a hop count, a flow-id, a length, and not much else. It should fit in 12 bytes easily, shorter than the existing IPv4 header. Make it 16 bytes if you want perpetual alignment.) Of course, for datagram applications you'd still have to send the whole TLEN, at least if the endpoint identification is needed. When running this protocol over IP6 it would make sense to use the security that's already there, so would your authentication functions be optional? Given the utter incompetence and uselessness of the IPv6 design, my *personal* opinion is that I'd ignore it totally in designing the basic Nimrod protocols. You should design a separate Nimrod inter-router format which meets the requirements laid out in the Nimrod IPng requirements document. Bending SIPP to shape will be so ugly you'll barf into your socks. Whatever support strategy works for IPv4 will work with SIPP (if it ever gets deployed widely). Noel   Received: from PIZZA.BBN.COM by BBN.COM id aa22214; 12 Oct 94 14:34 EDT Received: from pizza by PIZZA.BBN.COM id aa25927; 12 Oct 94 14:11 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa25922; 12 Oct 94 14:08 EDT Received: from ginger.lcs.mit.edu by BBN.COM id aa20252; 12 Oct 94 14:08 EDT Received: by ginger.lcs.mit.edu id AA21391; Wed, 12 Oct 94 14:07:56 -0400 Date: Wed, 12 Oct 94 14:07:56 -0400 From: Noel Chiappa Message-Id: <9410121807.AA21391@ginger.lcs.mit.edu> To: dab@epilogue.com, nimrod-wg@BBN.COM Subject: Re: nimrod protocols Cc: jnc@ginger.lcs.mit.edu From: Dave Bridgham > 5. Reliable transport. This is not just TCP? Why? Intersting question. I can see several reasons not to: - if you have application requirements (e.g. reliable flooding) which can be met better with a separate protocol (which is e.g. not unicast) - if you want to avoid features, such as TCP congestion control, which will get in your way (e.g. the problems the Canadian guys had with BGP) I don't offhand have a good feel for the right answer. It's a good point, and one we should make sure to examine carefully. What I'd suggest is that we get a little further down the road, and have a protocol sketched out, and at that point we can compare the two options a little more intelligently. Psychologically, this could be dangerous, as the pressure to use what you spent that time and energy on could lead you to make a wrong choice. However, I expect people thinking about Nimrod are strong enough to put that to one side and pick the best answer. Noel   Received: from PIZZA.BBN.COM by BBN.COM id aa29329; 12 Oct 94 16:12 EDT Received: from pizza by PIZZA.BBN.COM id aa26837; 12 Oct 94 15:53 EDT Received: from KARIBA.BBN.COM by PIZZA.BBN.COM id aa26833; 12 Oct 94 15:50 EDT To: nimrod-wg@BBN.COM Subject: reliable transport of Nimrod control messages Date: Wed, 12 Oct 94 15:52:36 -0400 From: Martha Steenstrup Here's a little history on why we did not use TCP to distribute control messages in IDPR. Many of these same reasons apply to Nimrod. Like Nimrod, IDPR had several different types of control messages - routing updates, path control messages, etc. Each had different requirements in terms of its timeliness, integrity, and reliability of transport. Using a single TCP connection to transport these different types of control messages didn't make a lot of sense, because we wanted to have different numbers of retransmissions per type of message. But multiple TCP connections per neighbor IDPR router, one for each type of control message, seemed like a lot of extra work for a router to maintain the necessary state and execute the protocol. Furthermore, at that time, there was no selective-retransmit version of TCP. So the loss of one control message when several different ones were in the process of transmission could make for more control traffic overhead. In addition, TCP did not provide some of the integrity features we wanted. In particular, all IDPR packets carried an absolute timestamp used to determine when a packet was too old or too new (i.e., something wrong with someone's clock). Timestamp checks were part of IDPR's integrity checking. Moreover, IDPR had the ability to specify a variety of source authentication mechanisms, where the authentication check could cover the entire packet contents and could act as a checksum as well as an authentication mechanism. Timestamp checking and authentication were not then part of TCP. Lastly, and here comes the heresy, we did not want to tie ourselves to a TCP/IP environment (I can see the lightning bolts now). Believe it or not, IDPR would work equally well in an OSI environment or a TCP/IP environment, and by mandating TCP as the mechanism for control message transport we would limit the applicability of the protocol. So we ended up making a transaction-based protocol (CMTP) for IDPR control messages, that had all of the features we needed for IDPR control message transport. (Actually, at the beginning, the distribution mechanism for each type of IDPR control message had its own transport protocol built into it. These transport protocols used many of the same common routines, but were nevertheless distinct. We later made a single transport protocol that satisfied the requirements of all IDPR control messages, at the urging of Tony Li.) CMTP also had NAKs as well as ACKs, which were used to transport additional information from the higher-level protocols (e.g., update distribution) back to the source, when the packet passed the CMTP checks but failed the higher-level protocol checks. If there is a standard transaction-based protocol that satisfies the requirements of Nimrod control message transport, that would be great. Please let us know. Charlie Lynn is currently checking out what's available in the Internet to handle the requirements for Nimrod. CMTP is one of the options, and may be the most flexible. m   Received: from PIZZA.BBN.COM by BBN.COM id aa00628; 12 Oct 94 16:32 EDT Received: from pizza by PIZZA.BBN.COM id aa27046; 12 Oct 94 16:10 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa27042; 12 Oct 94 16:08 EDT Received: from wd40.ftp.com by BBN.COM id aa28894; 12 Oct 94 16:04 EDT Received: from ftp.com by ftp.com ; Wed, 12 Oct 1994 16:04:38 -0400 Received: from mailserv-D.ftp.com by ftp.com ; Wed, 12 Oct 1994 16:04:38 -0400 Received: by mailserv-D.ftp.com (5.0/SMI-SVR4) id AA02856; Wed, 12 Oct 94 16:01:22 EDT Date: Wed, 12 Oct 94 16:01:22 EDT Message-Id: <9410122001.AA02856@mailserv-D.ftp.com> Yto: jnc@ginger.lcs.mit.edu Subject: Re: nimrod protocols From: Frank Kastenholz Reply-To: kasten@ftp.com Cc: kasten@ftp.com, nimrod-wg@BBN.COM, jnc@ginger.lcs.mit.edu Content-Length: 3607 > Return-Path: > Date: Wed, 12 Oct 94 13:49:40 -0400 > From: Noel Chiappa > To: kasten@ftp.com, nimrod-wg@BBN.COM > Subject: Re: nimrod protocols > Cc: jnc@ginger.lcs.mit.edu > Content-Type: text > Content-Length: 3706 > > From: Frank Kastenholz > > when I type 'telnet foo.bar.com', the local node does a standard DNS > lookup and gets the EID for 'foo.bar.com', yes? Now I have to > translate the EID into a Locator. Using the Q/R protocol I ask my > local routing agent "What's the locator for EID X?". > > NOT! > > You should get the current locator from the DNS at the same time that you get > the EID. ("Current", except in special circumstance like a very mobile host, > in which case you should get a locator for a base station, or something.) > > (You might need that mapping as an IPv4 transition hack, but that's not > architecture.) eeeeeek! what does this do for renumbering? what about mobility? what about configurability? are you expecting that in deploying nimrod we also deploy a revised dns system that allows for large-scale, dynamic, rapid, updates? what about auto-configuration? consider something like a mobile internetwork. one example i like for twisting people's brains is the usn's needs to put networks on aircraft carriers and networks on aircraft. the aircraft-network's 'service provider' is the carrier-network. the carrier-network's service provider could be whatever naval district/area/thing that the carrier is in. as the carrier moves around, the entire carrier-network (and all its aircraft's networks) 'go mobile' and have to be renumbered as they change positions in the topology. then, as the carrier moves around, the planes fly off and land, maybe changing to differnet carriers, or to a different 'network' (maybe when the plane's network is connected to whatever controls the plane -- maybe the carrier when it is on the flight deck, maybe some usmc fac when the plane is bombing some iraqi tanks...). you'd expect to update dns fast enough to deal with this? similarly, if someone decides to change the locator topology of their network, they'd then need to change dns as well. this would be a strong disincentive against changing network topology. perhaps strong enough that it will hardly ever be done. then a highly dynamic and flexible system will become a static and crufty system and people will install all sorts of hacks to get around making painful reconfigurations. why make the dynamic/flexible system then? > When running this protocol over IP6 it would make sense to use the > security that's already there, so would your authentication functions > be optional? > >Given the utter incompetence and uselessness of the IPv6 design, my *personal* >opinion is that I'd ignore it totally in designing the basic Nimrod protocols. if the internet becomes a sipp-based internet (let's be real, it could happen, regardless of anyone's fondest wishes...) then this would really make no sense. we'd be reinventing the wheel. >You should design a separate Nimrod inter-router format which meets the >requirements laid out in the Nimrod IPng requirements document. Bending SIPP >to shape will be so ugly you'll barf into your socks. Whatever support >strategy works for IPv4 will work with SIPP (if it ever gets deployed widely). while i am not a proponent of sipp, i am also not a proponent of re-inventing the wheel. if the internet is sipp based, then that's what we will have to work with. -- Frank Kastenholz   Received: from PIZZA.BBN.COM by BBN.COM id aa04292; 12 Oct 94 17:46 EDT Received: from pizza by PIZZA.BBN.COM id aa27816; 12 Oct 94 17:22 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa27812; 12 Oct 94 17:20 EDT Received: from nbkanata.Newbridge.COM by BBN.COM id aa02986; 12 Oct 94 17:17 EDT Received: from Newbridge.COM ([138.120.100.14]) by nbkanata.Newbridge.COM (4.1/SMI-4.1) id AA14529; Wed, 12 Oct 94 17:12:24 EDT Received: from mako.newbridge by Newbridge.COM (4.1/SMI-4.0) id AA23995; Wed, 12 Oct 94 17:12:23 EDT Received: from lobster.Newbridge.COM by mako.newbridge (4.1/SMI-4.1) id AA22668; Wed, 12 Oct 94 17:18:16 EDT Received: by lobster.Newbridge.COM (5.0/SMI-SVR4) id AA01565; Wed, 12 Oct 1994 17:18:25 +0500 Date: Wed, 12 Oct 1994 17:18:25 +0500 From: Joel Halpern Message-Id: <9410122118.AA01565@lobster.Newbridge.COM> To: nimrod-wg@BBN.COM Subject: Nimrod Protocol Machinery X-Sun-Charset: US-ASCII Content-Length: 4835 Martha asked me to post this to the list. (She sent it to me, acceidentally omitting the list.) (Then she gets to post my response.) Thank you, Joel M. Halpern jhalpern@newbridge.com Newbridge Networks Inc. ----- Begin Included Message ----- The hierarchical update protocol is used to distribute maps and endpoint/locator associations automatically, to a limited number of places, whenever there is a change in a map or the locator for an endpoint. (Maps and associations are distributed independently, but the same protocol is used in both cases.) Thus, the hierarchical update protocol is used to distribute information to "local" entities that are likely to require it. Costs for such unsolicited distribution are likely to be paid by the distributing entity. The query/response protocol is used to obtain information from a Nimrod database. For example, this information might be a more detailed map of a node, a locator for an endpoint, or a set of routes to a particular destination. This protocol is used to obtain information required by a specific entity but not normally required throughout an internetwork. (For endpoints, the locator associations distributed by the hierarchical update protocol are the same as those distributed in response to a query. It's just that in one case, the distribution of information is automatic to a portion of the internetwork, and in the other case, the distribution of information is in response to a specific request.) Costs for such requested information are likely to be paid by the requestor. Thus, one can choose the desired cost/performance tradeoffs by setting limits on what routing information gets distributed automatically and how far that information is distributed. The query/response protocol needs to be in any Nimrod prototype. It is the mechanism by which one endpoint obtains the locator of another endpoint with which it wants to communicate. It is also the mechanism by which a forwarding agent obtains a route. Furthermore, it is used to refresh information in a Nimrod database. For example, when a Nimrod agent returns to service after an outage, it may request from another agent of the same type, the contents of that agent's database, in order to rebuild its own database. Route agents, the entities that generate routes, determine when to ask for more detailed maps for particular nodes. Each route agent may have different criteria which it uses to decide when to ask for more detailed maps. There is not one set of criteria that is uniformly applied by all route agents when determining whether to request more detailed information. Some common reasons include: - The source or destination requests data transport by specific service providers, which may be components of larger nodes. In this case, the route agent might wish to get the detailed maps of those nodes that indicate they contain such service providers and to select routes within those nodes that include the specific service providers. - The source or destination requests a very specific quality of service. Large nodes are likely to advertise abstracted versions of the actual service they offer. In this case, the route agent might wish to get the detailed maps of those nodes that indicate that they might provide the requested service (e.g., the requested service falls within the range advertised for the large node), and if possible, to select routes within those nodes that provide the requested service. You are correct in saying that to get a Nimrod prototype up and running, we do not need to include the facility to request more detailed maps. In the long run, we want this feature but it's not necessary in the initial version. All Nimrod packet forwarding relies on the existence of underlying paths. This is true in both flow mode and datagram mode. For flow mode, Nimrod must install session-specific state in at least two routers, one at the source and one at the destination, and may in fact need to install such state in many other routers in between. For datagram mode, Nimrod need not install any session-specific state in any routers. Nevertheless, to forward a datagram, Nimrod may have to set up paths which will carry the datagram if no such paths already exist. Even if no path setup is required for a datagram, datagram forwarding requires many of the same procedures as path setup, including selecting the next hop and determining whether access restrictions permit the router to carry the specific packet. In fact, the only difference between datagram mode and flow mode is the establishment of session-specific state in the latter. The rest of the functionality is exactly the same. Hence, we refer to the protocol for setting up flows and for forwarding datagrams as "path setup". m ----- End Included Message -----   Received: from PIZZA.BBN.COM by BBN.COM id aa13562; 12 Oct 94 22:19 EDT Received: from pizza by PIZZA.BBN.COM id aa29610; 12 Oct 94 22:08 EDT Received: from KARIBA.BBN.COM by PIZZA.BBN.COM id aa29606; 12 Oct 94 22:05 EDT To: nimrod-wg@BBN.COM Subject: Joel's response Date: Wed, 12 Oct 94 22:07:40 -0400 From: Martha Steenstrup Hi, Here's Joel's response to my message, as promised. ------------------- There seems to be a difference of opinion. You are saying that the query/response protocol is how an endpoint finds the locator for another endpoint. Noel is saying that that is NOT the case. He specifically said that such as service is a bad idea. I am inclined to agree at least to the extend that I can not envision such a mechanism with desirable scaling properties. Unless of course you consider the DNS query to be that mechanism? It was the forwarding agent using a query protocol to get a route that makes me wonder about deferral. If the forwarding agent is required to be co-resident with a routing agent, for the protocol specification, then we do not get into defining such a query. This might keep our lives simpler. With regard to expanding maps, your first example points to one of the problems. I have trouble imaging that an aggregated map will have the names of the service providers who are hidden inside it. (There may be a lot of local providers) If such information is not tagged on the aggregated map, how will a remote entity know when to explode it. This general problem is one that clearly needs research before we try to say to much about it. Thank you, Joel M. Halpern jhalpern@newbridge.com Newbridge Networks Inc.   Received: from PIZZA.BBN.COM by BBN.COM id aa17712; 13 Oct 94 16:20 EDT Received: from pizza by PIZZA.BBN.COM id aa05435; 13 Oct 94 16:01 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa05431; 13 Oct 94 15:56 EDT Received: from ginger.lcs.mit.edu by BBN.COM id aa16219; 13 Oct 94 15:54 EDT Received: by ginger.lcs.mit.edu id AA29223; Thu, 13 Oct 94 15:54:13 -0400 Date: Thu, 13 Oct 94 15:54:13 -0400 From: Noel Chiappa Message-Id: <9410131954.AA29223@ginger.lcs.mit.edu> To: kasten@ftp.com, nimrod-wg@BBN.COM Subject: Re: nimrod protocols Cc: jnc@ginger.lcs.mit.edu From: kasten@ftp.com (Frank Kastenholz) Tried to reply to this last night, discovered my brain has aged to the point where I have to be awake to really thing this stuff through! :-) > You should get the current locator from the DNS at the same time that > you get the EID. what does this do for renumbering? what about mobility? what about configurability? are you expecting that in deploying nimrod we also deploy a revised dns system that allows for large-scale, dynamic, rapid, updates? Well, to the extent that functionality is needed, *some* system is going to have to provide that functionality, it might as well be the DNS. I'm not sure you always have to go back through the DNS though; if I'm mobile, and I have an open connection to you, when I move, I can tell you my new locator directly. what about auto-configuration? As in, how to you get the EID->locator mapping in? Again, the problem is basically the same no matter wher you keep the mapping, in the DNS, or in some other database system which does more or les the same thing. you'd expect to update dns fast enough to deal with this? Well, we may need to completely redo the insides of the DNS, but yeah. I don't see that we need a whole separate system.. similarly, if someone decides to change the locator topology of their network, they'd then need to change dns as well. Well, I think locators should be assigned without human intervention, so we're gonna have to automate that. If you have a private key which is needed before you can update the DNS record, then effectively the key-pair becomes an endpoint "name" as well. this would be a strong disincentive against changing network topology. perhaps strong enough that it will hardly ever be done. then a highly dynamic and flexible system will become a static and crufty system and people will install all sorts of hacks to get around making painful reconfigurations. Which is why you have to make addrress assignment totally automatic... > my *personal* opinion is that I'd ignore it totally in designing the > basic Nimrod protocols. You should design a separate Nimrod > inter-router format which meets the requirements laid out in the Nimrod > IPng requirements document. ... Whatever support strategy works for IPv4 > will work with SIPP (if it ever gets deployed widely). if the internet becomes a sipp-based internet ... then this would really make no sense. we'd be reinventing the wheel. ... while i am not a proponent of sipp, i am also not a proponent of re-inventing the wheel. if the internet is sipp based, then that's what we will have to work with. The problem is that SIPP, as it stands, does not provide what Nimrod needs, which was all very carefully laid out in the Nimrod IPng Requirements document. Saying "we'll do it with options" is not viable. If the packet tries to transit a non-Nimrod router, it won't know how to interpret the options, and blooey. Since you're only transiting Nimrod-aware routers anyway (unless the packet is encapsulated, barf, but I know we'll have to do that in some places), you might as well not torque yourself inside out, and just sit down and design a Nimrod inter-router format which gives you the things you need in a clear, straightforward, way. Noel   Received: from PIZZA.BBN.COM by BBN.COM id aa26989; 13 Oct 94 19:32 EDT Received: from pizza by PIZZA.BBN.COM id aa06934; 13 Oct 94 19:11 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa06930; 13 Oct 94 19:10 EDT Received: from guru.qualcomm.com by BBN.COM id aa26015; 13 Oct 94 19:06 EDT Received: (greg@localhost) by guru.qualcomm.com (8.6.9/QC-SOLARIS-2.1) id QAA22523; Thu, 13 Oct 1994 16:06:07 -0700 Date: Thu, 13 Oct 1994 16:06:07 -0700 From: Greg Noel Message-Id: <199410132306.QAA22523@guru.qualcomm.com> To: jnc@ginger.lcs.mit.edu, kasten@ftp.com Cc: nimrod-wg@BBN.COM Subject: Re: nimrod protocols Content-Length: 2446 As I've read the drafts of the Nimrod specifications, it has seemed to me that there are (at least) three different levels of mobility and corresponding mappings to EID and locator. It may be that different mechanisms are needed to deal with each type. As I think about it, there is a level of "mobility" where the typical changes are measured in days. In some sense, this is where the entity is registered for all to find, so it could be called the "registry" lookup. This is the level at which DNS operates, and is the level at which it makes sense to cache contact information on a longish basis. There's another level which has information about the current locator for the endpoint; it might have a volatility measured from several minutes to a couple of hours. One locator might be for when you are at home, the other for when you are at work. The third level is when the location is extremely volatile, changing on the order of a few seconds or even faster. The radio cells you pass through on the freeway would be an example of this. I think everybody agrees that there needs to be something at the registry level. The debate is whether the registry mechanism is sufficient to handle the demands at the other levels. I think it isn't. At the registry level, data should be valid for a "long" time, so you should be willing to cache it or even broadcast it. At the other levels, it's probably not worth this kind of investment. The middle level has to be tracked by the endpoints---if your locator changes or your partner's locator changes, you need to be aware of it. And if a locator changes, the last router for the old locator needs to remember it (for a "short" time) so that it can send updates. But I believe the last level is something that should _not_ be a part of Nimrod. For that, you need a service provider that gives a "freeway" locator at the middle level and tracks you internally. This is what a cellular phone service does now---on the one side, provides a fixed telephone number (middle-level locator) and delivers it to a rapidly- moving mobile phone. Three levels might be too simplistic, but I think the services provided at each level to be distinct enough to require different treatments. I've thought a little bit about whether this can be provided by a single mechanism; but that's the topic of a different note. (As an incredible oversimplification, I think the answer is "maybe.") -- Greg   Received: from PIZZA.BBN.COM by BBN.COM id aa28685; 15 Oct 94 22:35 EDT Received: from pizza by PIZZA.BBN.COM id aa20454; 15 Oct 94 22:13 EDT Received: from KARIBA.BBN.COM by PIZZA.BBN.COM id aa20450; 15 Oct 94 22:10 EDT Date: Sat, 15 Oct 94 22:12:46 EDT From: Martha Steenstrup To: nimrod-wg@BBN.COM Subject: two cents Using the DNS as the vehicle to manage the Nimrod endpoint/locator association database is a great idea over the long term, because we can build upon an existing well-maintained and widely deployed system rather than implementing and introducing an entirely new system ourselves. However, in the short term, I don't think that we will be able to use the DNS, because Nimrod requires certain functionality that the DNS does not currently provide. At the very least, DNS records must be able to carry Nimrod locators and endpoint identifiers (EIDs). Even if the DNS changes are minor, it will take awhile to integrate them into the DNS and to get them deployed - time we could be spending experimenting with a prototype of Nimrod. I think initially we should construct Nimrod-specific procedures for handling endpoint/locator associations. (One such candidate is described in the Nimrod functionality draft, but there are zillions of others.) Using Nimrod-specific procedures gives us several benefits, as follows. - We have complete control over these procedures, and hence we can get them implemented quickly, we can experiment with them, and we can easily modify them to provide better performance or slightly different functionality. - We would like the Nimrod endpoint/locator associations to keep pace with internetwork reconfigurations. Reconfigurations may not occur frequently, but the Nimrod association database should be able to accommodate them automatically, quickly and without human intervention. Currently, the DNS does not possess such functionality. - Mobility of endpoints and networks is an issue. We do not want to duplicate work that the Mobile IP group is doing. The draft on Nimrod mobility issues describes how Nimrod can easily accommodate the current Mobile IP protocol. However, there is functionality desired for supporting mobile internetworks which is not provided by the Mobile IP approach. Nimrod may be able to support some of this functionality, if we have a more dynamic system for updating endpoint/locator associations. Again, DNS does not currently support such dynamism. By using our own system initially, we have the flexibility to get things up and running quickly and to experiment. When we get some experience with Nimrod, we will then be in a much better position to generate a well-considered list of features we would like to have included in the DNS, in order to support the functionality required for Nimrod internetworks. An Example System. The example association database system in the draft supports automatic accommodation of locator changes resulting from reconfiguration and movement of endpoints and networks. The system propagates locator changes to the authoritative association source for the endpoint affected. It also propagates changes locally, i.e. within the immediate node containing the affected endpoint , but not to the entire internetwork. Thus, entities in the vicinity of the endpoint know how to reach it (and may also be more likely to be communicating with that endpoint, for example, if they're all members of a university or corporate network). Moreover, the perception of movement can be confined to the area in which it takes place. The rest of the internetwork need only know that the endpoint is still within the given node, not that it has moved within the node. Requests for locator information for a particular endpoint contain a unique endpoint label as the key into the association database. For ease of use, this label might be something that has structure and is organizationally assigned, e.g., a DNS domain name. Requests may be answered locally or from authoritative sources. The sequence of requests for retrieving a particular endpoint/locator association is in the spirit of the DNS, but not identical to it. (This example system by itself does not support extremely rapid mobility of endpoints. It would likely require support of routing mechanisms, which are currently beyond the scope of Nimrod.)   Received: from PIZZA.BBN.COM by BBN.COM id aa14114; 17 Oct 94 12:22 EDT Received: from pizza by PIZZA.BBN.COM id aa28812; 17 Oct 94 12:01 EDT Received: from TTL.BBN.COM by PIZZA.BBN.COM id aa28808; 17 Oct 94 11:58 EDT To: Andrew Molitor cc: nimrod-wg@BBN.COM Subject: Re: nimrod protocols In-reply-to: Your message of Wed, 12 Oct 94 10:04:09 -0500. <9410121504.AA13706@anubis.network.com> Date: Mon, 17 Oct 94 11:51:27 -0400 From: Ram Ramanathan > Date: Wed, 12 Oct 94 10:04:09 CDT > From: Andrew Molitor > Message-Id: <9410121504.AA13706@anubis.network.com> > To: nimrod-wg@BBN.COM > Subject: Re: nimrod protocols > > Does nimrod's reliable transport protocol need to be congestion > controlled, and all that other fun stuff TCP has? It's not terribly clear > how large a transaction is going to be, in general. If we're talking > about stuff that generally fits in a single frame, and which doesn't > need to have multiple packets in flight for performance, it's possible > to build protocols that are a bit lighter than TCP, and more message > oriented so you don't need to go un-byte-streaming a TCP stream. > > On the other hand, if the data are large, so TCP-like stuff is > necessary, it'd be best to build atop TCP. It's terribly easy to botch > a non-trivial transport protocol. > > So, any back of the envelope guesses as to how large a typical > map request/response thing is? > > > Andrew It seems to me that for most Nimrod protocol messages except the response for a map request, the data is not too large and could possibly be bounded to a single frame. With the map response, a querier could ask for not only a node's attributes (the "abstract map" (refer Nimrod Functionality document)) but also the connectivity of the nodes comprising it and their attributes (the "detailed map"). I think Andrew brought out a very good question on how big this can be. Can it be unbounded? Here is a very rough back-of-the-envelope calculation. The numbers I substitute may not please you, so comments are welcome on appropriate numbers. Perhaps this will help in the choice of an appropriate protocol. Math subject to verification. We assume that the node in question comprises of n nodes with an average degree of d. Each node has g groups such that the attributes (delay, bandwidth etc. ) of each group is the same. Each group has on average t attributes. Let M(n), M(g), M(t), M(l) denote the memory required by one node, group, attr and link respectively. Note that l = nd for a directed graph. Let B denote the no. of bytes for a locator. Then, the expression for the data size for a response to a query for a "detailed graph" is approximately, DataSize = (n+1)(M(n) + gM(g) + tR(t)) + lR(l) Okay, here are suggested numbers and a brief justification whenever possible. B = 32 (Noel's IPng requirements draft mentions 32 bytes per locator as "adequate"). M(n) = B M(g) = 10B (about 5 arc-pairs per group, with 2 locators per arc-pair) g = 3 (usually, we can say things like ALL or ALL except this arc-pair etc., so I estimate 3 as the average number of groups). t = 8 (bandwidth, delay, jitter, foo1, foo2...) M(t) = 6 (for each attribute, we need attr code (2 bytes) and attr val. (4 bytes)) d = 3 (guess) R(l) = 2B (assuming links are formed as concatenation of node locators). n = 10. This is the crucial one. What is the branching factor of the hierarchical tree, ie, how many nodes on average within a node? The classic paper by Kleinrock and Kamoun "Hierarchical routing in large Netwroks" says that table size optimization, the no. of nodes ineach node must be (total nodes)^(1/no. of levels). Assuming a million nodes and 6 levels, we get n=10. So with these numbers, we have, DataSize = 11(32 + 3(320 + 8(6))) + 30(64) = 14416 bytes. How big is this? Is this considered small enough for a protocol message? Can it be bounded? I think if n can be bounded, this can be too. Perhaps we could bound this thing by saying that detailed maps can only be obtained as successive abstract maps. It is easier to bound abstract maps. With the above numbers, they only cost 1136 bytes. In any case, I think we should consider carefully before going in for heavy machinery like TCP just for the query-response thingie. Especially, if it is not too large and if it can be broken down painlessly into smaller components using the protocol machinery itself. -Ram. -------------------------------------------------------------- Ram Ramanathan Advanced Networking R & D BBN Systems and Technologies 10 Moulton Street, Cambridge, MA 02138 Phone : (617) 873-2736 INTERNET : ramanath@bbn.com   Received: from PIZZA.BBN.COM by BBN.COM id aa16186; 17 Oct 94 12:52 EDT Received: from pizza by PIZZA.BBN.COM id aa29046; 17 Oct 94 12:25 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa29042; 17 Oct 94 12:23 EDT Received: from bells.cs.ucl.ac.uk by BBN.COM id aa13842; 17 Oct 94 12:18 EDT Received: from waffle.cs.ucl.ac.uk by bells.cs.ucl.ac.uk with local SMTP id ; Mon, 17 Oct 1994 17:17:58 +0100 To: Ram Ramanathan cc: Andrew Molitor , nimrod-wg@BBN.COM Subject: Re: nimrod protocols In-reply-to: Your message of "Mon, 17 Oct 94 11:51:27 EDT." Date: Mon, 17 Oct 94 17:17:54 +0100 Message-ID: <2825.782410674@cs.ucl.ac.uk> From: Jon Crowcroft >In any case, I think we should consider carefully before going in for >heavy machinery like TCP just for the query-response thingie. Especially, >if it is not too large and if it can be broken down painlessly into >smaller components using the protocol machinery itself. Ram, it is a tenet of the end2end reswarch group that TCP is not "heavy machinery" the socket interface, and possibly the byte stream interface support are, and the hacks to make that work properly for telnet and other protocols to which it is ill suited, but the basic protocol engine is small, elegant, and probably as nearly correct as can be provided its complete, and with T/TCP, i think its very close to that (alkthough i'd darlyu love to figure out an efficient anycast T/TCP, and just possibly a small group ordered M/T/TCP) jon   Received: from PIZZA.BBN.COM by BBN.COM id aa17890; 17 Oct 94 13:10 EDT Received: from pizza by PIZZA.BBN.COM id aa29246; 17 Oct 94 12:38 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa29242; 17 Oct 94 12:35 EDT Received: from ginger.lcs.mit.edu by BBN.COM id aa14353; 17 Oct 94 12:25 EDT Received: by ginger.lcs.mit.edu id AA24063; Mon, 17 Oct 94 12:25:12 -0400 Date: Mon, 17 Oct 94 12:25:12 -0400 From: Noel Chiappa Message-Id: <9410171625.AA24063@ginger.lcs.mit.edu> To: jhalpern@newbridge.com, nimrod-wg@BBN.COM Subject: Re: Nimrod Protocol Machinery Cc: jnc@ginger.lcs.mit.edu From: Martha Steenstrup The hierarchical update protocol is used to distribute maps and endpoint/locator associations automatically, to a limited number of places, whenever there is a change in a map or the locator for an endpoint. (Maps and associations are distributed independently, but the same protocol is used in both cases.) Martha, to focus in on the associations (leaving maps aside, that I all see), if we were using the DNS (perhaps turbocharged) to store locators, would you still be thinking that a Nimrod protocol is used to distribute that association? Are you thinking that that association update would be part of a host-initiated mobility mechanism? Of course, I guess the answer to this question depends on what we use for endpoint names. If we use DNS names, then we may not need a separate association database. If we don't, but use another namespace (e.g. EID's), then I can see that management of any (distributed) database using these names as keys would be a Nimrod responsibility. All Nimrod packet forwarding relies on the existence of underlying paths. This is true in both flow mode and datagram mode. ... For datagram mode, Nimrod need not install any session-specific state in any routers. Nevertheless, to forward a datagram, Nimrod may have to set up paths which will carry the datagram if no such paths already exist. You're using the word "path" here in your last sentence to describe what I though was actually a flow. I.e. in NDM (as I thought I understood it :-), datagram packets would be assigned to a sequence of valid flows, selected to form a path from the ultimate source to the ultimate destination; all datagram packets would at all times contain a valid flow-id, right? (By "valid flow-id", I mean one that is instantiated in the routers's flow database.) Are you proposing that we allow packets to include path-identifiers *or* flow-identifiers (perhaps with common syntax), or was that just some written shorthand? I normally think of a "path" as one of the 'attributes' of a flow (others might be resource allocations, etc), although some flows might have a path as their only major attribute. Even if no path setup is required for a datagram, datagram forwarding requires many of the same procedures as path setup, including selecting the next hop ... In fact, the only difference between datagram mode and flow mode is the establishment of session-specific state in the latter. If I understand what you are talking about here (actual forwarding of user datagram packets), what you're talking about with selection of the next hop only happens at the "active" routers in datagram mode; i.e. the routers which are the termination points of the sequence of flows/path I mentioned above, right? Intermediate routers along the path of the flow will handle the datagram packet the same way they would any other user data packet which was part of a user flow through the router. Hence, we refer to the protocol for setting up flows and for forwarding datagrams as "path setup". I think this terminology is going to cause confusion. Forwarding a datagram *might* require a setup, but it better not (on average), or datagram mode is going to have non-optimal performance. I tend to think of forwarding datagram traffic as much like forwarding flow traffic, not part of flow setup. The only difference between the two kinds of fowarding is that for datagram packets, the source has not assigned an end-end flow to the packet, but flow assignment is performed in a sequential manner in *some* of the routers as the packet traverses the network. Noel   Received: from PIZZA.BBN.COM by BBN.COM id aa19408; 17 Oct 94 13:33 EDT Received: from pizza by PIZZA.BBN.COM id aa29448; 17 Oct 94 12:59 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa29444; 17 Oct 94 12:57 EDT Received: from wd40.ftp.com by BBN.COM id aa15540; 17 Oct 94 12:43 EDT Received: from ftp.com by ftp.com ; Mon, 17 Oct 1994 12:40:37 -0400 Received: from mailserv-D.ftp.com by ftp.com ; Mon, 17 Oct 1994 12:40:37 -0400 Received: by mailserv-D.ftp.com (5.0/SMI-SVR4) id AA10468; Mon, 17 Oct 94 12:34:16 EDT Date: Mon, 17 Oct 94 12:34:16 EDT Message-Id: <9410171634.AA10468@mailserv-D.ftp.com> To: ramanath@BBN.COM Subject: Re: nimrod protocols From: Frank Kastenholz Reply-To: kasten@ftp.com Cc: amolitor@anubis.network.com, nimrod-wg@BBN.COM Content-Length: 1045 > DataSize = 11(32 + 3(320 + 8(6))) + 30(64) > = 14416 bytes. > > > How big is this? Is this considered small enough for a protocol message? > Can it be bounded? I think if n can be bounded, this can be too. messages over 1,000 or 1,500 bytes most likely will need to be fragmented. using ip fragmentation to break up the packet is a bad thing. you are much better off using some selective ack/retrans mechanism ala tcp (or even a simple lockstep protocol over udp ala tftp). if the performance and adaptability inherent in (good) tcps are critical, then use tcp. if you can do with a poorer level of performance, or less adaptability, a more lightweight protocol would be fine. another point to consider is that many routers contain a tcp implementation to support telnet for remote logins. it is feasible that tcp is already in all routers, in which case, the 'cost' of tcp is negligble (assuming that the tcp implementation is not 'crippled' to support _just_ one or two inbound telnet sessions). -- Frank Kastenholz   Received: from PIZZA.BBN.COM by BBN.COM id aa19701; 17 Oct 94 13:39 EDT Received: from pizza by PIZZA.BBN.COM id aa29530; 17 Oct 94 13:04 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa29524; 17 Oct 94 13:01 EDT Received: from ginger.lcs.mit.edu by BBN.COM id aa16078; 17 Oct 94 12:50 EDT Received: by ginger.lcs.mit.edu id AA24284; Mon, 17 Oct 94 12:50:42 -0400 Date: Mon, 17 Oct 94 12:50:42 -0400 From: Noel Chiappa Message-Id: <9410171650.AA24284@ginger.lcs.mit.edu> To: msteenst@BBN.COM, nimrod-wg@BBN.COM Subject: Re: Joel's response Cc: jnc@ginger.lcs.mit.edu From: jhalpern@newbridge.com (Joel Halpern) You are saying that the query/response protocol is how an endpoint finds the locator for another endpoint. Noel is saying that that is NOT the case. He specifically said that such as service is a bad idea. You're getting into an area here (endpoint names, and how to map them into core Nimrod concepts like locators, etc) which is sort of peripheral to Nimrod. Lacking agreement on what we are using for endpoint names (EID's, DNS names, or whatever), a question that is not as easy *or* as necesssary to answer (the latter because it *is* peripheral to Nimrod), expect some lack of finality. I think there *is* general agreement between Martha and I that to the extend you have an endpoint name which is *not* intended to be looked up in a distributed translation database (as EID's perhaps would not be, as opposed to DNS names, which are), you probably shouldn't try and start with that name, and translate it into something else (e.g. from an EID to a locator). *Generally* (things like IPv4 transition, and error analysis excepted), any time you need the locator, you *should* have the original "directory friendly" endpoint name (i.e. DNS), and you should start with that. Note that Martha's original note spoke of "endpoint names", not EID's, and Frank's note spoke of "EID's", not endpoint names. That part of why you get two different answers. However, this whole issue of endpoint names, and how to map from them, really is fairly peripheral to Nimrod, and may change depending on what happens outside. For instance, if the protocol family decide to use Nimrod for routing, it's going to have to figure out how to map from host-whatevers into Nimrod locators; we can't design Nimrod up front to handle that new use. So I'd say that this ->locator mapping issue can be kept to one side, to some degree. What am I missing? If such information is not tagged on the aggregated map, how will a remote entity know when to explode it. This general problem is one that clearly needs research before we try to say to much about it. May I suggest telepathy? Seriously, this is an unavoidable Catch-22. If you knew when you needed to expand a map, you probably wouldn't need to expand the map. I don't have any good answers either. In thinking about all these problems, I always go back to the road network model. In what circumstances do you go out and get detailed maps? Someone who knows of a back path may tell you about it, and you get a map to see. You may be exploring. You may need a detailed map to show the streets near your destination. Etc, etc. These situations probably have analogues in the network world. I really don't know how we will use Nimrod in the long run. All I know is that it gives us the flexibility, without carrying a substantial overhead for unused stuff, to explore all these things (how to do abstractions which discard data, etc) down the road, without massive upheaval. Noel   Received: from PIZZA.BBN.COM by BBN.COM id aa21593; 17 Oct 94 14:04 EDT Received: from pizza by PIZZA.BBN.COM id aa29809; 17 Oct 94 13:35 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa29805; 17 Oct 94 13:33 EDT Received: from quern.epilogue.com by BBN.COM id aa18880; 17 Oct 94 13:25 EDT From: Dave Bridgham Sender: dab@epilogue.com To: nimrod-wg@BBN.COM In-reply-to: Ram Ramanathan's message of Mon, 17 Oct 94 11:51:27 -0400 <9410171214.aa26415@quern.epilogue.com> Subject: nimrod protocols Date: Mon, 17 Oct 94 13:25:00 -0400 Message-ID: <9410171325.aa26950@quern.epilogue.com> Date: Mon, 17 Oct 94 11:51:27 -0400 From: Ram Ramanathan It seems to me that for most Nimrod protocol messages except the response for a map request, the data is not too large and could possibly be bounded to a single frame. It seems to me that I've been involved with too many protocols that made this limiting choice and it was a problem later. Dave   Received: from PIZZA.BBN.COM by BBN.COM id aa28151; 17 Oct 94 15:11 EDT Received: from pizza by PIZZA.BBN.COM id aa00526; 17 Oct 94 14:45 EDT Received: from TTL.BBN.COM by PIZZA.BBN.COM id aa00522; 17 Oct 94 14:41 EDT To: Greg Noel cc: nimrod-wg@BBN.COM Subject: Re: nimrod protocols (mobility) In-reply-to: Your message of Thu, 13 Oct 94 16:06:07 -0700. <199410132306.QAA22523@guru.qualcomm.com> Date: Mon, 17 Oct 94 14:43:24 -0400 From: Ram Ramanathan > Date: Thu, 13 Oct 1994 16:06:07 -0700 > From: Greg Noel > Message-Id: <199410132306.QAA22523@guru.qualcomm.com> > To: jnc@ginger.lcs.mit.edu, kasten@ftp.com > Cc: nimrod-wg@BBN.COM > Subject: Re: nimrod protocols > Content-Length: 2446 > > As I've read the drafts of the Nimrod specifications, it has seemed to > me that there are (at least) three different levels of mobility and > corresponding mappings to EID and locator. It may be that different > mechanisms are needed to deal with each type. > > As I think about it, there is a level of "mobility" where the typical > changes are measured in days. In some sense, this is where the entity > is registered for all to find, so it could be called the "registry" > lookup. This is the level at which DNS operates, and is the level at > which it makes sense to cache contact information on a longish basis. > > There's another level which has information about the current locator > for the endpoint; it might have a volatility measured from several > minutes to a couple of hours. One locator might be for when you are > at home, the other for when you are at work. > > The third level is when the location is extremely volatile, changing on > the order of a few seconds or even faster. The radio cells you pass > through on the freeway would be an example of this. Yes, I agree that the level of mobility influences, to a large extent, the mechanisms that are appropriate for it. The first two levels of mobility you mention could conceivably be handled by maintaining the endpoint-locator associations in the distributed database, without getting the "routing" involved. However, when we start getting into attachment point changes of the order of once in few seconds, mobility and routing cannot be disassociated. Routers must be actively involved in tracking mobility. This is not required for the first two levels. Another dimension of classification is whether networks move or not. In future, you are likely to have whole networks in trains, planes, hovercrafts etc. move. Routers in those networks will move, causing topology changes. This once again requires routing to become involved. Thus, another classification of mobility is whether routing is involved or a DNS like thing suffices. > > I think everybody agrees that there needs to be something at the registry > level. The debate is whether the registry mechanism is sufficient to > handle the demands at the other levels. > > I think it isn't. At the registry level, data should be valid for a > "long" time, so you should be willing to cache it or even broadcast it. > At the other levels, it's probably not worth this kind of investment. > > The middle level has to be tracked by the endpoints---if your locator > changes or your partner's locator changes, you need to be aware of it. > And if a locator changes, the last router for the old locator needs > to remember it (for a "short" time) so that it can send updates. > > But I believe the last level is something that should _not_ be a part > of Nimrod. Neither the last level nor the first two levels are "part" of Nimrod. The approach taken by the working group is that, as I mentioned above and as you also seem to be saying, what mechanisms to use for mobility handling depend on what the *requirements* are, and therefore, Nimrod does not specify any particular solution for mobility. Mobility is not a part of the core Nimrod architecture. What Nimrod does do, however, is to provide architectural hooks that enable your mechanism of choice to be grafted in. The approach is given in more detail in the Internet-Draft "Mobility Support for Nimrod : Requirements and Solution Approaches" (draft-ramanathan-mobility- 00.txt), by yours truly. In this draft, an example mechanism has been given, namely a version of IETF Mobile-IP adapted for Nimrod. This, I belive, can handle the first two mobility levels you defined, but not the third. > For that, you need a service provider that gives a "freeway" > locator at the middle level and tracks you internally. This is what > a cellular phone service does now---on the one side, provides a fixed > telephone number (middle-level locator) and delivers it to a rapidly- > moving mobile phone. The fact that Nimrod uses different namespaces for endpoints and locators makes it convenient for such a mechanism. For instance, a fast-moving endpoint, could give as its locator, the locator of an appropriate supercluster. Then, for all of Nimrod outside of that supercluster, the fast movement will not be "visible" and mobility will be reduced to level 2. Now, this kind of hierarchicalization (word coined for convenience) fits in well with the essence of Nimrod. > -- Greg -Ram. -------------------------------------------------------------- Ram Ramanathan Advanced Networking R & D BBN Systems and Technologies 10 Moulton Street, Cambridge, MA 02138 Phone : (617) 873-2736 INTERNET : ramanath@bbn.com   Received: from PIZZA.BBN.COM by BBN.COM id aa07365; 17 Oct 94 17:16 EDT Received: from pizza by PIZZA.BBN.COM id aa01579; 17 Oct 94 16:57 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa01575; 17 Oct 94 16:54 EDT Received: from ginger.lcs.mit.edu by BBN.COM id aa04528; 17 Oct 94 16:47 EDT Received: by ginger.lcs.mit.edu id AA26050; Mon, 17 Oct 94 16:46:31 -0400 Date: Mon, 17 Oct 94 16:46:31 -0400 From: Noel Chiappa Message-Id: <9410172046.AA26050@ginger.lcs.mit.edu> To: dab@epilogue.com, nimrod-wg@BBN.COM Subject: Re: nimrod protocols Cc: jnc@ginger.lcs.mit.edu From: Dave Bridgham It seems to me that I've been involved with too many protocols that made this limiting choice and it was a problem later. Excellent point. Unless it's really fairly short, and more or less guaranteed to stay that way (e.g. neighbour up/down probing, various kinds of requests) let's not assume it will stay that way. Noel   Received: from PIZZA.BBN.COM by BBN.COM id aa23317; 18 Oct 94 18:48 EDT Received: from pizza by PIZZA.BBN.COM id aa10492; 18 Oct 94 18:26 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa10488; 18 Oct 94 18:21 EDT Received: from guru.qualcomm.com by BBN.COM id aa21980; 18 Oct 94 18:17 EDT Received: (greg@localhost) by guru.qualcomm.com (8.6.9/QC-SOLARIS-2.1) id PAA16591; Tue, 18 Oct 1994 15:17:20 -0700 Date: Tue, 18 Oct 1994 15:17:20 -0700 From: Greg Noel Message-Id: <199410182217.PAA16591@guru.qualcomm.com> To: ramanath@BBN.COM Cc: nimrod-wg@BBN.COM Subject: Re: nimrod protocols (mobility) Content-Length: 10146 Ram Ramanathan says: > Yes, I agree that the level of mobility influences, to a large extent, > the mechanisms that are appropriate for it. The first two levels of > mobility you mention could conceivably be handled by maintaining the > endpoint-locator associations in the distributed database, without getting > the "routing" involved. However, when we start getting into attachment > point changes of the order of once in few seconds, mobility and routing > cannot be disassociated. Routers must be actively involved in tracking > mobility. This is not required for the first two levels. I disagree, but I think the disagreement is one of magnitude, not one of content. The distinction I am trying to draw in the first two levels is that at the first level, it's reasonable to keep the information in a widely-distributed database (as in, routinely distributed to a number of sites, potentially world-wide), while at the second level, the data is volatile enough (lifetime of a few minutes to a few hours) that it's not worth distributing widely. You seem to want to draw that line between the second and third examples. The distinction I am trying to draw between the second and third examples is that the rate of change is so great that it's likely to be impossible for the endpoints to be expected to handle it. (Perhaps not impossible; how about, "grossly inefficient.") Think of it this way: if the data packets are swamped by the routing updates, you'd like to do something that avoids the routing updates. It may be that the cut-point for routers to be involved is not the same as the cut-point for data not to be distributed. If so, there are more than the three levels I identified. (And calling them "levels" may be prejudicial; they may not stack.) I don't think that changes the point. > Another dimension of classification is whether networks move or not. > In future, you are likely to have whole networks in trains, planes, > hovercrafts etc. move. Routers in those networks will move, causing > topology changes. This once again requires routing to become involved. > Thus, another classification of mobility is whether routing is involved > or a DNS like thing suffices. Um, I don't think this is a different dimension; it just means that there can be more than one "second level" in the locator. But notice that this implies an architectural requirement: second-level entities need to be able to communicate. > Neither the last level nor the first two levels are "part" of Nimrod. > The approach taken by the working group is that, as I mentioned above > and as you also seem to be saying, what mechanisms to use for mobility > handling depend on what the *requirements* are, and therefore, Nimrod > does not specify any particular solution for mobility. Mobility is not > a part of the core Nimrod architecture. What Nimrod does do, however, > is to provide architectural hooks that enable your mechanism of choice > to be grafted in. Yeah, but what are the hooks? How do they allow the players to play? In fact, who are the players? That's where I was going in my note: Nimrod is going to provide hooks for certain players; how do we know that they are the right players? In other words, Nimrod will have a model of which players will be interacting based upon its requirements; I am trying to make that model explicit by identifying the players. If we can agree that all the players are present, we can avoid questions like this (I don't know who wrote it): > ... are you expecting that in deploying nimrod we also > deploy a revised dns system that allows for large-scale, dynamic, > rapid, updates? This was making the assumption that the more volatile level-two updates must be widely distributed. The answer was, effectively, that only the partners in the association need this level of detail, and they can talk to one another about it. Do I buy that the endpoint-endpoint updates are necessary? Yes, mostly. Do I buy that they are _all_ that is needed (in addition to a DNS-like system for the initial contact)? Well, no, not really---there's some second-level machinery needed, too. But without some agreement on the identity of the players (who is that second baseman? No, Who's on first), these discussions quickly bog down. And this sort of confusion happens a _lot_. > The approach is given in more detail in the Internet-Draft "Mobility Support > for Nimrod : Requirements and Solution Approaches" (draft-ramanathan-mobility- > 00.txt), by yours truly. In this draft, an example mechanism has been > given, namely a version of IETF Mobile-IP adapted for Nimrod. This, I > belive, can handle the first two mobility levels you defined, but not > the third. And again, I emphasize that the third level should _not_ be a part of Nimrod; that it specifically should be permanently excluded; and that the requirement placed on the service provider be that it hides that degree of motion and only "looks like" a second-level redirection entity. There will always be a point where a specific solution, highly tuned for a particular environment, will be necessary. If you are driving down the street going through two or three PCN cells per second, you want your cellular provider to make that invisible to the other entities. > The fact that Nimrod uses different namespaces for endpoints and locators > makes it convenient for such a mechanism. For instance, a fast-moving > endpoint, could give as its locator, the locator of an appropriate > supercluster. Then, for all of Nimrod outside of that supercluster, the > fast movement will not be "visible" and mobility will be reduced to level > 2. Now, this kind of hierarchicalization (word coined for convenience) > fits in well with the essence of Nimrod. Exactly my point. But I contend that Nimrod should identify the engineering trade-off of when it is necessary to go to this "supercluster" mechanism, and then say, "Nimrod doesn't care and will never ask how it works internally, but does place these requirements on the interface." So let's revisit the levels: Locator mobility occurs in (at least) three different levels. The "registry" level is the more-or-less permanent home for the endpoint; the "redirection" level is where most motion takes place; and the "provider" level is where high-speed motion can take place. As I see it, the registry level operates by mapping a name into a locator/EID. This is the primary locator for the EID and the registry is effectively guaranteeing that the locator will be valid as long as the name is valid---this is the same guarantee that DNS provides for IP addresses now. At the redirection level, a locator/EID can be mapped into a "more current" locator, either by an explicit request or by implicitly sending traffic to that locator/EID. In the latter case, the router does two things: it unreliably returns the new locator to the sender and it unreliably forwards the traffic via the new locator. Redirection levels are stackable---it is possible for there to be more than one redirection level in a locator. As far as Nimrod is concerned, the provider level looks like, at worst, a redirection level---it is the intent that this kind of level can use whatever local mechanism is necessary to hide the rapid motion from the other levels. (If it is the case that the registry-level lookup knows the current locator for the the endpoint, it can provide it as a hint in the initial query; this hint would have the same lifetime as a redirection-level locator. This is the sort of optimization you can now talk about with the players better identified---DNS is becoming "turbocharged" to use the Nimrod protocol for a class of association updates.) This gives us three major entities with which we must be concerned, which I'll call endpoints, registries, and relocators. In this model, the two endpoints of the connection are responsible for noticing when their locator has changed and notifying the other end; the router for the old locator simply provides belt-and-suspenders robustness (think of the case where a connection is not yet fully established). The endpoint is also responsible for notifying its registry of its current locator. This is my interpretation of Noel's thinking. So these are the players. Assuming that each can be either the source or destination of a message, there are at most 2^3 = 8 partners. And, without getting overly-specific, you can talk about the messages that have to be exchanged between each partner; these are the hooks. Here are some of the possible message patterns: o A message from an endpoint to a registry, requesting the locator/EID of another endpoint. o Is there a message that a registry might spontaneously send to an endpoint? Maybe an "are you there"? o A message from a relocator going "down the locator" to tell the lower-level entity (relocator or endpoint) that it is about to be relocated. o Is there a corresponding message that needs to go "up the locator"? o A message from an endpoint to its registry, notifying it of its new current locator. Is this going beyond the scope of Nimrod? I don't think so; we're not saying how it should be done or making any policy decisions about routing, we're merely looking at what information has to be passed so we can identify the hooks needed to exchange the data. Are these all the possible partners? I don't know, but I don't remember any discussion that needed something else. (On the other hand, I tend to think of a relocator as a router; it might be more useful to separate the roles. And is a map source more than just a specialized endpoint?) Let me emphasize my basic point again: there's confusion about who is playing what part. If we can clarify the players, we can focus on questions such as "are all the players present---is there something that needs doing that the players can't do?" or "are these players too specialized---can we distribute the roles differently so that the players are more generic?" Personally, I find the discussions around points like those much more enlightening. -- Greg   Received: from PIZZA.BBN.COM by BBN.COM id aa00729; 24 Oct 94 14:20 EDT Received: from pizza by PIZZA.BBN.COM id aa14610; 24 Oct 94 14:00 EDT Received: from BBN.COM by PIZZA.BBN.COM id aa14606; 24 Oct 94 13:56 EDT Received: from ginger.lcs.mit.edu by BBN.COM id aa28659; 24 Oct 94 13:51 EDT Received: by ginger.lcs.mit.edu id AA04200; Mon, 24 Oct 94 13:51:53 -0400 Date: Mon, 24 Oct 94 13:51:53 -0400 From: Noel Chiappa Message-Id: <9410241751.AA04200@ginger.lcs.mit.edu> To: greg@qualcomm.com, ramanath@BBN.COM Subject: Re: nimrod protocols (mobility) Cc: jnc@ginger.lcs.mit.edu, nimrod-wg@BBN.COM From: Greg Noel > when we start getting into attachment point changes of the order of once > in few seconds, mobility and routing cannot be disassociated. Routers > must be actively involved in tracking mobility. The way I look at this question is to look at the topological scope over which the mobile entity is moving, and the number of entities with which the mobile entity is communicating. These two are the principle terms in the cost functions for two major methods of handling mobility, viz: - i) let the routing do it, with a fixed "name" for the mobile entity, which the routing tracks, to keep the entities on the other end out of the grubby details (where scope is important) - ii) let the entities on the other end do it, using a new "name" which reflects the changed location, to keep the routing out of the grubby details (where the number of entities is important) Depending on the answers, one approach or another may make sense. I.e. a thing which is moving over a small scope, with lots of remote respondents, maybe you do that in the routing. Something moving widely, with few respondents, probably you put the burden on the ends. There's also the "base-station" approach, which makes things even more complicated. That approach doesn't have either of those costs, but you get the costs of triangle routing instead. This may be acceptable, if the change rate is high compared with the data rate; the costs of extra traffic due to triangle routing may be lower than the costs of traffic due to updates. at the first level, it's reasonable to keep the information in a widely-distributed database ... while at the second level, the data is volatile enough ... that it's not worth distributing widely. In some sense, these are simply subflavors of the "notify the other ends" approach. (Of course, if you have the routing support mobilty, you can view that as updating databases over various scopes, and at various rates, as well.) In fact, probably "rate of mobility" is a term in the cost function of *any* of these approaches to supporting mobility, but it probably has the effect of causing you to prefer solutions which limit the scope over which information must flow, as the rate of mobility increases. The distinction I am trying to draw between the second and third examples is that the rate of change is so great that it's likely to be impossible for the endpoints to be expected to handle it ... if the data packets are swamped by the routing updates, you'd like to do something that avoids the routing updates. There's no way to get rid of "routing updates" entirely, the only question is "who are they going to". If the data packets going to the ends are outnumbered by updates, so you send the updates somewhere else, you're still going to have that many updates, it's just somebody else's problem now. With most routing architectures, which are distributed algorithms, putting that kind of data rate into them is fairly expensive; each update cases a distributed computation, with attendant packet traffic to mesh the separated parts of the computation together. It's only when the scope is small (so the routing cost is small), and the number of endpoints large, that the overall cost of doing it in the routing works out smaller. Again, if neither of those looks good, then you have to look at base-station approaches. > Mobility is not a part of the core Nimrod architecture. Hmm. To the extent that the solution is "notify the endpoints" (*either* by updating the DNS, or by explicit notification via a redirect), I guess I'd agree. To the extent that the solution is local mobility in the routing, I have a mixed reaction. It need not be specified as part of Nimrod, since in Nimrod a given scope can deploy whatever local routing mechanism it wants; this could be a mechanism which supports mobility in the routing. However, if this approach to mobility is going to be common, it would be nice to provide built-in support for it. To the extent that it's a base-station approach, I'm not sure. Nimrod is in some sense just a "routing and addressing" architecture, but it also does have strong "forwarding" component (e.g. with NDM). So, in some sense, it is taking responsibility for getting the user traffic where it wants to go. If you think of base-station as part of "getting the user traffic where it wants to go", then maybe base-station is part of Nimrod too. At the redirection level, a locator/EID can be mapped into a "more current" locator, either by an explicit request or by implicitly sending traffic to that locator/EID. In the latter case, the router does two things: it unreliably returns the new locator to the sender and it unreliably forwards the traffic via the new locator. You've made the routers into "redirecting base-stations" here, which I guess is really a "notify the endpoints" mechanism, now that I think about it. It just had a "base-station" feel when I first looked at it. In this model, the two endpoints of the connection are responsible for noticing when their locator has changed and notifying the other end; the router for the old locator simply provides belt-and-suspenders robustness (think of the case where a connection is not yet fully established). The endpoint is also responsible for notifying its registry of its current locator. This is my interpretation of Noel's thinking. You have it more or less exactly, although I hadn't added the bit with the routers (perhaps on the same physical network as the destination used to be, or perhaps at a higher level, on responsible for advertising an abstraction the mobile entity used to be part of) providing forwarding pointers temporarily. Not that I'm saying that's a bad idea, it's just that it has costs and benfits, and I don't have a good idea of how they balance. The costs are more state in the routers, more complexity, perhaps a modest amount more (e.g. how does a router decide when to stop carrying a hint for the new location), etc, etc. The benfits are that in some cases (when the DNS has not been updated) you can find someone you otherwise wouldn't be able to. Another benefit is that if a site moves temporarily, it might be cheaper to do it via this, than by updating the DNS. How do these balance? Not sure. In general (I'm sure Steve Deering may not believe this :-), I am very reluctant to add complexity unless I'm sure it is needed. Is this going beyond the scope of Nimrod? I don't think so; we're not saying how it should be done or making any policy decisions about routing, we're merely looking at what information has to be passed so we can identify the hooks needed to exchange the data. Yeah, I can see the point here. To the extent that "getting the user traffic where it wants to go" is the job of Nimrod, then maybe it is in Nimrod's scope. Now that I think about it, that definition makes me nervous, though; that, in some sense, if the definition of the internetwork layer as a whole. Clearly the routing is a very key part of that layer, but there's more to that layer. Still, I can see a case that mobility mechanisms need to be fully worked out *in conjunction* with the routing; what each needs, and can do, will effect the other. However, *all* the mechanisms of the internetwork layer need to interoperate effectively, so this is just one more case of that. What this leads me to think is that the further away from the "core" subsystems of Nimrod (which to me are the naming, map distribution, etc), we get, the more we will have a "work in progress" which will have to evolve as the rest of the internetwork layer does. Hmm. If we can clarify the players, we can focus on questions such as "are all the players present---is there something that needs doing that the players can't do?" or "are these players too specialized---can we distribute the roles differently so that the players are more generic?" I would restate this in terms of system-design jargon like division into sub-systems, and functional modularity boundaries, etc (and I did in section 3.1* of the "Nimrod IPng" document), but it comes to the same thing. The key part of any design is deciding what service model your system (the internetwork layer, in our case) wants to provide, and how you split it up into pieces, and how those pieces communicate. What we seem to be doing now is iterating those second and third steps, based on the design, and understanding, we have so far. That's not a bad thing. Noel   Received: from PIZZA.BBN.COM by BBN.COM id aa19952; 29 Nov 94 12:09 EST Received: from pizza by PIZZA.BBN.COM id aa15194; 29 Nov 94 11:42 EST Received: from KARIBA.BBN.COM by PIZZA.BBN.COM id aa15190; 29 Nov 94 11:38 EST To: nimrod-wg@BBN.COM Subject: IETF31 Agenda Date: Tue, 29 Nov 94 11:40:21 -0500 From: Isidro Castineyra IETF31: San Jose, California. December 5-9 1994 Group Name: Nimrod - The New Internet Routing and Addressing Architecture IETF Area: Routing Date/Time: Wednesday, December 7, 1994 0930-1200 Thursday, December 8, 1994 0930-1200 Proposed Agenda -- First Session 1. Agenda bashing/Announcements 5min 2. Introduction: Nimrod Components 15min (Isidro Castineyra) 3. Nimrod Database Naming System 15min (Isidro Castineyra) 4. External Data Representation 30min (Isidro Castineyra) 5. Discovery Protocol 30min (Isidro Castineyra) 6. Hierarchical Update Protocol 30min (Ram Ramanathan) Proposed Agenda -- Second Session 7. Hierarchical Query/Response Protocol 30min (Ram Ramanathan) 8. Path Setup/Teardown Protocol 30min (Martha Steenstrup) 9. Transition Plan 30min (Charlie Lynn) 10. Reliable Transport Protocol 15min (Charlie Lynn) 11. Open Issues and Work Plan 15min   Received: from PIZZA.BBN.COM by BBN.COM id aa18820; 13 Dec 94 10:30 EST Received: from pizza by PIZZA.BBN.COM id aa04378; 13 Dec 94 10:02 EST Received: from KARIBA.BBN.COM by PIZZA.BBN.COM id aa04374; 13 Dec 94 9:58 EST To: nimrod-wg@BBN.COM Subject: Representational Variants Date: Tue, 13 Dec 94 10:01:15 -0500 From: Isidro Castineyra At the end of San Jose's IETF Thursday's session we made a list of four architectural variants we would consider. This message lists these options, plus one more that Ram pointed out. Terminology, and a brief discussion follow after the list. Architectural/representational variants: I. Multipoint arcs with attributes + nodes with abstract maps and no connectivity specs. II. Unidirectional arcs with attributes + nodes with "simple" connectivity specs and abstract maps. III. Adjacencies + nodes with "complicated" connectivity specs and *no* abstract maps. IV. Adjacencies + nodes with "simple" connectivity specs and abstract maps. V. Unidirectional arcs with attributes + nodes with "complicated" connectivity specs (no abstract maps). ---------------- Terminology: Adjacencies: unidirectional arcs without attributes. Complicated/Simple connectivity specs: a connectivity spec associated with a node is simple if it holds between the heads of any incoming arc and the head of any outgoing arc; it is said to be "complicated" if it holds only between a subset of (head incoming arc, head outgoing arc) pairs. Detailed/Abstract maps: a detailed (or real) map is one in which every node is a "real" node: it represents a region of the physical network. A real node's locator is a valid destination address for a nimrod packet; also, the locator of a real node can be the answer given by the EID-to-locator mapping. An abstract map, on the other hand, has "fake" nodes: nodes that are mostly repositories for connectivity specs. There are no EIDs that can be reached by sending a packet whose destination is a fake node's locator. I am assuming that nodes always contain real maps. Arcs attributes: typically, simple connectivity specifications. --------------- The architecture/database as presented at the IETF meeting corresponds to option III. As it seems that I am the only one that likes multipoint arcs, I am going to ignore option I. (But note that a fake node with simple connectivity specifications is equivalent to a multipoint arc.) That leaves us with four options that are really two orthogonal questions: 1.- Should we use either complicated connectivity specifications with only real maps; or simple connectivity specifications together with both real and abstract maps. (In principle, two more choices could be added to the second question: a. Complicated connectivity specifications *and* abstract maps. b. Simple connectivity specifications and *no* abstract maps. Choice "a" seems redundant. Choice "b" seems not powerful enough. So I am going to ignore these two options, but let me know if you can find a reason to consider them.) 2.- Should arcs have attributes? If fake nodes are allowed, attributes on arcs can be considered as syntactic sugar as arcs with attributes are equivalent to two arcs with a fake node that holds the attributes. I suggest that we address these two question separately, if possible, and that we first address the first one, leaving attributes on arcs for later. Fire away... Isidro   Received: from PIZZA.BBN.COM by BBN.COM id aa21817; 13 Dec 94 11:09 EST Received: from pizza by PIZZA.BBN.COM id aa04516; 13 Dec 94 10:32 EST Received: from KARIBA.BBN.COM by PIZZA.BBN.COM id aa04512; 13 Dec 94 10:29 EST To: nimrod-wg@BBN.COM Subject: Copies of IETF Slides Date: Tue, 13 Dec 94 10:32:26 -0500 From: Isidro Castineyra At Noel's request, I am enclosing an ascii version of the slides I used during the IETF meeting. Isidro -------------- Agenda Group Name: Nimrod - The New Internet Routing and Address- ing Architecture IETF Area: Routing Date/Time: Wednesday, December 7, 1994 0930-1200 Thursday, December 8, 1994 0930-1200 Proposed Agenda -- First Session 1. Agenda bashing/Announcements 5min (Isidro Castineyra) 2. Introduction: Nimrod Components 15min (Isidro Castineyra) 3. Nimrod Database 15min (Isidro Castineyra) 4. External Data Representation 30min (Isidro Castineyra) 5. Discovery Protocol 30min (Isidro Castineyra) 6. Hierarchical Update Protocol 30min (Ram Ramanathan) Nimrod's Components 1 December 1994 Agenda II Proposed Agenda -- Second Session 7. Hierarchical Query/Response Protocol 30min (Ram Ramanathan) 8. Path Setup/Teardown Protocol 30min (Martha Steenstrup) 9. Transition Plan 30min (Charlie Lynn) 10. Reliable Transport Protocol 15min (Charlie Lynn) 11. Open Issues and Work Plan 15min Nimrod's Components 2 December 1994 Nimrod Components 1. Database (a) Organization (b) Naming Scheme (c) External Data Representation 2. Protocols (a) Discovery (b) Hierarchical Update (c) Reliable Transport (d) Hierarchical Query/Response (e) Hierarchical Path Setup/Teardown 3. Transition Plan Nimrod's Components 3 December 1994 Nimrod Features o Representation of internetwork connectivity and services at multiple levels of abstraction. o Localized route generation based on "maps" and service requirements. o Source-directed and destination-directed packet forwarding along "flows." o Separate spaces to identify "what," "where," and "how to get there." Nimrod's Components 4 December 1994 Maps o Network information used for routing is organized as Maps. o A map expresses the available connectivity between different points of a network. o Different maps can represent the same region of a physical network at different levels of detail. o A map is a graph composed of nodes and arcs. Nimrod's Components 5 December 1994 Connectivity Specifications By connectivity between two points we mean the available services and the restrictions on their use. The following are 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 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 and is destined to research organizations." Nimrod's Components 6 December 1994 Nodes o A node represents a connected region of the physical network. o The region of the network represented by a node can be as large or as small as desired. o Properties of nodes are contained in attributes associated with them. Nimrod's Components 7 December 1994 Arcs o Arcs are unidirectional. o Arcs have no attributes. o 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. o Between two given nodes, there can be only one arc in each direction. Arcs always connect different nodes. Nimrod's Components 8 December 1994 Locators o The distinguishable components of a map are called basic topological entities (BTEs): nodes, arcs, and connectivity specifications. o A locator is a string of binary digits that identifies a BTE in a map. Different BTEs have necessarily different locators. A given BTE is assigned only one locator. o Locators specify where a BTE is in the network. o If where you are in the network changes, your locator changes. You cannot take your locator with you. o A locator does not specify a route to the BTE. o A given physical element of the network might implement more than one BTE---for example, a router that is part of two different nodes. o All routing map information is expressed in terms of locators; routing selections are based on locators. EIDs are not used in making Nimrod routing decisions. Nimrod's Components 9 December 1994 Locators II o The locator of an arc is prefixed by the locator of the node attached to the tail of the arc (the node the arc "leaves"). o Nimrod requires locators sharing a prefix to be assigned to a contiguous region of the network. o Two elements of the network that have been assigned locators that share a prefix should be connected to each other with elements that themselves have been assigned locators with that prefix. Nimrod's Components 10 December 1994 Internal Maps o As part of its attributes, a node can have internal maps. o 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. o 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. o The nodes of this map can themselves have detailed maps. Nimrod's Components 11 December 1994 Other Node Attributes o Transit Connectivity: This attribute specifies the services available between the heads of arcs arriving to that node and the heads of arcs leaving that node. o Inbound Connectivity: This attribute represents connectivity from arcs impinging on the node to the inside of the node. o Outbound Connectivity: This attribute represents connectivity from the inside of the node to the head of arcs leaving the node. These attributes have locators that are prefixed by the node's locator. Nimrod's Components 12 December 1994 Database Definition o Specification of the database structure and of the naming system. Names are used, for example, to request elements of the database. o Specification of a flexible "type" system. For example, it should be possible to interoperate implementations that do not understand the same set of connectivity specifications. o Specification of an external representation. 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. o Specification of simple a query language. o Efficiency is of the essence: it should be nice to be able to "just lay the packet in memory." Nimrod's Components 13 December 1994 Database Elements o Arcs o Nodes o Maps o Connectivity Specifications Nimrod's Components 14 December 1994 arc 1. Locator of the arc; 2. Locator of the arcs's destination node; Nimrod's Components 15 December 1994 Node 1. Locator of the node; 2. Set of outgoing arcs; 3. Internal map; 4. Set of transit connectivity specifications; 5. Set of incoming connectivity specifications; 6. Set of outgoing connectivity specifications; Nimrod's Components 16 December 1994 Map 1. Set of node locators; 2. Set of arcs; Nimrod's Components 17 December 1994 Connectivity Specification 1. Locator; 2. type; 3. Set of input arc locators; 4. Set of output arc locators; 5. performance specification; 6. Policy restrictions: Nimrod's Components 18 December 1994 Query Language: What information can be requested o Partial maps: nodes and arcs (topology). o Complete maps: includes attributes of all nodes. o Specific attributes of specific nodes. For example, o List of arcs; o Transit connectivity; o Outgoing connectivity; o Incoming connectivity; Nimrod's Components 19 December 1994 Undefined Elements o Locators; o Connectivity specification type; o Performance specification; o Policy restrictions; Nimrod's Components 20 December 1994 External Representation o Every element sent as a (type, length, value) triple. o Representation Based on RFC 1014. Nimrod's Components 21 December 1994 To be Specified o Locator external representation: 1. Can the hierarchical structure of a locator be inferred from its representation? 2. Is there a single representation for locators? o Performance specification and representation: how to characterize performance guarantees and how to represent these externally. o Policy representation. Nimrod's Components 22 December 1994   Received: from PIZZA.BBN.COM by BBN.COM id aa11240; 13 Dec 94 14:41 EST Received: from pizza by PIZZA.BBN.COM id aa05743; 13 Dec 94 14:07 EST Received: from BBN.COM by PIZZA.BBN.COM id aa05739; 13 Dec 94 14:02 EST Received: from ginger.lcs.mit.edu by BBN.COM id aa07737; 13 Dec 94 13:55 EST Received: by ginger.lcs.mit.edu id AA28162; Tue, 13 Dec 94 13:54:43 -0500 Date: Tue, 13 Dec 94 13:54:43 -0500 From: Noel Chiappa Message-Id: <9412131854.AA28162@ginger.lcs.mit.edu> To: isidro@BBN.COM, nimrod-wg@BBN.COM Subject: Re: Representational Variants Cc: jnc@ginger.lcs.mit.edu From: Isidro Castineyra As it seems that I am the only one that likes multipoint arcs, I am going to ignore option I. (But note that a fake node with simple connectivity specifications is equivalent to a multipoint arc.) ... 2.- Should arcs have attributes? If fake nodes are allowed, attributes on arcs can be considered as syntactic sugar as arcs with attributes are equivalent to two arcs with a fake node that holds the attributes. I suggest that we address these two question separately, if possible, and that we first address the [other] one, leaving attributes on arcs for later. I'm not actually sure there is any disagreement here any more, or any question to settle. What I thought I heard at the WG meeting was general agreement that the ultimate basic entities should be "meta-nodes" (a word chosen to avoid existing meanings in people's minds) which can have attributes, and adjacancies (unidirectional, as you mentioned). In this model, an arc with attributes, is, as you suggest, simply a meta-node with those attributes, and the adjacencies which are needed to represent the connectivity of the arc. (The meta-node could be marked as an "arc" meta-node if there was any need to restrict its properties to those you think of as being associated with an arc.) A multi-point arc is also easy to provide; as you indicated, it's a meta-node with numerous adjacencies. The things you now think of as "nodes" could similarly be meta-nodes with an attribute that restricts their properties to the subset you now think of as being associated with nodes. I'm particularly happy with this model, since if you look at how things like arcs with attributes, or multi-point arcs, etc, would actually inevitably be *represented* and *stored*, they *always* look like metanodes (structures of memory cells) and adjacencies (pointers), since those are what our information technology has settled on as basic elements. I expect that we will find practical uses for both arcs with adjacencies (e.g. point-point lines) as well as multi-point arcs (e.g. Ethernets), from the users' point of view. However, inside, it will all be metanodes and adjacencies. (Inevitably, I suspect, we'll wind up calling these "nodes" and "arcs" again! :-) I don't see that there's anything to be lost, in either simplicity or efficiency, from using this basic model (as opposed to making either arcs-with-attributes or multi-point-arcs basic building blocks). Processing of, say, a multi-point-arc meta-node should be just as efficient as processing of a multi-point-arc fundamental object, no? Did I miss anything? I know that this can be seen as either i) putting off the question of what representation to use for another day, or ii) allowing everyone to have their own preferred brand of cake, but I don't think so. I'm actually of the opinion that the former is good, since I think our knowledge and experience is so slender that that kind of flexibility is an advantage (provided, of course, that it is obtained with no loss of efficiency, as I am convinced it is). This is a separate question from your first question, which is whether the attributes of metanodes are "simple" (i.e. apply to all adjacency:adjacency pairings), or "complex". That's one we're going to have to hash out, since it *does* have efficiency, etc, considerations. Noel   Received: from PIZZA.BBN.COM by BBN.COM id aa12428; 13 Dec 94 14:57 EST Received: from pizza by PIZZA.BBN.COM id aa05874; 13 Dec 94 14:29 EST Received: from KARIBA.BBN.COM by PIZZA.BBN.COM id aa05870; 13 Dec 94 14:27 EST To: Noel Chiappa cc: nimrod-wg@BBN.COM Subject: Re: Representational Variants In-reply-to: Your message of Tue, 13 Dec 94 13:54:43 -0500. <9412131854.AA28162@ginger.lcs.mit.edu> Date: Tue, 13 Dec 94 14:29:55 -0500 From: Isidro Castineyra Noel, >>I'm not actually sure there is any disagreement here any more, or >>any question to settle. What I thought I heard at the WG meeting was >>general agreement that the ultimate basic entities should be >>"meta-nodes" (a word chosen to avoid existing meanings in people's >>minds) which can have attributes, and adjacancies (unidirectional, >>as you mentioned). It is hard to gauge agreement in real time at the working group. So, I sent the "Representational Variants" message to make sure that we have everybody on board. I really don't want to go through this again. >>In this model, an arc with attributes, is, as you suggest, simply a >>meta-node with those attributes, and the adjacencies which are >>needed to represent the connectivity of the arc. (The meta-node >>could be marked as an "arc" meta-node if there was any need to >>restrict its properties to those you think of as being associated >>with an arc.) A multi-point arc is also easy to provide; as you >>indicated, it's a meta-node with numerous adjacencies. >>The things you now think of as "nodes" could similarly be meta-nodes >>with an attribute that restricts their properties to the subset you >>now think of as being associated with nodes. >> >>I expect that we will find practical uses for both arcs with >>adjacencies (e.g. point-point lines) as well as multi-point arcs >>(e.g. Ethernets), from the users' point of view. However, inside, it >>will all be metanodes and adjacencies. (Inevitably, I suspect, we'll >>wind up calling these "nodes" and "arcs" again! :-) I agree that the combination of meta-nodes and adjacencies allow us to have all the things we want. Though I find it useful to keep the different things (arcs, strict-nodes, multi-point arcs) separate in my mind. I also believe that we will end-up talking about arcs, nodes, etc. >>I'm particularly happy with this model, since if you look at how >>things like arcs with attributes, or multi-point arcs, etc, would >>actually inevitably be *represented* and *stored*, they *always* >>look like metanodes (structures of memory cells) and adjacencies >>(pointers), since those are what our information technology has >>settled on as basic elements. This is where I get uncomfortable. If we like metanodes because they are a useful concept that helps us to think and organize things, I am happy to adopt them. If the motivation for metanodes is that they make the architecture closer to the way we would implement, I will be less happy. I suspect, and hope, that both of these will be the case: i.e., metanodes useful when thinking about things and when we start implementing. >>This is a separate question from your first question, which is >>whether the attributes of metanodes are "simple" (i.e. apply to all >>adjacency:adjacency pairings), or "complex". That's one we're going >>to have to hash out, since it *does* have efficiency, etc, >>considerations. Let's deal with that one next (like... soon). Thanks, Isidro   Received: from PIZZA.BBN.COM by BBN.COM id aa16637; 13 Dec 94 15:38 EST Received: from pizza by PIZZA.BBN.COM id aa06217; 13 Dec 94 15:13 EST Received: from BBN.COM by PIZZA.BBN.COM id aa06213; 13 Dec 94 15:11 EST Received: from ginger.lcs.mit.edu by BBN.COM id aa12859; 13 Dec 94 15:02 EST Received: by ginger.lcs.mit.edu id AA29026; Tue, 13 Dec 94 15:02:19 -0500 Date: Tue, 13 Dec 94 15:02:19 -0500 From: Noel Chiappa Message-Id: <9412132002.AA29026@ginger.lcs.mit.edu> To: isidro@BBN.COM, jnc@ginger.lcs.mit.edu Subject: Re: Representational Variants Cc: jnc@ginger.lcs.mit.edu, nimrod-wg@BBN.COM From: Isidro Castineyra It is hard to gauge agreement in real time at the working group. So, I sent the "Representational Variants" message to make sure that we have everybody on board. I really don't want to go through this again. Good point! This is where I get uncomfortable. If we like metanodes because they are a useful concept that helps us to think and organize things, I am happy to adopt them. If the motivation for metanodes is that they make the architecture closer to the way we would implement, I will be less happy. I suspect, and hope, that both of these will be the case: i.e., metanodes useful when thinking about things and when we start implementing. I personally have both of these motivations; it is the simplest and most flexible model, and it is the one that will be closest to actual implementations. (I'm not tied to the term "meta-node", I just used it to distinguish from the "nodes" we have been talking about heretofore. Call them whatever you want!) I wouldn't be so quick to discount the worth of a model which is a close match to implementation; I think that you will find that with the average person out there in network-land, who likes to think in very concrete terms (packet formats and the like), it will be a big plus to have something they can easily visualize in concrete terms. (Says Noel, thinking down the road to the "selling job" which Martha has stuck him with! :-) > first question, which is whether the attributes of metanodes are > "simple" ... or "complex". That's one we're going to have to hash out Let's deal with that one next (like... soon). Yup. Someone (Martha?) was going to explain why complex nodes make for more efficient path-selection algorithms than abstract maps, which is something I need to understand better. Noel   Received: from PIZZA.BBN.COM by BBN.COM id aa17583; 13 Dec 94 15:52 EST Received: from pizza by PIZZA.BBN.COM id aa06300; 13 Dec 94 15:26 EST Received: from BBN.COM by PIZZA.BBN.COM id aa06296; 13 Dec 94 15:24 EST Received: from ginger.lcs.mit.edu by BBN.COM id aa13607; 13 Dec 94 15:13 EST Received: by ginger.lcs.mit.edu id AA29183; Tue, 13 Dec 94 15:13:32 -0500 Date: Tue, 13 Dec 94 15:13:32 -0500 From: Noel Chiappa Message-Id: <9412132013.AA29183@ginger.lcs.mit.edu> To: isidro@BBN.COM, nimrod-wg@BBN.COM Subject: Re: Copies of IETF Slides Cc: jnc@ginger.lcs.mit.edu From: Isidro Castineyra At Noel's request, I am enclosing an ascii version of the slides I used during the IETF meeting. The point here is that people should go through these, and if they see anything they wildly disagree with, they should point them out. Noel   Received: from PIZZA.BBN.COM by BBN.COM id aa28138; 14 Dec 94 6:25 EST Received: from pizza by PIZZA.BBN.COM id aa10456; 14 Dec 94 6:11 EST Received: from BBN.COM by PIZZA.BBN.COM id aa10452; 14 Dec 94 6:09 EST Received: from SUNIC.SUNET.SE by BBN.COM id aa27808; 14 Dec 94 6:12 EST Received: from alfa.camk.edu.pl by sunic.sunet.se (8.6.8/2.03) id MAA04200; Wed, 14 Dec 1994 12:11:55 +0100 From: Rafal_Pietrak@camk.edu.pl MMDF-Warning: Parse error in original version of preceding line at BBN.COM Received: from marvin.camk.edu.pl by alfa.camk.edu.pl (5.65b/RP-1.3) id AA17400; Wed, 14 Dec 94 12:14:03 +0100 Message-Id: <9412141114.AA17400@alfa.camk.edu.pl> Received: by marvin.camk.edu.pl (NX5.67d/NX3.0X) id AA19061; Wed, 14 Dec 94 12:14:04 +0100 Date: Wed, 14 Dec 94 12:14:04 +0100 Received: by NeXT.Mailer (1.95.RR) Received: by NeXT Mailer (1.95.RR) To: Isidro Castineyra Subject: Re: Representational Variants Cc: nimrod-wg@BBN.COM Hi, I'm not a member of the WG; still, I'd like to make a comment related to the subject. Reading the nimrod architecture draft I had an impression, that arcs of the network topology map are defined as _logical_ entities, i.e. indicating (possible) traffic, not connectivity. The document says: "The presence of an arc between two nodes specifies that traffic can flow between those two points in the direction indicated by the arc.". This suggests that these maps are used for traffic flow optimization, not for connectivity setup and maintenance. If the later was intended, I wonder whether saying, that "arcs represent physical network interfaces" changes the intended meaning. Actually, I've read the rest of the document with such assumption, namely: arcs: are physical interfaces with heads pointing towards the 'wire' and tails hooked into an 'active' (whatever that means) hardware (not indicating the direction of traffic flow at all). nodes: everything else: these include hosts, routers, networks (those passive, like ethernet, too) and even other maps. Nodes have locators (even those passive). maps: lists of pairs of nodes (their locators or EIDs ??), each such pair representing an arc; these *may* have locators. Yes, this is literally *not* what is in the architecture draft. But its simple, and it allowed me to read and (well, more or less) understand the rest of the document even though I had to keep in mind the difference. Is this kind of maps useless (mismatching) the kind of functionality nimrod imposes on a topology map? -Rafal   Received: from PIZZA.BBN.COM by BBN.COM id aa16851; 14 Dec 94 10:43 EST Received: from pizza by PIZZA.BBN.COM id aa11648; 14 Dec 94 10:21 EST Received: from KARIBA.BBN.COM by PIZZA.BBN.COM id aa11644; 14 Dec 94 10:18 EST To: Rafal_Pietrak@camk.edu.pl cc: nimrod-wg@BBN.COM Subject: Re: Representational Variants In-reply-to: Your message of Wed, 14 Dec 94 12:14:04 +0100. <9412141114.AA17400@alfa.camk.edu.pl> Date: Wed, 14 Dec 94 10:21:07 -0500 From: Isidro Castineyra Rafal, >>I'm not a member of the WG; still, I'd like to make a comment related >>to the subject. I am not sure if there is such a thing as being a member of the WG. Your comments are always welcome. In the abscence of extra information, a map only announces the existence of services between different points. Nimrod makes no assumptions about how these services are implemented nor about the physical reality behind nodes and arcs. However, it is possible to use Nimrod to represent "real" networks. Strictly speaking, only the network owner (manager) needs to know about the mapping between Nimrod objects (nodes, arcs) and physical assets (routers, hosts, communication links, etc.). Some have proposed that there could be attributes associated with nodes and arcs that say things like "this node is a router". If maps can include this kind of information, the physical realization of Nimrod entities could be also announced to others. Why or when to do this is a separate discussion. Does that answer your concerns? Isidro   Received: from PIZZA.BBN.COM by BBN.COM id aa01049; 14 Dec 94 14:14 EST Received: from pizza by PIZZA.BBN.COM id aa13111; 14 Dec 94 13:46 EST Received: from BBN.COM by PIZZA.BBN.COM id aa13107; 14 Dec 94 13:44 EST Received: from ginger.lcs.mit.edu by BBN.COM id aa27544; 14 Dec 94 13:30 EST Received: by ginger.lcs.mit.edu id AA04266; Wed, 14 Dec 94 13:30:17 -0500 Date: Wed, 14 Dec 94 13:30:17 -0500 From: Noel Chiappa Message-Id: <9412141830.AA04266@ginger.lcs.mit.edu> To: nimrod-wg@BBN.COM Subject: Simplified maps Cc: jnc@ginger.lcs.mit.edu I've been thinking about the ever-popular topic of how do we most efficiently and clearly create a transform between our abstract maps, and real-world physical topologies. One thing we might want to think about is the fact that for most hosts, we probably don't need to show either them, or their interfaces, in any map. If we adopt the convention that a host's interface to a network named with the locator >A>B..F>G is always of the form >A>B..F>G>X, where "X" is effectively the physical address of the host's interface, we need never put meta-nodes ("mnodes", for short) for either the hosts, or their interfaces, in any maps. In essence, you'd mark the mnode representing the network (which you can interpret as a multi-point arc with attributes :-) as not being expandable, so those interfaces would always be "hidden" inside the network's mnode. Theoretically you could (if you wanted) allow it to expand into a map showing each interface as an mnode, connected to the mnode for the interface. We may find some use for this (e.g. if different host interfaces to a given network have different realizable throughputs, and you wish to indicate that on the map), but at the moment it seems less likely. Of course, none of this would stop us giving either the host or the interface a locator of the form >A>B..F>H (since you can construct a map with either the host or the interface being shown by an mnode at a peer level with the network's mnode), provided there was some use for doing so. However, this is at sufficient variance with current practise (where interfaces derive their address from the address of the network to which they are attached) that it would probably confuse people. A corollary to this principle applies to routers. A simple-minded application of the meta-node/adjacency model to routers would leave us with an mnode for each interface, as well as an mnode for the router. If we don't with to say anything unusual about the interface, other than give them locators, this is probably inefficient. There's also the old problem of what locators do you give to the interfaces: ones which lump them with the host, or with the router. (I.e. do you draw circles which include the interfaces with the host, or the router.) So, perhaps we might wish to define an mnode type for "router" which has, as one of its attributes, a list of interface locators: each locator would provide (by the method above) the locator for the interface of that router to each network mnode to which the router has an adjacency. We thus wouldn't need the overhead of an mnode for each interface, to do nothing more than provide a place to put the locator of the interface. Again, this mnode could be marked as "unexpandble", but if you wanted, you could allow it to be expanded to a map showing the router mnode, and an mnode for each interface. Which raises an interesting possibility, one I had never, ever thought of. I had always considered that abstraction boundaries (i.e. the circles on the map which enclose pieces of the graph) would match naming aggregation boundaries. ***However, this is not always necessary.*** For instance, suppose we had a router >A>B>R which is connected to networks A>B>F, A>B>G and A>B>H. It's interface locators would be F>X, G>Y, and H>Z. One would normally assume that mnodes representing these interfaces would be aggregated with their associated network mnodes to hide them. Hoever, there is no reason it has to be that way. It would be quite possible to have a map which showed the area A>B as containing nodes R, F, G and H, and you only see nodes F>X, G>Y and H>Z when you expand node *R*, *not* nodes F, G or H. The downside of this is that given a locator >A>B>C, if you wanted to find the node named >A>B>C, you couldn't be *guaranteed* of finding it by looking inside node >A>B. There are obviously ways of getting around this, but there's an even worse problem. The routing aggregation works because you don't need to know how to get to >A>B>C if you're >A>Z, you only need to know how to get to >A>B. Allowing >A>B>C to hide inside >A>X is going to mess this up. It works for *interfaces* because if you have something with the locator >A>B>C, where C is the physical address of an interface on network >A>B, if you get to >A>B you're guaranteed that any router connected to >A>B can send packets to >A>B>C. So maybe the rule is that >A>B>C is allowed to be aggregated inside >A>X for map abstraction purposes if and only if A>B>C is directly reachable from >A>B, or something like that. Hmm. Something to go away and think about Real Hard. Noel   Received: from PIZZA.BBN.COM by BBN.COM id aa05943; 14 Dec 94 15:18 EST Received: from pizza by PIZZA.BBN.COM id aa13514; 14 Dec 94 14:51 EST Received: from BBN.COM by PIZZA.BBN.COM id aa13510; 14 Dec 94 14:49 EST Received: from ginger.lcs.mit.edu by BBN.COM id aa02609; 14 Dec 94 14:35 EST Received: by ginger.lcs.mit.edu id AA04747; Wed, 14 Dec 94 14:34:30 -0500 Date: Wed, 14 Dec 94 14:34:30 -0500 From: Noel Chiappa Message-Id: <9412141934.AA04747@ginger.lcs.mit.edu> To: Rafal_Pietrak@camk.edu.pl, isidro@BBN.COM Subject: Re: Representational Variants Cc: nimrod-wg@BBN.COM From: Rafal_Pietrak@camk.edu.pl I'm not a member of the WG In the IETF, anyone who cares to participate in any way is an IETF or WG "member". We're very anarchistic! I had an impression, that arcs of the network topology map are defined as _logical_ entities, i.e. indicating (possible) traffic, not connectivity. Yes, this map model that we are working on is intended to be used for very high-level descriptions of large chunks of the network (where an entire service provider might be a single node) as well as low-level maps where there is a one-one correspondence between nodes and physical entities. I'm not sure exactly what you mean by "connectivity" (do you mean that an arc would represent direct physical connectivity between two nodes), but you do need connectivity - defined as a way to get trafic from one of the two nodes to another - before traffic can flow directly between those nodes. This suggests that these maps are used for traffic flow optimization, not for connectivity setup and maintenance. Yes and no. In general the maps are used for path selection; i.e. a user (or an agent of the user) wants to find a path from one place to another, and uses a collection of map data to do so. (Just as if I set out to drive from Paris to Prague I'd look at a collection of road maps to pick a path.) So, in many cases, the maps would be used to handle normal data traffic. The maps would also be referred to either to pick a reasonably efficient path that met an unusual set of service constraints (e.g. needs a 1Gb/sec path), or to compute a very efficient path (i.e. better than the sub-optimal path normally provided by most large-scale routing). However, as an optimization for certain classes of short-lived traffic, where path selection presents a substantial (and non-useful) overhead, there is a way for users to utilize path segments that the network has precomputed (using the maps). Again, I'm not quite sure what you mean by "traffic flow optimization" (do you mean picking an optimal path from a given traffic stream, or somehow controlling overall traffic patterns) and "connectivity setup" (do you refer to what we call "flow setup", or do you mean the process by which nodes discover and report connectivity between themselves), so it's difficult to comment definitively on your statement. If the later was intended, I wonder whether saying, that "arcs represent physical network interfaces" changes the intended meaning. Since arcs do not represent just physical interfaces, but can be used to represent connectivity at high levels of abstraction, this is not an issue. arcs: are physical interfaces with heads pointing towards the 'wire' and tails hooked into an 'active' (whatever that means) hardware (not indicating the direction of traffic flow at all). That is certainly a simple model to work with, and one close to the one that OSPF uses. I understand the attractiveness of modelling interfaces as arcs (I used to work with that model myself). However, I think that one you start to think about things like adding attributes to interfaces (thereby needing arcs with attributes) the value of our "meta-node/adjacency" basic model becomes more apparent. Yes, the user interface will probably draw pictures in which interfaces are shown as arcs, but the underlying data structure will be the meta-node/adjacency model, in which one of your "arcs" shows up as a meta-node with some adjacencies. nodes: everything else: these include hosts, routers, networks (those passive, like ethernet, too) and even other maps. Nodes have locators (even those passive). The thing is that interfaces also need locators, so that on a host with multiple interfaces, you can indicate which one you wish to use. (This may make a difference if one host interface is to a 1.4 Mbit/sec link, and another is to a 100 Mbit/sec link, and your application needs 10 Mbit/sec.) So, in you model, the arcs need locators, as well as the nodes. Yes, this is literally *not* what is in the architecture draft. But its simple, and it allowed me to read and (well, more or less) understand the rest of the document even though I had to keep in mind the difference. Yes, we need a simple model if people are to be able to read the drafts and understand it. I expect that we will provide some simple examples showing how a few simple network topologies (e.g. a router and two networks) and how those translate into Nimrod maps. Is this kind of maps useless (mismatching) the kind of functionality nimrod imposes on a topology map? We're trying to balance two very different goals. One is to provide a map model which has the maximum amount of flexibility, since we aren't *really* sure what people are going to want to do. The second is to provide a map model which is easy to use in typical real-world situations. There's often a conflict. If you focus on the second, you wind up with the kind of map model you outlines, where nodes represent networks and routers, and arcs represent interfaces. I started with that, but I've been persuaded that it's not the most flexible model. What we're struggling with now is, given this more abstract model, how to provide a simple and efficient transliteration from the real world systems, to this model. Noel   Received: from PIZZA.BBN.COM by BBN.COM id aa12662; 15 Dec 94 11:23 EST Received: from pizza by PIZZA.BBN.COM id aa19917; 15 Dec 94 10:57 EST Received: from KARIBA.BBN.COM by PIZZA.BBN.COM id aa19913; 15 Dec 94 10:54 EST To: nimrod-wg@BBN.COM Subject: Abstract Maps Considered Harmful Date: Thu, 15 Dec 94 10:56:34 -0500 From: Isidro Castineyra Abstract maps have been proposed partly as a substitute for "complex" connectivity specifications. As I see it, the hope is that they would allow very succinct characterization of a node services. Below I argue that abstract maps are a bad idea and that we would do better by keeping complex connectivity specifications. Maps are used to generate routes. When a node distributes an internal map (be it a "detailed", or an "abstract" map). It must be prepared, among other things, to accept flow setups defined by a explicit route (a.k.a. source route ). The explicit route is specified in terms of the locators of connectivity specifications appearing in that map. Moreover, the explicit route must be implemented correctly: the service provided to packets in that flow should be consistent with the connectivity specifications that appear in the explicit route. When the map is a detailed map (a "strict" abstraction of the underlying physical network), implementing the explicit route is relatively easy. Assume that the explicit route contains a sequence of connectivity specifications, each associated with a (sub)node in the map. Every subnode routes through itself according to the connectivity specification associated with it, and then passes the flow-setup packet to a neighbor subnode; the neighbor repeats the process, etc. Supposedly, a (sub)node that advertises a connectivity specification knows how to implement it. If the map is an abstract map, things are not as straightforward. Assume that we are dealing with a "transit" abstract map. The node would distribute this map in the spirit of "I work as if I was built internally as the map says". Whoever is using the map to generate routes, does not care that the map is abstract, as long as it gets the service it has specified in the explicit route. However, if the map owner got too fancy when building the map, it might find it hard to built a "real" route that implements the abstract one. I imagine that this could be the case when the explicit route is a long sequence of connectivity specifications each associated with neighboring "imaginary" nodes. On the other hand, Nimrod cannot really legislate against abstract maps; there is no way to enforce such a prohibition. A node can advertise any map it pleases. It is the job of the Nimrod implementation used within that node to perform correctly. While one implementation might do only "strict" abstraction, and, therefore, simplify route generation, another implementation might decide to get fancy and advertise all sorts of abstract maps making work for the routing experts (mmm, job security?). So, what is the point of this rant? I would like to keep complex connectivity specifications. This would allow implementations in which all maps are strict and transit service is specified in terms of complex connectivity specifications. Admittedly, everything that a complex connectivity specification can say, can also be said in an abstract map. But I will let somebody else argue this side. Isidro   Received: from PIZZA.BBN.COM by BBN.COM id aa15703; 15 Dec 94 12:01 EST Received: from pizza by PIZZA.BBN.COM id aa20217; 15 Dec 94 11:36 EST Received: from TTL.BBN.COM by PIZZA.BBN.COM id aa20212; 15 Dec 94 11:34 EST To: Isidro Castineyra cc: nimrod-wg@BBN.COM Subject: Re: Representational Variants In-reply-to: Your message of Tue, 13 Dec 94 10:01:15 -0500. Date: Thu, 15 Dec 94 11:34:32 -0500 From: Ram Ramanathan To: Isidro Castineyra Subject: Re: Representational Variants In-reply-to: Your message of Tue, 13 Dec 94 10:01:15 -0500. -------- > To: nimrod-wg@BBN.COM > Subject: Representational Variants > Date: Tue, 13 Dec 94 10:01:15 -0500 > From: Isidro Castineyra > > At the end of San Jose's IETF Thursday's session we made a list of > four architectural variants we would consider. This message lists > these options, plus one more that Ram pointed out. Terminology, and a > brief discussion follow after the list. > > Architectural/representational variants: > > I. Multipoint arcs with attributes + > nodes with abstract maps and no connectivity specs. > > II. Unidirectional arcs with attributes + > nodes with "simple" connectivity specs and abstract maps. > > III. Adjacencies + > nodes with "complicated" connectivity specs and *no* abstract maps. > > IV. Adjacencies + > nodes with "simple" connectivity specs and abstract maps. > > V. Unidirectional arcs with attributes + > nodes with "complicated" connectivity specs (no abstract maps). > > My order of preference amongst these is given below (1= most preferred, 5 = least preferred). My personal reasons for this preference follow. 1. V 2. III 3. II 4. IV 5. I Basically, I don't like fake nodes and hence abstract maps. I prefer the flexibility afforded by attributes on arcs. The latter is, however, not as important to me as the former. There are mainly two points that have influenced me: a) The representation must be as natural as possible. That is, one must be able to see a strong relation between the representation and the actuality. This is especially important to network maintenance people who would probably rather not do complex conversions/mappings when analyzing a packet containing a map. Therefore my antipathy toward "fake" nodes and toward "abstract maps". Further, there is an unclear correspondence between a route (or path) and its realization in terms of physical entities. When I want to cluster entities, I draw circles around them and call them nodes. These nodes are connected and I represent this connectivity by arcs. Since we have aggregated, we need to say something about the aggregation. So I give a node some attributes and an arc some attributes. For instance, BBN and MIT are connected by a microwave link (as part of DARTnet (ARPA experimental testbed). I would have two nodes, one for MIT, one for BBN and an arc depicting the "microwave" link. For instance, as part of the attribute, I would say that it is more error prone than a wire link. Putting a fake node in place of this link and putting all the attributes that make sense *between* nodes into that node is, to me, an unnecessary deviation from "natural"-ness. b) The representation must be as flexible as possible. That is, if represntn A allows me to represent information in more ways than repr. B, I prefer A to B, provided that A is not too complicated. Thus, I prefer "partial" connectivity spec (what Isidro called "complicated" connectivity spec - "partial" is a more objective term, and also, I believe they are not all that complicated) to "total" connectivity specifications ( a specification always applies to *all* arcs incident on a node). A total specification is a particular case of a partial spec and if we have a partial spec as the "chosen" representation, we can always specify total specs, but not vice-versa. On similar lines, arcs-with-attrs are more flexible than attributeless arcs. One concern is: Will V or III make the implementation complicated? Will the use of partial specifications make the route computation hairy? I believe not. My belief is based on the route generation module that I (re-)implemented for IDPR. IDPR is a link-state, source-specified routing mechanism and the representation used there is very very close to III above. Currently, IDPR uses Dijkstra SPF to generate policy routes (ie, QoS and access restrictions) including muticast and maximally disjoint multipath policy routes. The chief idea that was used to make the IDPR implementation simple, and I strongly believe this holds for Nimrod too, is to get away from the fact that connectivity specs on arcs or nodes *need* to be chained together as an explicit graph in order to run Dijkstra or any such algorithm. It is simpler to adapt the core idea of Dijkstra to the problem at hand than to convert the problem at hand to a representaion traditionally used for Dijkstra. Now, there is an obvious tradeoff between representational flexibility/power and implementation complexity. While I would be the last to discount the importance of implementation friendliness, I would argue against compromising architectural clarity, naturalness and flexibility for its sake. In a broader perspective, I actually don't think there is much difference between any of the schemes I..V and would not be unhappy to work with any of them. Cheers, -Ram.   Received: from PIZZA.BBN.COM by BBN.COM id aa00430; 15 Dec 94 15:41 EST Received: from pizza by PIZZA.BBN.COM id aa21567; 15 Dec 94 15:15 EST Received: from KARIBA.BBN.COM by PIZZA.BBN.COM id aa21563; 15 Dec 94 15:13 EST Date: Thu, 15 Dec 94 15:15:46 EST From: Martha Steenstrup To: nimrod-wg@BBN.COM Subject: IETF slides Nimrod: Data Message Forwarding (Graphical slides, including packet formats, omitted.) 1. Routes - Route agents generate routes at the request of forwarding agents, using available maps and (source/destination) traffic service requirements. - Route: - Expressed as a sequence of node locators, from source to destination, together with the labels for those node service attributes used in route selection. - Must include at least the source and destination node locators. - Different segments of the same route may be expressed at different node granularities. 2. Paths - Forwarding agents set up paths according to the routes selected. - Path: - Realization of a route as forwarding state within the forwarding agents along the route. - Forwarding state includes previous-hop and next-hop forwarding agents and path labels as well as traffic service requirements. - Paths are inherently multi-level, i.e., themselves composed of multiple paths. 3. Packet Forwarding Modes - Datagram: - No session-specific state. - For traffic sessions consisting of few messages or traversing unreliable or highly mobile sections of an internetwork. - Flow: - Establishes session-specific state. - For traffic sessions consisting of several messages or requiring guaranteed service. - Both modes rely on the existence of underlying paths established in forwarding agents. 4. Path Setup - Each path has an initiator and a target. - Path setup may be either source-initiated or destination-initiated. - Multiple paths may be set up along the same route, multiple traffic sessions may use the same path, and a traffic flow may be spread over multiple paths. - The context of a path is the lowest-level node that contains the entire path. - Path setup is similar for unicast and multicast. 5. Path Setup Messages - Setup: generated by the initiator and used to establish forwarding state. - Accept: generated by the target and used to inidicate successful path setup to the initiator. - Teardown: generated by any forwarding agent on the path and used to remove the path from all forwarding agents in which it exists. - All path setup messages are exchanged using a reliable transaction protocol. 6. Path Setup: Initiator - States: - idle: awaiting a setup message. - check: performing checks on setup message. - ready: checks complete, forwarding state installed, and ready to forward data along path. - done: path successfully setup to target. idle -- request setup --> check. check -- fail --> idle. check -- pass --> ready. ready -- receive accept --> done. ready -- teardown --> idle. done -- teardown --> idle. 7. Path Setup: All Others - States: - idle: awaiting setup. - check: performing checks on path setup message. - ready: checks complete, forwarding state installed, and ready to forward data along path. idle -- request setup --> check. check -- fail --> idle. check -- pass --> ready. ready -- teardown --> idle. 8. Check State Actions - Consistency checks of setup message contents: - Path label unused? - Route contains current node? - Service attribute present in current node? - Route consistent with current node's service constraints? - Resource availability check for next hop: - Able to obtain path with sufficient resources to next node in route? - Failure of any consistency check or of the resource availability check causes path teardown. - Successful completion of all checks results in new forwarding state and transmission of the setup message to the next node (source-initiated) or previous node (destination-initiated) on the route. 9. IPv6 Nimrod-Specific Options - Hop-by-hop options: - Path labels. - Monitoring. - Route option: - Route specification. - End-to-end options: - Endpoint identifiers. - Service specification. 10. IPv6 Path Labels Option (Packet format omitted) - Labels specified in order from lowest level to highest level. - Path label nesting has maximum depth of 256. - Each label is 16 bits long and not necessarily globally unique but is unique among the forwarding agents on the given path. - Modified at most forwarding agents. 11. IPv6 Monitoring Option (Packet format omitted) - Records path performance information. - Multiple performance measures may be monitored simultaneously. - Modified at most forwarding agents. 12. IPv6 Route Specification Option (Packet format omitted) - Specifies routes in terms of node locators and the labels of the accompanying service attributes. - Node locators can be of arbitrary length, but at each level they are restricted to 16 bits. - Also contains modifiable pointer to next node in specified route. 13. IPv6 Endpoint Identifiers Option (Packet format omitted) - Contains the source and destination endpoint identifiers. 14. IPv6 Service Specification Option (Packet format omitted) - Contains information about requested services, such as delay and throughput, used for selecting appropriate next hops. 15. IPv6 Datagram-Mode Data Packet - Flow label = 0. - Source address = IPv6 address of source of current lowest-level path. - Destination address = IPv6 address of destination of current lowest-level path. - Path labels option (mandatory, except for immediate neighbors). - Route specification option (optional). - Endpoint identifiers option (mandatory). - Service specification option (optional). 16. IPv6 Flow-Mode Data Packet - Flow label = 0. - Source address = IPv6 address of source of current lowest-level path. - Destination address = IPv6 address destination of current lowest-level path. - Path labels option (mandatory). - Monitoring option (optional). - Endpoint identifiers option (optional). 17. Setup Message (Packet format omitted) - Constructed to look like an IPv6 data message in order to be able to reuse the IPv6 routines: - Flow label = 0. - Source address = 0. - Destination address = 0. - Path labels option (mandatory). - Monitoring option (optional). - Route specification option (mandatory). - Endpoint identifiers option (mandatory). - Service specification option (optional). - Also contains a maximum path lifetime and an indication of whether the path is source-initiated or destination-initiated. 18. Accept Message (Packet format omitted) - In response to a setup message, may contain monitored information, if the monitoring option was present in the setup message. - May also be sent in response to flow-mode data messages containing the monitoring option. 19. Teardown Message - In response to a setup message, travels back to the initiator, with monitored information if the monitoring option was present in the setup message. - Otherwise, travels in both path directions away from the forwarding agent initiating the teardown.   Received: from PIZZA.BBN.COM by BBN.COM id aa06117; 16 Dec 94 11:17 EST Received: from pizza by PIZZA.BBN.COM id aa27572; 16 Dec 94 10:55 EST Received: from BBN.COM by PIZZA.BBN.COM id aa27568; 16 Dec 94 10:50 EST Received: from SUNIC.SUNET.SE by BBN.COM id aa04423; 16 Dec 94 10:50 EST Received: from alfa.camk.edu.pl by sunic.sunet.se (8.6.8/2.03) id QAA08251; Fri, 16 Dec 1994 16:50:12 +0100 From: Rafal_Pietrak@camk.edu.pl MMDF-Warning: Parse error in original version of preceding line at BBN.COM Received: from marvin.camk.edu.pl by alfa.camk.edu.pl (5.65b/RP-1.3) id AA25580; Fri, 16 Dec 94 16:52:20 +0100 Message-Id: <9412161552.AA25580@alfa.camk.edu.pl> Received: by marvin.camk.edu.pl (NX5.67d/NX3.0X) id AA19812; Fri, 16 Dec 94 16:52:27 +0100 Date: Fri, 16 Dec 94 16:52:27 +0100 Received: by NeXT.Mailer (1.95.RR) Received: by NeXT Mailer (1.95.RR) To: nimrod-wg@BBN.COM Subject: Re: Representational Variants > Date: Wed, 14 Dec 94 14:34:30 -0500 > From: jnc@ginger.lcs.mit.edu (Noel Chiappa) > > From: Rafal_Pietrak@camk.edu.pl > I'm not a member of the WG > > In the IETF, anyone who cares to participate in any way is an IETF > or WG "member". We're very anarchistic! I like it :). [deleted...] > I'm not sure exactly what you mean by "connectivity" (do you mean > that an arc would represent direct physical connectivity between > two nodes), but you do need connectivity - defined as a way to get > traffic from one of the two nodes to another - before traffic can > flow directly between those nodes. [deleted...] > Yes and no. In general the maps are used for path selection; i.e. a > user (or an agent of the user) wants to find a path from one place > to another, and uses a collection of map data to do so. (Just as if > I set out to drive from Paris to Prague I'd look at a collection of > road maps to pick a path.) So, in many cases, the maps would be > used to handle normal data traffic. The maps would also be referred > to either to pick a reasonably efficient path that met an unusual > set of service constraints (e.g. needs a 1Gb/sec path), or to > compute a very efficient path (i.e. better than the sub-optimal > path normally provided by most large-scale routing). Actually, now I realized that there was an unexpressed assumption in my comments. Following your example with driving from Paris to Prague; My idea of maps used for "connectivity setup", is that these maps contain thin black lines (which almost no attributes) allowing me to get to Prague by whatever possible means. Maps used for traffic optimization would contain markings indicating highways, bridges, and (speaking about policy) national borders. The assumption I did is that I've been thinking about using maps -- nimrod maps -- to generate locators with virtually no user (or administrator) intervention. Since locators are used to get packets across the network I called this purpose "connectivity". Maps with fancy attributes (like bandwidth, QoS, etc) would then be used for selecting the best possible path, flow setup etc, thus for "optimization". Again, mobile network, after changing location, will have to update the "connectivity" map and reassign locators, but probably lots of attributes from "optimization" map could remain constant. One reason I fancy with these concepts is to 'optimize' network bootstrap time -- i.e. a situation when *whole* internet gets down and forgets it's configuration; then, here and there routers and hosts are powered up again. Like and overnight IPv4 to IPv6 transition. [deleted...] > and "connectivity setup" (do you refer to what we call "flow > setup", or do you mean the process by which nodes discover and > report connectivity between themselves), so it's difficult to The later. [deleted...] > nodes: everything else: these include hosts, routers, > networks (those passive, like ethernet, too) and even > other maps. Nodes have locators (even those passive). > > The thing is that interfaces also need locators, so that on a host Yes of course, my omission. Arcs can have locators, too. [deleted...] > If you focus on the second, you wind up with the kind of map model > you outlines, where nodes represent networks and routers, and arcs > represent interfaces. I started with that, but I've been persuaded > that it's not the most flexible model. What we're struggling with > now is, given this more abstract model, how to provide a simple and > efficient transliteration from the real world systems, to this > model. I see. I'll keep on listening to the list. -Rafal   Received: from PIZZA.BBN.COM by BBN.COM id aa07951; 16 Dec 94 11:43 EST Received: from pizza by PIZZA.BBN.COM id aa27720; 16 Dec 94 11:14 EST Received: from KARIBA.BBN.COM by PIZZA.BBN.COM id aa27716; 16 Dec 94 11:11 EST To: Noel Chiappa cc: nimrod-wg@BBN.COM Subject: Re: Simplified maps In-reply-to: Your message of Wed, 14 Dec 94 13:30:17 -0500. <9412141830.AA04266@ginger.lcs.mit.edu> Date: Fri, 16 Dec 94 11:14:25 -0500 From: Isidro Castineyra ... >> Theoretically you could (if you wanted) allow it to expand into a >>map showing each interface as an mnode, connected to the mnode for >>the interface. I don't get the sentence above. Is something missing? >> We may find some use for this (e.g. if different host interfaces to >>a given network have different realizable throughputs, and you wish >>to indicate that on the map), but at the moment it seems less >>likely. Of course, none of this would stop us giving either the >>host or the interface a locator of the form >A>B..F>H (since you can >>construct a map with either the host or the interface being shown by >>an mnode at a peer level with the network's mnode), provided there >>was some use for doing so. However, this is at sufficient variance >>with current practise (where interfaces derive their address from >>the address of the network to which they are attached) that it would >>probably confuse people. An alternative would be to make the network+hosts one mnode that can be opened to show a central "transient" mnode that represents the network hardware and peer to this the mnodes for the hosts (or their interfaces). >> A corollary to this principle applies to routers. A >>simple-minded application of the meta-node/adjacency model to >>routers would leave us with an mnode for each interface, as well as >>an mnode for the router. If we don't with to say anything unusual >>about the interface, other than give them locators, this is probably >>inefficient. There's also the old problem of what locators do you >>give to the interfaces: ones which lump them with the host, or with >>the router. (I.e. do you draw circles which include the interfaces >>with the host, or the router.) So, perhaps we might wish to define >>an mnode type for "router" which has, as one of its attributes, a >>list of interface locators: each locator would provide (by the >>method above) the locator for the interface of that router to each >>network mnode to which the router has an adjacency. We thus wouldn't >>need the overhead of an mnode for each interface, to do nothing more >>than provide a place to put the locator of the interface. Again, >>this mnode could be marked as "unexpandble", but if you wanted, you >>could allow it to be expanded to a map showing the router mnode, and >>an mnode for each interface. A couple of comments: I do not like the idea of defining special types of mnodes. If the basic paradigm can do the job, I am loath to "corrupt" it (1/2 :-)). If adjacencies have locators, one could map interfaces to pairs of adjacencies. When doing this, each interface would have two locators, one in each direction. This sounds appropriate as an interface exists not by itself, but between two things. Moreover, if adjacencies have attributes, as Ram advocates, that is where we can hang the properties of the interfaces. More generally, what you seem to try to do is to have mnodes for both the host (das Ding an sich) and its interfaces. Then you are left with the problem of how to relate them. I suppose that if we are trying to use Nimrod to manage the physical network something like this might be useful. However, I don't think that this is necessary just for routing: each interface (to which you want to give a locator ending in its physical address) is represented as its own mnode; the map need not show that all these interfaces correspond to the same host. Host is a physical concept not necessarily a routing concept. The tie-in between all these different interfaces would come through the EID-locator mapping. >> Which raises an interesting possibility, one I had never, ever >>thought of. I had always considered that abstraction boundaries >>(i.e. the circles on the map which enclose pieces of the graph) >>would match naming aggregation boundaries. ***However, this is not >>always necessary.*** For instance, suppose we had a router >A>B>R >>which is connected to networks A>B>F, A>B>G and A>B>H. It's >>interface locators would be F>X, G>Y, and H>Z. One would normally >>assume that mnodes representing these interfaces would be aggregated >>with their associated network mnodes to hide them. Hoever, there is >>no reason it has to be that way. It would be quite possible to have >>a map which showed the area A>B as containing nodes R, F, G and H, >>and you only see nodes F>X, G>Y and H>Z when you expand node *R*, >>*not* nodes F, G or H. The downside of this is that given a locator >>>A>B>C, if you wanted to find the node named >A>B>C, you couldn't be >>*guaranteed* of finding it by looking inside node >A>B. There are >>obviously ways of getting around this, but there's an even worse >>problem. The routing aggregation works because you don't need to >>know how to get to >A>B>C if you're >A>Z, you only need to know how >>to get to >A>B. Allowing >A>B>C to hide inside >A>X is going to mess >>this up. It works for *interfaces* because if you have something >>with the locator >A>B>C, where C is the physical address of an >>interface on network >A>B, if you get to >A>B you're guaranteed that >>any router connected to >A>B can send packets to >A>B>C. So maybe >>the rule is that >A>B>C is allowed to be aggregated inside >A>X for >>map abstraction purposes if and only if A>B>C is directly reachable >>from >A>B, or something like that. Hmm. Something to go away and >>think about Real Hard. I really don't like this. I really don't like this. I really don't like this. As you point out, this breaks aggregation which is our main concern. Isidro   Received: from PIZZA.BBN.COM by BBN.COM id aa22345; 19 Dec 94 10:40 EST Received: from pizza by PIZZA.BBN.COM id aa14229; 19 Dec 94 10:15 EST Received: from KARIBA.BBN.COM by PIZZA.BBN.COM id aa14225; 19 Dec 94 10:11 EST To: nimrod-wg@BBN.COM Subject: Minutes of the IETF meeting for your comments Date: Mon, 19 Dec 94 10:13:53 -0500 From: Isidro Castineyra I am enclosing a draft of the minutes. Please let me know if you would like to make any changes. I am planning to send them off tomorrow. Thanks, Isidro --------------- Nimrod WG Minutes, IETF 31, San Jose Isidro Castineyra, BBN December 19, 1994 1 Preface The Nimrod WG met on Wednesday December 7, 1994 from 0930 to 1200 and on Thursday December 8 from 0930 to 1200. The agenda for the meeting was: 1. Agenda bashing/Announcements---5min (Isidro Castineyra) 2. Introduction: Nimrod Components---15min (Isiidro Castineyra) 3. Nimrod Database Naming System---15min (Isidro Castineyra) 4. External Data Representation---30min (Isidro Castineyra) 5. Discovery Protocol---30min (Isidro Castineyra) 6. Hierarchical Update Protocol---30min (Ram Ramanathan) 7. Hierarchical Query/Response Protocol---30min (Ram Ramanathan) 8. Path Setup/Teardown Protocol3---30min (Martha Steenstrup) 9. Transition Plan---30min (Charlie Lynn) 10. Reliable Transport Protocol---15min (Charlie Lynn) 1 11. Open Issues and Work Plan---15min 2 Components Isidro Castineyra enumerated the components being designed: o Database o Discovery Protocol; o Hierarchical Update Protocol; o Reliable Transport; o Hierarchical Query/Response Protocol; o Hierarchical Path Setup/Teardown Protocol. 3 Database Isidro Castineyra described briefly the database organization, a query language, and a suggested external representation. The database was presented in term of a description of the data structures for: arcs, nodes, maps and connectivity specifications. A proposed structure for each one of these was presented. A sketch of a query language was also presented. The suggested external data representation is based on (type, length, value) tripes in which each element of the triple is encoded as in RFC 1014. 4 Hierarchical Update Protocol Ram Ramanathan discussed the hierarchical update and query protocols and the mapping of the association database maintenance, map distribution to these protocols. There were three main themes to the presentation: 1. Overview of functionality and description of map update and association maintenance. The functionality of Nimrod includes agent and neighbor discovery, locator acquisition, arc formation, map query, map distribution, association query and update, path setup and teardown. Currently, we plan on using five protocols in Nimrod - hierarchial update, hierarchical query-response, path setup, discovery, reliable transport. The functionality is designed in terms of Nimrod "agents" which include the Entity Representative, Association Agent, Route Agent 2 and Forwarding Agent. The functionality of map distribution and association maintenance were described in terms of a node's immediate environment (ie, the agents of the node's parent, child and sibling nodes). 2. Hierarchical Update and Query Response Protocols. The hierarchical update protocol is used to update database contents (eg. association database, map database etc.). It uses the Reliable Transport protocol between peer agents. The protocol engine at an agent works as follows. On the arrival of a message, it checks the timestamp, sequence number, authentication etc. If it is not okay, the message is ignored. Otherwise, the Update Message Forwarding Table (to be defined) is consulted and a decision is made whether or not to cache and/or forward. As per the UMFT, the message is forwarded to each agent. If error, another agent is tried. Exceptions that must be handled include invalid timestamp, duplicate message, nexthop unreachable. The query response protocol is used for obtaining information about a specific portion of a database (eg. association query, map query etc). Like the Update Protocol, this also uses the Reliable Transport protocol between peer agents. The protocol engine at a transit agent is very similar to the update protocol engine, except that a different table, Query Message Forwarding Table is consulted. At an originating agent, the protocol engine is slightly different. The originator prepares and sends a query message (according to the QMFT) and sets a timer and waits for one of the following : A response to the query, upon which the response is handed to the application; a query abort command from the application, upon which the state is rest; a timer expiration upon which state is reset. 3. The mapping of functionality into protocols. This is done by means of the control message forwarding tables (UMFT and QMFT described earlier). A (U/Q)FMT contains, for each agent, a table with the protocol messages (eg. association update, map update etc) as the rows and the source of the message (eg. agent F of parent, agent E of child etc) as the columns. Every entry (i,j) indicates the set of actions to be taken if a message of type i is received from source j. The benefits of this approach include flexibility, implementation friendli- -ness and the explicit identification of all combinations. A few UMFT and QMFT tables were described. The detailed design of the update and query-response protocols is in progress. A draft will be posted to the nimrod-wg shortly. 3 5 Hierarchical Setup/Teardown Protocol Martha Steenstrup discussed data message forwarding in Nimrod. She presented a high-level overview of the Nimrod path setup protocol, including functional description, finite state machine, and packet formats. The Nimrod path setup protocol establishes forwarding information in "forwarding agents" according to the routes selected. Each forwarding agent along the path performs route consistency and resource availability checks, before establishing forwarding state. Path setup may be initiated by the source or the destination, and paths may be torn down at any time by any forwarding agent along the path. She also discussed how Nimrod message forwarding would operate with IPv6. She proposed several Nimrod-specific IPv6 options to carry nested path labels, performance monitoring information, Nimrod routes, service specifications, and endpoint identifiers. Also, she provided examples of IPv6 data message formats corresponding to the Nimrod "datagram" and "flow" message forwarding modes. 6 Transition Plan Charlie Lynn presented a transition plan. The slides from his presentation will be posted to the mailing list. 7 Points Raised 7.1 Metanodes Noel Chiappa proposed that maps be composed of "metanodes" and adjacencies (arcs with no attributes). A metanode has attributes associated with it (e.g., connectivity specifications). Connectivity between metanodes is represented with adjacencies. Metanodes can be used to represent: nodes, arcs, and multipoint arcs. 7.2 Uniform Connectivity Specifications Dave Bridgham proposed that all connectivity specifications associated with a node be uniform: i.e., that they apply between all pairs of incoming and outgoing arcs. 8 Open Issues The following are open issues identified. 4 o Locator external representation: 1. Can the hierarchical structure of a locator be inferred from its representation? 2. Is there a single representation for locators? o Performance specification and representation: how to characterize performance guarantees and how to represent these externally. o Policy representation. o Five alternative Architectural/representational variants: 1. Multipoint arcs with attributes + nodes with abstract maps and no connectivity specs; 2. Unidirectional arcs with attributes + nodes with uniform connectivity specs and abstract maps; 3. Adjacencies + nodes with specific (non-uniform) connectivity specs and *no* abstract maps; 4. Adjacencies + nodes with uniform connectivity specs and abstract maps; 5. Unidirectional arcs with attributes + nodes with specific connectivity specs (no abstract maps). 5   Received: from PIZZA.BBN.COM by BBN.COM id aa29887; 22 Dec 94 11:54 EST Received: from pizza by PIZZA.BBN.COM id aa07658; 22 Dec 94 11:24 EST Received: from KARIBA.BBN.COM by PIZZA.BBN.COM id aa07653; 22 Dec 94 11:20 EST To: nimrod-wg@BBN.COM Subject: Minutes from the San Jose IETF meeting Date: Thu, 22 Dec 94 11:22:53 -0500 From: Isidro Castineyra Nimrod WG Minutes, IETF 31, San Jose Isidro Castineyra, BBN December 22, 1994 1 Preface The Nimrod WG met on Wednesday December 7, 1994 from 0930 to 1200 and on Thursday December 8 from 0930 to 1200. The agenda for the meeting was: 1. Agenda bashing/Announcements---5min (Isidro Castineyra) 2. Introduction: Nimrod Components---15min (Isidro Castineyra) 3. Nimrod Database Naming System---15min (Isidro Castineyra) 4. External Data Representation---30min (Isidro Castineyra) 5. Discovery Protocol---30min (Isidro Castineyra) 6. Hierarchical Update Protocol---30min (Ram Ramanathan) 7. Hierarchical Query/Response Protocol---30min (Ram Ramanathan) 8. Path Setup/Teardown Protocol---30min (Martha Steenstrup) 9. Transition Plan---30min (Charlie Lynn) 10. Reliable Transport Protocol---15min (Charlie Lynn) 1 11. Open Issues and Work Plan---15min 2 Components Isidro Castineyra enumerated the components being designed: o Database o Discovery Protocol; o Hierarchical Update Protocol; o Reliable Transport; o Hierarchical Query/Response Protocol; o Hierarchical Path Setup/Teardown Protocol. 3 Database Isidro Castineyra described briefly the organization of the database of routing information, a query language, and a suggested external representation. The database was presented in term of a description of the data structures for: arcs, nodes, maps and connectivity specifications. A proposed structure for each one of these was presented. A sketch of a query language was also presented. The suggested external data representation is based on (type, length, value) triples in which each element of the triple is encoded as in RFC 1014. 4 Hierarchical Update Protocol Ram Ramanathan discussed the hierarchical update and query protocols and the mapping of the association database maintenance, and map distribution to these protocols. There were three main themes to the presentation: 1. Overview of functionality and description of map update and association maintenance. The functionality of Nimrod includes agent and neighbor discovery, locator acquisition, arc formation, map query, map distribution, association query and update, path setup and teardown. Currently, we plan on using five protocols in Nimrod - hierarchial update, hierarchical query-response, path setup, discovery, reliable transport. The functionality is designed in terms of Nimrod "agents" 2 which include the Entity Representative, Association Agent, Route Agent and Forwarding Agent. The functionality of map distribution and association maintenance were described in terms of a node's immediate environment (ie, the agents of the node's parent, child and sibling nodes). 2. Hierarchical Update and Query Response Protocols. The hierarchical update protocol is used to update database contents (eg. association database, map database etc.). It uses the Reliable Transport protocol between peer agents. The protocol engine at an agent works as follows. On the arrival of a message, it checks the timestamp, sequence number, authentication etc. If it is not okay, the message is ignored. Otherwise, the Update Message Forwarding Table (UMFT, to be defined) is consulted and a decision is made whether or not to cache and/or forward. As per the UMFT, the message is forwarded to each agent. If error, another agent is tried. Exceptions that must be handled include invalid timestamp, duplicate message, nexthop unreachable. The query response protocol is used for obtaining information about a specific portion of a database (eg. association query, map query etc). Like the Update Protocol, this also uses the Reliable Transport protocol between peer agents. The protocol engine at a transit agent is very similar to the update protocol engine, except that a different table, Query Message Forwarding Table (QMFT) is consulted. At an originating agent, the protocol engine is slightly different. The originator prepares and sends a query message (according to the QMFT) and sets a timer and waits for one of the following : A response to the query, upon which the response is handed to the application; a query abort command from the application, upon which the state is reset; a timer expiration upon which state is reset. 3. The mapping of functionality into protocols. This is done by means of the control message forwarding tables (UMFT and QMFT described earlier). A (U/Q)FMT contains, for each agent, a table with the protocol messages (eg. association update, map update etc) as the rows and the source of the message (eg. agent F of parent, agent E of child etc) as the columns. Every entry (i,j) indicates the set of actions to be taken if a message of type i is received from source j. The benefits of this approach include flexibility, implementation friendliness and the explicit identification of all combinations. A few UMFT and QMFT tables were described. The detailed design of the update and query-response protocols is in progress. A draft will be posted to the nimrod-wg shortly. 3 5 Hierarchical Setup/Teardown Protocol Martha Steenstrup discussed data message forwarding in Nimrod. She presented a high-level overview of the Nimrod path setup protocol, including functional description, finite state machine, and packet formats. The Nimrod path setup protocol establishes forwarding information in "forwarding agents" according to the routes selected. Each forwarding agent along the path performs route consistency and resource availability checks, before establishing forwarding state. Path setup may be initiated by the source or the destination, and paths may be torn down at any time by any forwarding agent along the path. She also discussed how Nimrod message forwarding would operate with IPv6. She proposed several Nimrod-specific IPv6 options to carry nested path labels, performance monitoring information, Nimrod routes, service specifications, and endpoint identifiers. Also, she provided examples of IPv6 data message formats corresponding to the Nimrod "datagram" and "flow" message forwarding modes. 6 Transition Plan Charlie Lynn presented a transition plan that discussed the issues associated with moving from an IPv4 internetwork supporting the current routing protocols to an internetwork supporting IPv6 and Nimrod. . The slides from his presentation will be posted to the mailing list. 7 Points Raised 7.1 Metanodes Noel Chiappa proposed that maps be composed of "metanodes" and adjacencies (arcs with no attributes). A metanode has attributes associated with it (e.g., connectivity specifications). Connectivity between metanodes is represented with adjacencies. Metanodes can be used to represent: nodes, arcs with attributes, and multipoint arcs. 7.2 Uniform Connectivity Specifications Dave Bridgham proposed that all connectivity specifications associated with a node be uniform: i.e., that they apply between all pairs of incoming and outgoing arcs. 4 8 Open Issues The following are open issues identified. o Locator external representation: 1. Can the hierarchical structure of a locator be inferred from its representation? 2. Is there a single representation for locators? o Performance specification and representation: how to characterize performance guarantees and how to represent these externally. o Policy representation. o Five alternative Architectural/representational variants: 1. Multipoint arcs with attributes + nodes with abstract maps and no connectivity specs; 2. Unidirectional arcs with attributes + nodes with uniform connectivity specs and abstract maps; 3. Adjacencies + nodes with specific (non-uniform) connectivity specs and *no* abstract maps; 4. Adjacencies + nodes with uniform connectivity specs and abstract maps; 5. Unidirectional arcs with attributes + nodes with specific connectivity specs (no abstract maps). 5   Received: from PIZZA.BBN.COM by BBN.COM id aa17976; 22 Dec 94 16:52 EST Received: from pizza by PIZZA.BBN.COM id aa09603; 22 Dec 94 16:32 EST Received: from KARIBA.BBN.COM by PIZZA.BBN.COM id aa09599; 22 Dec 94 16:30 EST Date: Thu, 22 Dec 94 16:32:33 EST From: Martha Steenstrup To: nimrod-wg@BBN.COM Subject: help Hi guys, I'm confused, and I'd like your help in clearing up my confusion. For the past year, I've been operating with what I thought was the working group's model of Nimrod. But lately, I'm beginning to worry that it's not really what you had in mind, particularly with respect to nodes and maps. The Nimrod model should be simple yet flexible. If the following model is not what you expect, please tell me how it differs and how you would like it to change. I'd like to know now rather than later, because protocols have already been designed according to this model. Nimrod objective: To reduce the amount of routing-related information that must be distributed, processed, and stored within a large, heterogeneous, and dynamic internetwork and to provide routes that meet the constraints imposed by the traffic sessions and by the networks themselves. Nimrod solution: To cluster contiguous network physical assets (e.g., routers, hosts, point-to-point and multiaccess links) and to abstract routing-related information (e.g., service offerings and restrictions on use of services) for these component assets. Clustering multiple physical assets into a single entity used for Nimrod routing reduces the total number of entities that are visible to routing at a particular level in a hierarchy of such clusters. Abstracting routing information from components assets to determine the routing information for the cluster reduces the amount of routing information visible for a particular cluster. Nimrod features: - Map-oriented (i.e., link-state) routing information. - Source-directed and destination-directed packet forwarding. - Construction of routes that meet the service constraints of session sources and destinations (e.g., desired delay, bandwidth, service provider) and of transit networks (e.g., expected delay, available bandwidth, times when services is offered, charge for service). Nimrod maps: From a Nimrod-centric perspective, an internetwork is a set of clusters of physical assets together with the hierarchical and adjacency relationships among the clusters and the services provided by these clusters. In the past, we have referred to the clusters as "nodes", the adjacencies as "arcs", and the services as "connectivity specifications" or "service attributes". We call a collection of Nimrod nodes, arcs, and associated connectivity specifications a "map". Routes are generated using internetwork maps and the locations and service requirements of sources and destinations. Physical assets may be clustered according to a variety of criteria. For example, all assets under the same management may be made into a cluster, or all assets within a certain radius of an urban center may be made into a cluster. The clustering criteria need not be the same across an internetwork. Moreover, an existing cluster may spawn separate sub-clusters if it becomes too large. Clustering may be an automatic operation or a manual operation. In any case, the choice of clustering criteria and algorithms will be under the control of network management. Nodes, arcs, and connectivity specifications each have a set of attributes that pertain to them, including a label (called the "locator" which is unique to the entity and which in part describes the entity's location within the map of the entire internetwork. Session "endpoints" (e.g., hosts or even processes in hosts) belong to particular clusters. Each endpoint also has attributes, including the locator of the node to which the endpoint belongs, a short location-independent label (called the "endpoint identifier"), and optionally a more friendly (but longer) location-independent label (such as a DNS name). Nimrod connectivity specifications: Connectivity specifications describe the services that the node provides together with restrictions on access to those services and the incoming and outgoing arcs between which they apply. Connectivity specifications come in three varieties: transit (from incoming to outgoing arcs), incoming (from incoming arcs to locations within the node), and outgoing (from locations within the node to outgoing arcs). Some connectivity specifications may apply between all incoming and/or outgoing arcs for a node, while others may apply between a proper subset of such arcs. For example, it may be possible to obtain 1 Mbs across the node, from any incoming to any outgoing arc, while between a specific incoming and outgoing arc pair, it may be possible to obtain 1 Gbs. When determining the connectivity specifications to advertise for a node, a network manager may use a combination of methods including measuring the performance between incoming and outgoing arcs, abstracting service information from the connectivity specifications of the component nodes, or configuring predetermined values. The number of connectivity specifications advertised by a node will depend upon the number of service offerings and restrictions for the node, the cost of advertising this information, and the revenue expected from users attracted to the node as a result of the services offered. Each node has at least two different maps associated with it: the "abstract map", which describes the node's connectivity specifications and arcs and the "detailed map", which describes the node's component nodes and connectivity specifications and component arcs. The node's abstract map is the one that is normally more widely known and used in generating routes that include that node. When forwarding packets across the node using a route constructed from the abstract map, the node is responsible for choosing an appropriate route across itself. The node's detailed map is less likely to be widely distributed and may be obtained by querying the node for it. With the detailed map, routes may be generated that explicitly include component nodes of the given node. Hence, the detailed map provides more information for those who require very precise routes. In the past, we have looked at models in which arcs have service attributes and at models in which they don't. Consider the case of two adjacent nodes X and Y, with a point-to-point link connecting a router in X and a router in Y. The point-to-point link has properties such as delay, available capacity, speed, etc. which may be different in the incoming and outgoing directions. In the arc-attribute model, these service properties are attached to the arc. Also, connectivity specifications for a node apply from the point that an incoming arc enters a node to the point where an outgoing arc exits a node. The services provided by a given route include those advertised in its constituent node's connectivity specifications and for its constituent arcs. In the no-arc-attribute model, these service properties are absorbed into the node's connectivity specifications. In this case, connectivity specifications for a node apply from the point that an incoming arc enters a node to the point where an outgoing arc touches the adjacent node. The services provided by a given route are those advertised in its constituent node's connectivity specifications. Nimrod nodes: For correct Nimrod routing, it is necessary to able to place queries to nodes for information about their maps. Hence, there must exist locatable entities acting on behalf of those nodes to respond to such queries. Moreover, when a route includes a particular node, the route must traverse the given node. Hence, there must exist entities acting on behalf of that node to forward traffic across it. Therefore, nodes not only possess attributes used for routing but also are affiliated with entities that can act on their behalf for distributing routing information and for forwarding packets. Nimrod rules of thumb: Nimrod must be able to provide routes that meet detailed session service requirements yet must strive to limit the amount of routing information necessary to do so. These are conflicting objectives. Physical asset clustering and routing information abstraction should not be applied gratuitously, but rather only when the size of the internetwork becomes to large to handle with a "flat" routing system. Furthermore, the clustering and abstraction algorithms should be selected carefully. The choice of algorithms will depend on the underlying internetwork topology and services as well the desired performance of the routing system. The clustering hierarchy should be no deeper than necessary, as increased depth often results in increased loss of information detail.