From owner-Big-Internet@munnari.oz.au Wed Jun 2 09:01:56 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA07717; Wed, 2 Jun 1993 09:02:07 +1000 (from owner-Big-Internet) Return-Path: Received: from atc.boeing.com by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA07714; Wed, 2 Jun 1993 09:01:56 +1000 (from ericf@atc.boeing.com) Received: by atc.boeing.com (5.57) id AA04819; Tue, 1 Jun 93 16:05:59 -0700 Date: Tue, 1 Jun 93 16:05:59 -0700 From: Eric Fleischman Message-Id: <9306012305.AA04819@atc.boeing.com> To: big-internet@munnari.oz.au Subject: TP-IX pro/con Earlier I posted a proposed list of PROs/CONs of SIP, PIP, and TUBA to the SIP, PIP and TUBA working groups. Now that TP-IX (old IPv7) has become a working group, I have constructed a tentative pro-con list for TP-IX as well. This is not being posted to the TP-IX working group list because I desire that the participants of the SIP vs TP-IX discussion which took place earlier last month on this list may be able to critique this "rough draft" evaluation. TP-IX PROs 1) Explicitly designed to support high bandwidth applications through enlarging the window size, sequence (and ACK) space, port numbers, and PDU size. TP-IX datagrams have a forward route ID for extremely fast path, circuit, or flow-based forwarding. 2) Transition eased via directly using the current TCP/IP architecture. TP-IX directly interoperates with IPv4 (via stateless transition). 3) Maintains current TCP/IP look-and-feel including preserving the current IPv4 addressing for deployed IPv4 hosts even after the IPv4 address space has saturated (i.e., eliminating the requirement to re-address these hosts). TP-IX CONs 1) Involves changes to both the network and transport layers. 2) RAP protocol is an unproven, distance-vector-based protocol. 3) Tends towards large, flat, global routing tables. 4) No wide IETF acceptance for TP-IX yet: TP-IX working group has only recently been established. 5) There are no commercial implementations of TP-IX yet. Thus, no manufacturer or network provider currently supports TP-IX. [Contrary: Process Software Corporation plans a commercial release later this year.] Note: the "Contrary" statements in brackets are a recent innovation of mine to try to identify disputable points with the nature of the opposing argument being identified. Note: Those interested in receiving an Updated version of my previous SIP, PIP, and TUBA PRO/CONs may request a copy directly from me. These updates have been made in response to the feedback I have received on the initial version which were posted to the various working groups. Since much of this feedback consisted in much disagreement between the various "feed-backers", I felt obligated to invent the "contrary" statement designations. --Eric Fleischman From owner-big-internet@munnari.oz.au Wed Jun 2 14:32:44 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA22775; Wed, 2 Jun 1993 14:33:14 +1000 (from owner-big-internet) Return-Path: Message-Id: <9306020433.22775@munnari.oz.au> Received: from sirius.process.com by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA16108; Wed, 2 Jun 1993 12:04:03 +1000 (from ULLMANN@PROCESS.COM) Date: Tue, 1 Jun 1993 22:03 -0400 From: ULLMANN@PROCESS.COM (Robert L Ullmann) To: big-internet@munnari.oz.au Subject: re: TP-IX PROs and CONs Hi Eric, I'd like to take issue with a couple of points (the CONs, of course ;-): 4) The fact that the TP/IX WG has just now been formed is not technically relevent. One might just as well point out that the IPv7-TP/IX project start predates the others by four years. (June 1988 vs circa 1992 for most of the rest of the work, as far as I know). Neither is at all relevent; we are looking for the best technical solution here. 5) Note that none of the proposals has commercial product available now; and none is likely to until the process is further advanced. PSC does plan to release RAP software, but note that this is not dependent on TP/IX, and TP/IX is not dependent on RAP. Whatever PSC's plans & contigency plans might be, this is _not_relevent_. In any case: we are supposed to be in a technical experimentation and analysis phase; a kick-it-out-the-door deployment race is in no-ones interest. (Regardless of how much that may be the IETF "tradition" :-( ) I suggest 4&5 be dropped; non-technical, not comparable. On the others, I would draw people's attention to the fact that nothing about TP/IX requires RAP, and RAP does not require TP/IX. Yes, they are designed to be complimentary, but statements like (not that Eric said this, mind you) "TP/IX's routing protocol, RAP, is ..." are prima facie invalid. (:-) I do believe any proposal requires answering the problem of providing at least one coherent routing protocol across the deployment coexistance period; and only the TP/IX - RAP combination offers this. Note I say coexistance: no "transition" is going to fly; and the coexistance is going to be long. Best Regards, Robert From owner-big-internet@munnari.oz.au Wed Jun 2 15:35:32 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA25397; Wed, 2 Jun 1993 15:35:48 +1000 (from owner-big-internet) Return-Path: Received: from Valinor.Stanford.EDU by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA21214; Wed, 2 Jun 1993 13:56:38 +1000 (from vaf@Valinor.Stanford.EDU) Received: by Valinor.Stanford.EDU (5.65/inc-1.0) id AA21883; Tue, 1 Jun 93 20:55:41 -0700 Date: Tue, 1 Jun 93 20:55:41 PDT From: Vince Fuller To: Valdis Kletnieks Cc: Darren Reed , big-internet@munnari.oz.au Office: Spruce Hall F15, (415) 723-6860 Usmail: Pine Hall 115, Stanford, CA, 94305-4122 Subject: Re: experimental network In-Reply-To: Your message of Fri, 28 May 93 00:16:55 EDT Message-Id: Is anybody besides me feeling just a *little* concerned that ZEALOT (or whatever they call the DNS walker) found a bunch of .com nodes in a reserved net? Do you suppose these people are in for a surprise? Or are we for thinking the space is reserved? I don't think this is cause for concern. Anything bogus addresses that could be found by walking the DNS tree belong to folks who have probably already noticed that those addresses are not routed into the Internet... Are there any *other* "reserved" net with squatters in them? Probably, though again, I doubt there is cause for concern. Lots of people like to use bogus net numbers for testing and internal, "unconnected" networks. For some, it is something of a rude shock when they do decide to get connected, but most of them get over it pretty fast... --Vince From owner-Big-Internet@munnari.oz.au Wed Jun 2 19:59:31 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA06625; Wed, 2 Jun 1993 20:00:26 +1000 (from owner-Big-Internet) Return-Path: Received: from mwassocs.demon.co.uk by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA06598; Wed, 2 Jun 1993 19:59:31 +1000 (from whyman@mwassocs.demon.co.uk) Date: Wed, 2 Jun 93 10:57:30 BST From: Tony Whyman Message-Id: <1693.whyman@mwassocs.demon.co.uk> To: big-internet@munnari.oz.au Reply-To: whyman@mwassocs.demon.co.uk Subject: Efficient Routing with Bit-oriented Address Prefixes X-Mailer: VE3PZR VIEW DIS V1.01. Lines: 263 Firstly, I am not sure if this it the best mailing list for starting off this particular discussion. However, it should be read by all interested parties, so here goes. Introduction ------------- Current trends in the development of addressing and routing imply a routing decision process that operates by comparing a destination address with a variable length bit-oriented prefix (e.g. CIDR, SIP and CLNP). This allows for route aggregation, where possible. However, this technique also appears to be at the expense of a more costly route decision process, when compared with routing on 32-bit IP addresses and by address class. This cost is likely to increase with address length. My motivation for writing this text, is to find a way of maintaining the current level of routing efficiency even when routing is performed using address prefixes. The proposal discussed below appears to decouple the cost of the routing decision from the address size and indeed whether it is fixed or variable in length. If accepted, it should enable addressing plans to be developed without being unnecessarily constrained by considerations of routing efficiency. It also appears to lead in to consideration of header compression and flows. The Route --------- A routing protocol, such as IDRP, operates between a pair of communicating routers (Boundary Intermediate Systems or BISs to use the current jargon). A BIS advertises one or more routes to each BIS with which it is in contact. Those routes are determined according to its local routing policy, and typically include at least one route to destinations within its local Routing Domain. When that policy enables packets to transit the BIS's local Routing Domain, routes received from a BIS in one Routing Domain, may also be advertised to a BIS in another Routing Domain. BISs connect up multiple Routing Domains and provide a routing topology according to how the Network Designers/Operators have (hopefully) planned it. As routes are re-advertised they may further be aggregated with other routes in order to reduce the amount of routing information disseminated. The result of this aggregation is that, in general, a route may be modelled as an inverted tree. The apex of the tree is the point at which the route is being observed from (i.e. a BIS that has received the advertisement of the route from another BIS), and the nodes of the tree, both branch and leaf nodes, represent the destinations of the route. The path a packet follows when sent from the BIS at the apex to any destination of the route is described by the structure of the tree. A example of a possible route is shown in the figure below, drawing heavily on the road network in north-west Europe for its inspiration. LONDON | | | DOVER | | | CALAIS / \ / \ / \ PARIS BRUSSELS / \ / \ / \ HAMBURG FRANKFURT In the above figure, the route from London to any of the identified cities on the continent always goes via the ports of Dover and Calais, and then fanout starts occurring. The same effect may usually be observed in data communications networks. Just as with a road network, a data comms network following a topology such as that given above is likely to have a long term stability. Change is only likely to come about either through the building of new roads (data links), or temporary problems, blocking the preferred highway. However, even though the path followed by packets, for example, from London to Brussels is stable, and generally predictable under current routing strategies, an essentially first principles routing decision is made at London, Dover and Calais, taking the destination address, and comparing it with all known address prefixes, just on the off chance that something may have changed. This is what leads to a potentially high cost routing overhead. When the destination address is a 32-bit IP address, with a known class, then there is probably not much that can be done to improve on the overhead - routing is arguably very efficient in such circumstances. However, when the routing decision is made by comparing variable length bit-oriented prefixes with the destination address, then there does appear to be scope for improvement. Caching the Routing Decision ---------------------------- If the packets between the same destination pair almost always follow the same path, then why not cache the route decision? One possibility is to create a hash table of cached routing decisions, and generate the hash index through a combination of the packet's source and destination address. In principle, that would work, however, it ignores the fact that a route is not just determined by a source and destination pair, but also by security and QoS requirements. That makes for a lot of computation in generating the has index and comparing the resulting table entry with the packet header. It may even be more costly than the routing decision itself! Another possibility is for the sender to provide additional information with the packet. For example, a 16 or 32-bit identifier. Such an identifier would uniquely identify a packet addressed to a given destination, with a specific set of security and QoS requirements, and would be repeated on every packet with the same Security and QoS requirements and to the same destination. The routing decision, once made, may be cached against this identifier. The first packet sent to a given destination and with a given combination of security and QoS requirements would be given a newly generated identifier by the sender. The sender would not be permitted to re-use the same identifier within a known time T. When it was received by next BIS, the new identifier would be recognised as new, the routing decision made, and the result of the decision cached in a table indexed by the identifier. All subsequent packets with the same identifier would then be routed by a simple look up in the cache. Cache information would be retained for a time t (t Received: from itd.nrl.navy.mil by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA11822; Wed, 2 Jun 1993 22:14:30 +1000 (from atkinson@itd.nrl.navy.mil) Received: by itd.nrl.navy.mil (4.1/SMI-4.1) id AA21694; Wed, 2 Jun 93 08:14:22 EDT Date: Wed, 2 Jun 93 08:14:22 EDT From: atkinson@itd.nrl.navy.mil (Ran Atkinson) Message-Id: <9306021214.AA21694@itd.nrl.navy.mil> To: big-Internet@munnari.oz.au Subject: Re: Efficient Routing with Bit-oriented Address Prefixes A side point, one had better not be using "security" (i.e. sensitivity labels as per RFC-1108) for routing purposes unless you have some way of authenticating ALL of your routing information and also authenticating ALL of the information in each packet header that influences routing (including that sensitivity label). One could generalise and say that this is a problem independent of "security labels". We had significant discussions in the SAAG meeting in DC last fall and the overwhelming consensus was that there was no meaningful way to route on IP labels or any kind of "security TOS" in the near term. Clearly routing without authentication has been practical for some years now (albeit undesirable). Let's please drop the references to "security" in the address length discussions. Secondly, Tony talks about most packets taking the same path. This is true for flows when all parties are at static locations. I do not believe that this is true for the mobile host situation, which is important to some of us. The implications of mobile hosts need to be addressed. It also appears that the cost of the first packet is much higher in Tony's proposal than it is at present (if not, then it needs to be explained why this is not true). This has potential implications for UDP traffic. The case of UDP traffic that doesn't behave in a flow-like manner needs to be addressed in detail. Ran atkinson@itd.nrl.navy.mil From owner-Big-Internet@munnari.oz.au Thu Jun 3 04:15:41 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA26141; Thu, 3 Jun 1993 04:15:59 +1000 (from owner-Big-Internet) Return-Path: Received: from ibeam.ht.intel.com by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA26112; Thu, 3 Jun 1993 04:15:41 +1000 (from jrb@ibeam.ht.intel.com) Received: from ishark.intel.com by ibeam.intel.com with smtp (Smail3.1.28.1 #2) id m0o0xN9-0003dLC; Wed, 2 Jun 93 11:17 PDT Received: by ishark.intel.com (Smail3.1.26.7 #9) id m0o0xKU-0004rJC; Wed, 2 Jun 93 11:14 PDT Message-Id: To: Eric Fleischman Cc: big-internet@munnari.oz.au Subject: Re: TP-IX pro/con In-Reply-To: Your message of "Tue, 01 Jun 93 16:05:59 PDT." <9306012305.AA04819@atc.boeing.com> Date: Wed, 02 Jun 93 11:14:23 PDT From: jrb@ibeam.ht.intel.com Please send the previous pros/cons discussion for SIP, et.al, and much thanks for big picture work, which seems to be sorely missing sometimes from these discussions. Jim Binkley jrb@ibeam.intel.com From owner-big-internet@munnari.oz.au Thu Jun 3 04:39:48 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA26975; Thu, 3 Jun 1993 04:40:00 +1000 (from owner-big-internet) Return-Path: Received: from mwassocs.demon.co.uk by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA20316; Thu, 3 Jun 1993 01:37:33 +1000 (from whyman@mwassocs.demon.co.uk) Date: Wed, 2 Jun 93 16:05:51 BST From: Tony Whyman Message-Id: <1719.whyman@mwassocs.demon.co.uk> To: Ran Atkinson Cc: big-internet@munnari.oz.au Reply-To: whyman@mwassocs.demon.co.uk Subject: Re: Efficient Routing with Bit-oriented Address Prefixes X-Mailer: VE3PZR VIEW DIS V1.01. Lines: 105 Ran, You have a valid point on security: > > A side point, one had better not be using "security" (i.e. > sensitivity labels as per RFC-1108) for routing purposes unless you > have some way of authenticating ALL of your routing information and > also authenticating ALL of the information in each packet header that > influences routing (including that sensitivity label). One could > generalise and say that this is a problem independent of "security > labels". We had significant discussions in the SAAG meeting in DC > last fall and the overwhelming consensus was that there was no > meaningful way to route on IP labels or any kind of "security TOS" in > the near term. Clearly routing without authentication has been > practical for some years now (albeit undesirable). Let's please drop > the references to "security" in the address length discussions. > However, the following text does, I hope make clear the sense that I was discussing security. It's text I wrote earlier and is hacked out of the ICAO specification for the Aeronautical Telecommunications Network (ATN). The second case is the more significant. "Security 2.3.16 A dialogue between two ATN users may also have security requirements associated with the dialogue, and, in such cases, the information transferred between those ATN users may need to include security related information. Security related information may be used for two purpose: a) to signal the level of protection required; b) to provide information for access control functions. 2.3.17 ATN User data may be protected by the invocation of security services specific to individual protocol layers in line with the effective Security Policy. Such security services may be end-to-end in that they provide protection for the duration of the data's transit across the ATN, or they may only be applied for part of the transit where such protection is considered necessary to protect against known vulnerabilities. A request for protection may also affect the route that the data takes through the ATN, when it is necessary for the data to follow a specific path in order for the required level of protection to be maintained. 2.3.18 Communications resources in the ATN may limit their use to certain ATN Users or classes of user data. Such resources are then said to apply access control. Access control may be applied for regulatory reasons, or for commercial reasons. For example, the Mode S subnetwork is restricted to data relating to flight safety and regularity, while commercial service providers may restrict access to their networks to customers with arranged credit facilities. In such cases, the routing functions within the ATN will ensure that data is only routed along routes that will permit the data's transit, using the security related information to determine the appropriate route." In the latter case, "2.3.18", authentication may be performed, but that has nothing to do with the routing decision. The routing decision is about avoiding an access control failure, rather than performing the access control. In this example of security, an undetected integrity failure or masquerade by the routing function may cause the data to be dumped down-stream, but this is not a security violation - except perhaps a Denial of Service if it happened often enough. The former case, "2.3.17" is what I think that you are discussing and, yes, I would agree that if a routing decision is made under these circumstances, something else is clearly necessary. However, for the "2.3.18" case, I believe that it is correct to discuss security in a routing context today, and certainly as part of a general model. > Secondly, Tony talks about most packets taking the same path. This > is true for flows when all parties are at static locations. I do not > believe that this is true for the mobile host situation, which is > important to some of us. The implications of mobile hosts need to be > addressed. It also appears that the cost of the first packet is much > higher in Tony's proposal than it is at present (if not, then it needs > to be explained why this is not true). This has potential > implications for UDP traffic. The case of UDP traffic that doesn't > behave in a flow-like manner needs to be addressed in detail. > I am also very interested in mobile hosts (i.e. aircraft). In the case of mobiles, a route will change over time, and the closer you are to the mobile, the more rapid the rate of change. However, only the part of the route that changes requires re-computation of the routing information. Furthermore, it appears possible to pre-empt the re-computation - there is no reason to wait for the next data packet - an extended encapsulation protocol could set up the path and flow identifiers in the absence of user data, as soon as the change occurs. -- Tony Whyman McCallum Whyman Associates Ltd Tel +44 962 735580 FAX +44 962 735581 Internet: whyman@mwassocs.demon.co.uk Compuserve: 100041,315 From owner-big-internet@munnari.oz.au Thu Jun 3 06:28:11 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA00987; Thu, 3 Jun 1993 06:28:26 +1000 (from owner-big-internet) Return-Path: Received: from zephyr.isi.edu by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA29048; Thu, 3 Jun 1993 05:37:11 +1000 (from postel@ISI.EDU) Received: by zephyr.isi.edu (5.65c/5.61+local-13) id ; Wed, 2 Jun 1993 12:35:13 -0700 Date: Wed, 2 Jun 1993 12:35:13 -0700 From: postel@ISI.EDU (Jon Postel) Message-Id: <199306021935.AA18831@zephyr.isi.edu> To: dee@skidrow.ljo.dec.com, roode@oas.olivetti.com, kbe@sony.craynet.dk, rching@natadm.nat.com, ycw@nat.com Subject: NETWORK NUMBER 89 Cc: iana@ISI.EDU, scottw@internic.net, domreg@internic.net, Big-Internet@munnari.OZ.AU Hello. No use what so ever of Network Number 89 is currently authorized. The use of Network Number 89 for any purpose at this time is not appropriate and should be stopped as soon as possible. --jon. From owner-Big-Internet@munnari.oz.au Fri Jun 4 04:32:20 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA25538; Fri, 4 Jun 1993 04:32:38 +1000 (from owner-Big-Internet) Return-Path: Received: from itd.nrl.navy.mil by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA25535; Fri, 4 Jun 1993 04:32:20 +1000 (from atkinson@itd.nrl.navy.mil) Received: by itd.nrl.navy.mil (4.1/SMI-4.1) id AA02838; Thu, 3 Jun 93 14:30:32 EDT Date: Thu, 3 Jun 93 14:30:32 EDT From: atkinson@itd.nrl.navy.mil (Ran Atkinson) Message-Id: <9306031830.AA02838@itd.nrl.navy.mil> To: whyman@mwassocs.demon.co.uk Subject: Re: Efficient Routing with Bit-oriented Address Prefixes Cc: big-Internet@munnari.oz.au Tony, Your followup obscured your points further rather than clarifying them, so I might not have understood you correctly. Please permit me to try to restate my views in a hopefully more clear manner. I fear we are talking past each other. If you wish to use the "security label" as a factor in selecting the route then you must have some way of verifying that the "security label" is indeed authentic for that packet and has not been changed (intentionally or accidentally) in transit. If you cannot authenticate that routing input data, then you are fooling yourself. For a packet to traverse an inappropriate or undesired route because the "security label" on that packet was not authentic is in fact a security violation. Given that we do not have a deployed internetwork authentication mechanism at present, it is undesirable to attempt to use "security labels" as part of a routing decision in the current Internet. This security problem can be somewhat generalised by observing that there are no meaningful authentication mechanisms in existing routing protocols or on other packet header fields that are used for routing. For any packet to take a route other than the desired route because of packet header field data being modified in transit is a security violation. This has NOTHING to do with "access controls" of any sort. I believe the access control reference (perhaps unintentionally) is actually a red herring in this context. Ran atkinson@itd.nrl.navy.mil From owner-big-internet@munnari.oz.au Sat Jun 5 02:01:20 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA18540; Sat, 5 Jun 1993 02:01:57 +1000 (from owner-big-internet) Return-Path: Received: from mwassocs.demon.co.uk by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA12492; Fri, 4 Jun 1993 23:41:37 +1000 (from whyman@mwassocs.demon.co.uk) Date: Fri, 4 Jun 93 13:03:57 BST From: Tony Whyman Message-Id: <1753.whyman@mwassocs.demon.co.uk> To: Ran Atkinson Cc: big-Internet@munnari.oz.au Reply-To: whyman@mwassocs.demon.co.uk Subject: Re: Efficient Routing with Bit- oriented Address Prefixes X-Mailer: VE3PZR VIEW DIS V1.01. Lines: 99 === > > Tony, > > Your followup obscured your points further rather than clarifying them, > so I might not have understood you correctly. Please permit me to try > to restate my views in a hopefully more clear manner. I fear we are > talking past each other. > Perhaps the best way that I can describe the situation that I am referring to is by giving an example. Let's assume that you play golf on your day off, and that to get from home to the golf course, a short cut exists across the naval base - in through one gate and out of the other. On your day off, you are driving to the base and as you are approaching the front gate you see the sign "all passes must be shown". You have forgotten your pass. It's quicker to drive round the base than to go back home and get it, and so that is what you do. You successfully reach the golf course. Now I would argue that you made a routing decision when you came to that sign. The base had declared an intention to make an authentication check, you know a priori that you could not pass the check, and so you changed your route. This is the situation that I was referring to. Translating this into a networking context, a Routing Domain may apply access control by authenticating the source of each packet it receives and the deciding whether to route the packet or discard it. This is not an issue if the Routing Domain is simply an End Routing Domain i.e. packets are only ever routed to it for internal destinations. However, if the Routing Domain is a Transit Routing Domain i.e. packets may be routed through it to other Routing Domains, then this may result in a problem. For example, if IDRP is used as the routing protocol, a Routing Domain may receive two (or more) routes to the same destination and must choose between them. One route may be via a Routing Domain that applies access control as discussed above, while the other is via Routing Domain that is unconstrained and relays all data. If the first route offers a lower transit delay than the second then all packets with a TOS that indicates a preference for low transit delay will get routed along the first route. This is fine for the packets that pass the access control check, but not so good for those that don't. They have disappeared down a black hole, when a perfectly good route (the second one) existed to their destination. So that this problem can be avoided, what is needed is some electronic equivalent of the "all passes must be shown" sign. The route should indicate that an access control check will be performed so that the appropriate routing decision can be made. IDRP already includes a SECURITY path attribute and I would argue that that is the appropriate place to put such a sign. It need be no more that a security policy identifier. This simply implies that the identified security policy will be applied somewhere down the route, but without indicating what is going to happen. The semantic is that the route is only suitable for packets that are known to that security policy. This may be indicated in each packet in an equally simple fashion - by the same security policy identifier in its own security parameter, perhaps as part of a more general security label. The routing decision is then straightforward - a route with a SECURITY attribute is only available to packets which identify the same security policy. Such a mechanism can be used to avoid the above problem. You may argue that the need for security mechanisms to support integrity checks, and authentication have not gone away. I would agree with you, but my point is that they are separate from the routing decision in the above example, and applied in a totally different place. The routing decision is based on security related information, but is not in itself a security mechanism, it is a routing decision based on the warning of the later application of a real security mechanism. I would argue that there is a need to consider this kind of routing decision in a general model of routing. Furthermore, the need for such a routing decision is not imaginary. In civil aviation, there are some Administrations that are making it clear that they will only relay data related to Air Traffic Control and not any old airline communication. Whether they really do implement checks to back this up remains to be seen, but we have to find a mechanism that enables this to be possible. Perhaps more realistic are service providers that are wary about relaying data from sources that are not identified customers, or perhaps on credit hold. Again some mechanism has to be found to enable this to be possible without creating black holes in the network. -- Tony Whyman McCallum Whyman Associates Ltd Tel +44 962 735580 FAX +44 962 735581 Internet: whyman@mwassocs.demon.co.uk Compuserve: 100041,315 From owner-big-internet@munnari.oz.au Sat Jun 5 05:36:21 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA25479; Sat, 5 Jun 1993 05:36:32 +1000 (from owner-big-internet) Return-Path: Received: from alpha.Xerox.COM by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA19127; Sat, 5 Jun 1993 02:18:46 +1000 (from deering@parc.xerox.com) Received: from skylark.parc.xerox.com ([13.2.116.7]) by alpha.xerox.com with SMTP id <11697>; Fri, 4 Jun 1993 09:18:01 PDT Received: from localhost by skylark.parc.xerox.com with SMTP id <12171>; Fri, 4 Jun 1993 09:17:49 -0700 From: Christian.Huitema@sophia.inria.fr, Steve Deering , Bob.Hinden@eng.sun.com, Dave Crocker To: sip@caldera.usc.edu, ip-encaps@sunroof.eng.sun.com, iesg@cnri.reston.va.us, iab@isi.edu, big-internet@munnari.oz.au Subject: SIP & IPAE groups to merge and shuffle chairs Date: Fri, 4 Jun 1993 09:17:46 PDT Sender: Steve Deering Fake-Sender: deering@parc.xerox.com Message-Id: <93Jun4.091749pdt.12171@skylark.parc.xerox.com> With Christian Huitema's election as IAB chair and the extra workload that that entails, he has decided to resign as co-chair of the SIP Working Group. With the approval of the Internet Area ADs, Bob Hinden will be taking his place as co-chair (with Steve Deering) of the SIP group. This also seems an appropriate time to terminate the separate IPAE Working Group, chaired by Dave Crocker, and have its work taken over by the SIP group, since IPAE has evolved into being the SIP transition and implementation group. This will require a modification of the SIP WG charter, which will be submitted to the IESG for approval. Christian, Steve, Bob, and Dave From owner-big-internet@munnari.oz.au Sat Jun 5 05:52:30 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA25825; Sat, 5 Jun 1993 05:52:35 +1000 (from owner-big-internet) Return-Path: Received: from mwassocs.demon.co.uk by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA17680; Sat, 5 Jun 1993 01:37:21 +1000 (from whyman@mwassocs.demon.co.uk) Date: Fri, 4 Jun 93 16:07:16 BST From: Tony Whyman Message-Id: <1763.whyman@mwassocs.demon.co.uk> To: Ran Atkinson Cc: big-Internet@munnari.oz.au Reply-To: whyman@mwassocs.demon.co.uk Subject: Re: Efficient Routing with Bit- X-Mailer: VE3PZR VIEW DIS V1.01. Lines: 89 > > I am not concerned about routing around places. One reason that we > have IP sensitivity labels is to ensure that we do not send sensitive > traffic through channels that are inappropriate for that traffic. So > if the IP label gets improperly "downgraded" from say "secret" to say > "unclassified" (or from "proprietary" to "published information" for > commercial users) whilst in transit, then that traffic might travel > via a channel that is inappropriate for the traffic sensitivity. Such > inappropriate routing constitutes a security violation and has NOTHING > to do with access controls. Non-sensitive traffic can travel using > protected links but sensitive traffic must not travel via unprotected > links. It has to do with ensuring that my sensitive traffic only uses > appropriate communications channels rather than performing access > controls on the other folks data. I think I can see now why we are having this argument. You are concerned about traffic sensitivity. I am not (at least in this instance). I am concerned with making sure that non-sensitive traffic does not disappear down a black-hole. > > Please forget access control. IP labels are not used for that kind of > access control and were not designed to be used for that kind of access > control. The concern is that data might be inappropriately "downgraded" > whilst in transit and that data might travel via unprotected links when > it needs to travel via protected links. Please go study how we actually > use IP sensitivity labels (e.g. IP Security Option labels) in more detail. > Without authentication of those labels, I would submit that using those > labels is mostly silly (perhaps on a LAN in a vault with no external > connections and everyone in the vault allowed to see all data it is OK > as it stands). Ah, but I am using the CLNP security parameter. The IP security option is certainly restricted in the way you describe. This is not true for CLNP. > > > I do not believe that this access control you discuss is in fact a problem > in the current or in the near-term Internet. Further, without a method > of having "passes" that could be authenticated, you cannot really enforce > any access control that you might wish to have -- instead you are only > fooling yourself and anyone can spoof your access controls with no real > difficulty. Mechanisms that claim to provide some security but which are > not really secure are dangerous because people get a false sense of confidence > and leave themselves more vulnerable than when they understand that they > have no real security mechanisms. > I never said that the appropriate mechansisms were not enforced somewhere. I am concerned about separating those that implement such mechanisms from those that don't or implement different ones. > > How do you propose to PREVENT me from spoofing your identifier ? Without > at least authentication of the identifier, anyone in the Internet can > forge that credential with no difficulty and violate your security policy. > Your policy is not enforceable without authentication and such implementation > would create a false sense of security and be highly undesirable. > It doesn't matter to me if someone does. The person to which it matters is responsible for enforcing their own security. If my router directs a packet down a path because someone has spoofed a security label, it doesn't matter to me, because while I was using security information as part of a routing decision, I was not enforcing any Security Policy. However, if someone does spoof the identifier then they are not going to have much luck when they get to the point at which access control is applied unless they have also managed to spoof whatever authentication mechanism is applied. Perhaps we should not continue to broadcast this argument. Its gone away from my original paper, and security was not intended to be a significant issue. What you are saying makes sense to me in the context of the communication of sensitive data. I have worked in this area. But I would argue that protection of sensitive data while in transit is only one aspect of communications security. The other is control over access to communications resources. -- Tony Whyman McCallum Whyman Associates Ltd Tel +44 962 735580 FAX +44 962 735581 Internet: whyman@mwassocs.demon.co.uk Compuserve: 100041,315 From owner-big-internet@munnari.oz.au Sat Jun 5 05:55:24 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA25912; Sat, 5 Jun 1993 05:55:27 +1000 (from owner-big-internet) Return-Path: Received: from itd.nrl.navy.mil by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA15520; Sat, 5 Jun 1993 00:43:47 +1000 (from atkinson@itd.nrl.navy.mil) Received: by itd.nrl.navy.mil (4.1/SMI-4.1) id AA22984; Fri, 4 Jun 93 10:43:29 EDT Date: Fri, 4 Jun 93 10:43:29 EDT From: atkinson@itd.nrl.navy.mil (Ran Atkinson) Message-Id: <9306041443.AA22984@itd.nrl.navy.mil> To: whyman@mwassocs.demon.co.uk Subject: Re: Efficient Routing with Bit- Cc: big-Internet@munnari.oz.au % From whyman@mwassocs.demon.co.uk Fri Jun 4 09:42:23 1993 % Date: Fri, 4 Jun 93 13:03:57 BST % Message-Id: <1752.whyman@mwassocs.demon.co.uk> % To: Ran Atkinson % Cc: big-Internet@munnari.oz.au % Reply-To: whyman@mwassocs.demon.co.uk % Subject: Re: Efficient Routing with Bit... % Now I would argue that you made a routing decision when you came to that % sign. The base had declared an intention to make an authentication check, % you know a priori that you could not pass the check, and so you changed % your route. This is the situation that I was referring to. One obvious problem is that we do not have the moral equivalent of a "pass". In effect, when the gate guard checks for your pass he is authenticating you and your right to pass through the gate. We don't have anything like a pass because we cannot authenticate anything in the IP header (right now in the deployed Internet). % Translating this into a networking context, a Routing Domain may apply % access control by authenticating the source of each packet it receives and % the deciding whether to route the packet or discard it. This is not an % issue if the Routing Domain is simply an End Routing Domain i.e. packets % are only ever routed to it for internal destinations. However, if the Routing % Domain is a Transit Routing Domain i.e. packets may be routed through it to % other Routing Domains, then this may result in a problem. I am not concerned about routing around places. One reason that we have IP sensitivity labels is to ensure that we do not send sensitive traffic through channels that are inappropriate for that traffic. So if the IP label gets improperly "downgraded" from say "secret" to say "unclassified" (or from "proprietary" to "published information" for commercial users) whilst in transit, then that traffic might travel via a channel that is inappropriate for the traffic sensitivity. Such inappropriate routing constitutes a security violation and has NOTHING to do with access controls. Non-sensitive traffic can travel using protected links but sensitive traffic must not travel via unprotected links. It has to do with ensuring that my sensitive traffic only uses appropriate communications channels rather than performing access controls on the other folks data. % For example, if IDRP is used as the routing protocol, a Routing Domain may % receive two (or more) routes to the same destination and must choose % between them. One route may be via a Routing Domain that applies access % control as discussed above, while the other is via Routing Domain that is % unconstrained and relays all data. If the first route offers a lower % transit delay than the second then all packets with a TOS that indicates a % preference for low transit delay will get routed along the first route. % This is fine for the packets that pass the access control check, but not so % good for those that don't. They have disappeared down a black hole, when a % perfectly good route (the second one) existed to their destination. Please forget access control. IP labels are not used for that kind of access control and were not designed to be used for that kind of access control. The concern is that data might be inappropriately "downgraded" whilst in transit and that data might travel via unprotected links when it needs to travel via protected links. Please go study how we actually use IP sensitivity labels (e.g. IP Security Option labels) in more detail. Without authentication of those labels, I would submit that using those labels is mostly silly (perhaps on a LAN in a vault with no external connections and everyone in the vault allowed to see all data it is OK as it stands). % So that this problem can be avoided, what is needed is some electronic % equivalent of the "all passes must be shown" sign. The route should % indicate that an access control check will be performed so that the % appropriate routing decision can be made. I do not believe that this access control you discuss is in fact a problem in the current or in the near-term Internet. Further, without a method of having "passes" that could be authenticated, you cannot really enforce any access control that you might wish to have -- instead you are only fooling yourself and anyone can spoof your access controls with no real difficulty. Mechanisms that claim to provide some security but which are not really secure are dangerous because people get a false sense of confidence and leave themselves more vulnerable than when they understand that they have no real security mechanisms. % IDRP already includes a SECURITY path attribute and I would argue that that % is the appropriate place to put such a sign. It need be no more that a % security policy identifier. This simply implies that the identified % security policy will be applied somewhere down the route, but without % indicating what is going to happen. The semantic is that the route is only % suitable for packets that are known to that security policy. Unless you authenticate each IDRP packet and transaction, I can force your data to travel via my systems by forging IDRP packets which claim that all other routes have some security policy. For me to force your packets to travel via routes under my control is a significant security violation. This is a big problem. Adding that sign makes it EASIER for Internet security to be violated than not adding that sign until we have some stronger authentication mechanisms in place. % This may be indicated in each packet in an equally simple fashion - by the % same security policy identifier in its own security parameter, perhaps part % of a more general security label. The routing decision is then straight % forward - a route with a SECURITY attribute is only available to packets % which identify the same security policy. Such a mechanism can be used to % avoid the above problem. How do you propose to PREVENT me from spoofing your identifier ? Without at least authentication of the identifier, anyone in the Internet can forge that credential with no difficulty and violate your security policy. Your policy is not enforceable without authentication and such implementation would create a false sense of security and be highly undesirable. % You may argue that the need for security mechanisms to support integrity % checks, and authentication have not gone away. I would agree with you, but % my point is that they are separate from the routing decision in the above % example, and applied in a totally different place. The routing decision is % based on security related information, but is not in itself a security % mechanism, it is a routing decision based on the warning of the later % application of a real security mechanism. They are not separate. Without authentication you cannot actually implement any kind of policy because I can easily violate your would-be policy without you having any way to detect it. I can also cause other security violations (an example is described above) because you have added this new mechanism that is very conveniently subvertable by an intruder. In effect, you reduce the effective security by implementing your mechanism without simultaneously implementing authentication of IP datagrams and the routing protocols. % Furthermore, the need for such a routing decision is not imaginary. In % civil aviation, there are some Administrations that are making it clear % that they will only relay data related to Air Traffic Control and not any % old airline communication. Whether they really do implement checks to back % this up remains to be seen, but we have to find a mechanism that enables % this to be possible. Perhaps more realistic are service providers that are % wary about relaying data from sources that are not identified customers, or % perhaps on credit hold. Again some mechanism has to be found to enable this % to be possible without creating black holes in the network. I can make other customers pay for my Internet traffic right now if I wish to. I can also subvert all of the would-be policy mechanisms. It would be easy to send any old airline communication via the ATC channels unless both the IP traffic AND the routing protocols are authenticated. There is ongoing work in the IETF on a security protocol for IPv4. At the moment it appears that authentication without confidentiality might not be an offered service. I personally believe that we do need authentication without confidentiality and I personally believe that there are a lot more customers who desire that than that desire confidentiality and authentication. Security issues have to be addressed comprehensively and wholistically. They cannot be separated out from routing or other matters. We should not be implementing mechanisms that will reduce security in the current Internet and claim that we are doing it in order to help with security. Regards, Ran atkinson@itd.nrl.navy.mil Naval Research Laboratory Washington, DC, USA P.S. It isn't clear to me that this discussion is of general interest to the big-Internet community. If folks think it should be taken off the list, please drop an email or something... :-) From owner-Big-Internet@munnari.oz.au Sat Jun 5 13:04:07 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA04622; Sat, 5 Jun 1993 13:04:17 +1000 (from owner-Big-Internet) Return-Path: Received: from nsco.network.com by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA04618; Sat, 5 Jun 1993 13:04:07 +1000 (from jmh@anubis.network.com) Received: from anubis-e1.network.com by nsco.network.com (5.61/1.34) id AA25638; Fri, 4 Jun 93 22:06:28 -0500 Received: from gramarye.network.com by anubis.network.com (4.1/SMI-4.1) id AA17621; Fri, 4 Jun 93 22:03:18 CDT Date: Fri, 4 Jun 93 22:03:18 CDT From: jmh@anubis.network.com (Joel Halpern) Message-Id: <9306050303.AA17621@anubis.network.com> To: whyman@mwassocs.demon.co.uk Subject: Re: Efficient Routing with Bit-oriented Address Prefixes Cc: big-internet@munnari.oz.au In the abstract, what you propose is already done by all high performance routers, without any help from the originating end-systems. You suggest that the header addressing information is redundant. It is not. You can not actually expect the cache on the backbone to remain current. Since the end-system can not predict when the cache may be flushed, the information must be kept in all packets. Please note that source-destination pair caching is MUCH more resource intensive than the destination based caching we currently use. The number of distinct source-destination pairs flowing through the internet backbone at any given time is amazing, and growing faster than the number of connected endpoints. Please do not require us to keep pairwise state in the routers. Thank you, Joel M. Halpern jmh@network.com Network Systems Corporation From owner-Big-Internet@munnari.oz.au Sat Jun 5 21:43:36 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA12756; Sat, 5 Jun 1993 21:43:39 +1000 (from owner-Big-Internet) Received: from mundamutti.cs.mu.OZ.AU by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA12753; Sat, 5 Jun 1993 21:43:36 +1000 (from kre@munnari.OZ.AU) Received: from ub-gate.UB.com by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA10977; Wed, 2 Jun 1993 10:10:57 +1000 (from solensky@andr.UB.com) Return-Path: Received: from sunny.andr.UB.com (sunny.andr.UB.com) by ub-gate.UB.com (4.1/SMI-4.1[UB-1.8]) id AA13138; Tue, 1 Jun 93 17:10:49 PDT Received: from fenway.andr.UB.com by sunny.andr.UB.com (4.1/SMI-4.1) id AA08181; Tue, 1 Jun 93 20:10:48 EDT Received: by fenway.andr.UB.com (4.1/SMI-4.1) id AA05970; Tue, 1 Jun 93 20:10:47 EDT Date: Tue, 1 Jun 93 20:10:47 EDT From: solensky@andr.UB.com (Frank T Solensky) Message-Id: <9306020010.AA05970@fenway.andr.UB.com> To: kre@munnari.oz.au Subject: New "growth" charts Resent-To: Big-Internet@munnari.OZ.AU Resent-Date: Sat, 05 Jun 1993 21:43:21 +1000 Resent-Message-Id: <17170.739280601@munnari.OZ.AU> Resent-From: Robert Elz Updated growth charts should now be available via anonymous ftp at munnari.oz.au:~big-internet/nsf-netnumbers-9306.ps. There are now 12,349 advertised network numbers compared to 5515 at this time last year, representing an annual growth rate of 123.92%. The predicted value of 11591 nets for June 1 was passed on the 10th of the month. The "best-fit" logistic curve though the existing data also continues to accelerate: the curve now levels off at approximately 23.1 million network numbers, compared to about 13.3 million at the end of April and 15208 this time last year. I've put two trend lines on the "Total Networks" charts to give the viewer some idea of how last months' and this months' trend lines compare to each other. On the semi-log graph, I've also added a line to represent the max number of IPv4 nets at 2.11+ million net numbers. At current rates, that maximum will be exceeded in mid-2000 (keeping in mind that the projections are simple extensions of historic growth trends). The prediction for July 1 being at 12,449 net numbers (current + 100) suggests that the trend line for the short-term future may still be running on the conservative side. -- Frank From owner-Big-Internet@munnari.oz.au Mon Jun 7 19:38:25 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA08370; Mon, 7 Jun 1993 19:38:57 +1000 (from owner-Big-Internet) Return-Path: Received: from gate.demon.co.uk by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA08333; Mon, 7 Jun 1993 19:38:25 +1000 (from whyman@mwassocs.demon.co.uk) Received: from mwassocs.demon.co.uk by gate.demon.co.uk id aa00695; 7 Jun 93 10:37 BST Date: Mon, 7 Jun 93 09:11:01 BST From: Tony Whyman Message-Id: <1788.whyman@mwassocs.demon.co.uk> To: Joel Halpern Cc: big-internet@munnari.oz.au Reply-To: whyman@mwassocs.demon.co.uk Subject: Re: Efficient Routing with Bit-oriented Address Prefixes X-Mailer: VE3PZR VIEW DIS V1.01. Lines: 67 > From: Joel Halpern > > In the abstract, what you propose is already done by all high performance > routers, without any help from the originating end-systems. I really don't follow what you are trying to say here. Firstly my text was mainly concerned with routing using IDRP, and I just referred to the possibility of also using the approach with Hosts/ESs. Secondly, are you trying to tell me that a similar protocol already exists? If so, I'd be interested to see the specification, as it's obviously something that I've missed. > > You suggest that the header addressing information is redundant. It is not. > You can not actually expect the cache on the backbone to remain current. > Since the end-system can not predict when the cache may be flushed, the > information must be kept in all packets. Perhaps I should have stated the underlying assumption i.e. that once a router accepts a local identifier from another router, it implicitly agrees to maintain the cached information. Perhaps the problem is in the word cache. Directory may be better. A proper specification of the protocol would also include an error response to signal loss of cached data. Also, the proposal is for strictly local identifiers. A problem on one link should not impact any other. > > Please note that source-destination pair caching is MUCH more resource > intensive than the destination based caching we currently use. The > number of distinct source-destination pairs flowing through the internet > backbone at any given time is amazing, and growing faster than the > number of connected endpoints. Please do not require us to keep pairwise > state in the routers. As my text develops, there is a subtle change from destination based caching to source/destination caching. That is to allow for compression of the entire header. Inevitably there is a tradeoff here between bandwidth utilisation and router memory size, and I would always see compression as being an optional extension because of this, that may be used on some links and not on others. > > Thank you, > Joel M. Halpern jmh@network.com > Network Systems Corporation > > Perhaps it's also worth pointing out that there is some underlying work behind the idea that I floated. The origin is a specification for compression of CLNP over low bandwidth mobile subnetworks. This specification came from concerns over network bandwidth and cost, and immediately generated similar concerns from the router developers, to those aired above. The network won. I floated the concept in a wider forum, not so much because of the compression angle, but because the same technique appeared to enable faster routing and be applicable to resource management, with compression being almost an incidental and certainly optional. -- Tony Whyman McCallum Whyman Associates Ltd Tel +44 962 735580 FAX +44 962 735581 Internet: whyman@mwassocs.demon.co.uk Compuserve: 100041,315 From owner-big-internet@munnari.oz.au Sat Jun 12 17:59:14 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA17593; Sat, 12 Jun 1993 17:59:23 +1000 (from owner-big-internet) Return-Path: Received: from mwassocs.demon.co.uk by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA12371; Sat, 12 Jun 1993 00:15:47 +1000 (from whyman@mwassocs.demon.co.uk) Date: Fri, 11 Jun 93 08:57:50 BST From: Tony Whyman Message-Id: <1882.whyman@mwassocs.demon.co.uk> To: big-internet@munnari.oz.au Reply-To: whyman@mwassocs.demon.co.uk Subject: Re: Comments on Internet Draft on SIP 64-bit Addressing X-Mailer: VE3PZR VIEW DIS V1.01. Lines: 215 ====== Thank you for your clearly restrained response to my comments on SIP addressing. As requested, I have transferred the discussion to the big internet list. The following message is forwarded: > Date: Mon, 7 Jun 93 15:45:50 EDT > From: William Allen Simpson > Message-Id: <1240.bill.simpson@um.cc.umich.edu> > To: whyman@mwassocs.demon.co.uk > Reply-To: bsimpson@morningstar.com > Subject: Re: Comments on Internet Draft on SIP 64-bit Addressing > > I see that no one has bothered to reply to you while I was away. > > Unfortunately, I don't have a lot of time either. But here's an > acknowlegement that I received your message. > > As to your comments, the SIP list is for implementors. Discussion of > perceived differences between the proposals is best kept to the > big-internet list. SIP already has 3 interoperable implementations, > and is working on enhancements, not basic design. Unfortunately, I mis-read the text at the start of your internet draft "Administrative Allocation of the 64-bit Number Space". It said that "Comments on this memo should be submitted to the sip@caldera.usc.edu." It was obviously stupid of me not to realise that this should have been read as big-internet. It also escaped my attention that SIP is already perfect. > > I will speak briefly to most of your points. > > > 1) This plan is all about administration. I cannot find a reference to a > > proposed topology or routing strategy. How can this plan be validated > > without at least a model topology and routing strategy? > > > It clearly says allocation in the title -- why then are you surprised? > > You don't understand the current methods of IP routing? The routing > method is already used in IP, and the current topology is the topology. > > No need to restate the obvious. > The proposed SIP addressing model appears to owe more to CIDR than the current methods of IP routing (and the flat IP address space). CIDR has only scratched the surface of policy based routing and how addressing and routing interact. An addressing plan is more than just allocation; its relationship with topology will have a major impact on the potential for route aggregation and the overall efficiency of routing. I did not think it wrong to ask that the SIP addressing plan justify itself against a model topology and an assumed routing strategy. If you think that routing based on address prefixes is just like good old IP then you may be in for some surprises. > > 2) The plan is geographical, and seems very CCITT like (c.f. E.163, > > X.400) in its approach to address allocation. However, there are known > > problems with these type of plans. X.400 country oriented addressing > > > > 3) What about international mobiles? For example, X.121 supports > > international maritime services. Also, ICAO is planning a network for > > the most internationally mobile of them all - aircraft. > > > The plan allocates 1/8 of the space for such use. Perhaps you think > that more than 1/8 of the population is expected to be simultaneously at > sea or in the air by 2025? > Where is this allocation specified? Perhaps I also mis-read "reserved for future use" on page 6 for "mobile". > > 4) Who will operate the scheme in each country, decide on how each > > country's address space is allocated, etc.? > > > Already clearly stated. Continental, regional, country. Just as it is now. > It is not clearly stated. Firstly, I can only see country as the allocation unit. For example, I cannot see a European address space separate from the UK one i.e. the UK address space is totally subordinate to the European address space; it is not possible to advertise a "European" address prefix that is not also an address prefix for the UK. Secondly, some organisation has to be responsible for allocation within each country. Thirdly, I do not see any relationship between current IP address allocation and countries. So, how is the plan to be administered? > > 5) Europe is trying to move to a free market in communications services. > > > UK and France are already both in the same cluster. I begin to think > you didn't actually read the text. > > Any U.K. provider stupid enough to allocate all of his resources in > France to his U.K. space (and refuses to interconnect with French > providers), deserves to run out of allocation. > > The beauty of the clustering is that we won't notice such stupidity here > in the U.S. It stays a local problem. It is easy to take a scornful view of service providers that do not interconnect, but interconnection of service providers is one of the most closely fought of all commercial issues. It is naive to assume that service providers will interconnect as a matter of course, unless it is in their commercial interests to do so. Otherwise, it just doesn't happen unless the regulatory regime forces it. The addressing plan should respect the way service providers want to operate and interconnect, and permit efficient route aggregation within the natural interconnection framework and not one artificially constrained to geographical countries. > > > 6) The UK, for example, appears to have been allocated a shade under 7 > > octets, for its address space. A numbering plan for OSI NSAP Addresses > > > OSI NSAPs are of no consequence to this plan. This is a 64-bit plan. > True in that with OSI there is no need to attempt to squeeze a quart into a pint pot. Otherwise, the objective is identical. By referencing an existing addressing plan that has already attempted to tackle the same problem, it is possible to gain insights that might otherwise have been overlooked. > > Take an example of a service provider trying to reach every home in the > > UK, within a five octet address space. The current UK telephone > > numbering plan has 3 digits for the area code and 6 digits for > > exchange/subscriber number. Based on this, a service provider trying to > > > Any fool can try using phone numbers as an allocation scheme. Such a > plan wastes over 99.5% of the space in 10 digits (5 octets). The beauty > of this plan is that it localizes such stupidity to a single country. > > If they waste 99.5% of their space, and want more, it is pretty easy to > tell them "go use more of what you already have." > The most surprising thing about your response is the obvious similarity between the SIP addressing plan and the international telephone numbering plan. Do not expect the outcome to be very different. > > 7) The text on page 2 - "organizations which refuse to interconnect within > > continents, clusters or countries" - suggests a somewhat unrealistic > > attitude. What about militaries which interconnect in line with their > > operational deployments, or the existing world-wide airline reservation > > systems? Such organisations are not as unusual or as awkward as the > > text seems to imply. > > > The plan is organized around likely interconnects, clearly specified. > > When compared to 4 billion people, such organizations *are* unusual, > numbering in the dozens. and hence of no consequence whatsoever? > > Organizations do not use computers, people do. Ever heard of EDI? > > > 8) The text on page 4 in respect of population seems to be implying a flat > > address space within each country. Within each country there will be a > > need to structure addresses, and a more realistic projection of address > > space utilisation should be provided. > > > The text takes no position on the internal structure of country's space. > That is left to the individual country. As above, the beauty of the > plan is that such details are unnecessary, and damage from bad decisions > is clearly limited. So, if SIP addresses are nationally implemented in anything other than a nearly flat address space, then you will run out of addresses. > > > 9) There is no discussion of the implications of this plan on charging > > plans, or even the assumptions that have been made. This is not a > > trivial issue. The most limiting factor in agreeing changes to the > > X.400 Addressing Plan is the Charging Plan adopted by ADMDs, and how > > the route and hence the cost is inferred from address. > > > The plan deliberately takes no position on charging. We are _truly_ > sorry that OSI can't get it right. This has nothing to do whatsoever with OSI. Service Providers need to be able to publish a tarrif that relates to destination addresses and, as I pointed out, the operational experience is that once a particular charging plan is up and running then change is almost out of the question given the commercial interests involved. It's better to get the issues out of the way before everything gets set in concrete. > > But I've already used the word stupidity too many times in this message. > Yes, I had noticed. It was obviously stupid of me to think that you were interested in any comments. > Bill.Simpson@um.cc.umich.edu > I cannot help but be worried about the assumption that just by doubling the size of the address, the original IP addressing and routing model will simply scale, and that's it. Furthermore, commercial and regulatory issues may not have bothered the internet much in the past, but a consequence of its expansion is that they will be unavoidable in the future. They cannot be just ignored. -- Tony Whyman McCallum Whyman Associates Ltd Tel +44 962 735580 FAX +44 962 735581 Internet: whyman@mwassocs.demon.co.uk Compuserve: 100041,315 From owner-Big-Internet@munnari.oz.au Sun Jun 13 09:00:13 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA15465; Sun, 13 Jun 1993 09:00:25 +1000 (from owner-Big-Internet) Return-Path: Received: from GINGER.LCS.MIT.EDU by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA15462; Sun, 13 Jun 1993 09:00:13 +1000 (from jnc@ginger.lcs.mit.edu) Received: by ginger.lcs.mit.edu id AA04963; Sat, 12 Jun 93 19:00:02 -0400 Date: Sat, 12 Jun 93 19:00:02 -0400 From: jnc@ginger.lcs.mit.edu (Noel Chiappa) Message-Id: <9306122300.AA04963@ginger.lcs.mit.edu> To: big-internet@munnari.oz.au, whyman@mwassocs.demon.co.uk Subject: Re: Comments on Internet Draft on SIP 64-bit Addressing Cc: jnc@ginger.lcs.mit.edu An addressing plan is more than just allocation; its relationship with topology will have a major impact on the potential for route aggregation and the overall efficiency of routing. Exactly. The addressing plan should respect the way service providers want to operate and interconnect, and permit efficient route aggregation within the natural interconnection framework and not one artificially constrained to geographical countries. I concur. Addresses need to be based, first and foremost, on the actual network topology. Without real links over which traffic can flow, it's utterly useless to the routing to hand out addresses which indicate a close relationship. I cannot help but be worried about the assumption that just by doubling the size of the address, the original IP addressing and routing model will simply scale, and that's it. Furthermore, commercial and regulatory issues may not have bothered the internet much in the past, but a consequence of its expansion is that they will be unavoidable in the future. They cannot be just ignored. My concern exactly. The challenge to routing in the Internet in the future is not going to be simply "give acceptably efficicent routes from X to Y with an acceptable level of routing overhead, treating all nodes/links as more or less homogeneous". Rather, routing will have to concern itself with many, many more issues, *among* which are the policy and commercial concerns you mention. Among the consequences of this are that we will need to name topological aggregates based on many consideration other than just "minimizing routing overhead"; we'll want to name areas in which policies apply, areas which have certain charging rules, etc, etc. I have a hard time believing that there is enough flexibility in 64 bits to do so, and this alone makes SIP unacceptable. Here's an old message I sent to one of the SIP backers, which I think put the point pretty well: Sorry, I just don't think a 64-bit field is going to be big enough to give topologically and policy sensitive addresses to the global Internet. For instance, this very example shows you can't use an IEEE inside a globally useful SIP address. Well, you say, that's not so bad, ARP still works, but consider, you still have to assign local "small numbers", and set up the translations; of course, you could do the assignment dynamically, but then you've got problems getting the correct information into DNS (securely if need be), and DNS caches everywhere. Even worse, the same is true of WAN addresses such as X.121, and the assignment of small numbers, and the resolution from those numbers to the X.121 equivalents is a hard problem. ... 64 bits might be enough if i) you could impose a rational heirarchy all the way down (which we all know is not possible :-), ii) you didn't need to embed any large other addresses (e.g. IEEE or X.121) in it, and iii) and all you had to worry about was expressing topology, not policy aggegates. However, the latter alone is going to be enought to unavoidably trip up any calculation that 64 bits is enough. Policy routing (the only kind we're going to have in 5 years when the Internet is fully commercial) is going to need to make policy statements about topology aggregates, and the *only* way to name these aggregates is through addressing abstractions. 64 bits is going to get burned up pretty quick. However, it's more than just the addressing which doesn't measure up. The whole model where routers make an independant decision on each packet they see, based solely on information in the packet, doesn't seem to fit well into this more complex model of the future. In fact, this leads to what I consider to be the chief basic failing of SIP, which is exactly the same as what I reckon is the chief basic failing of CLNP and the whole ISO stack: it's different from TCP/IP, but not different enough to be interesting or really useful. Both suffer from a lack of expressed design vision. Noel From owner-Big-Internet@munnari.oz.au Mon Jun 14 07:27:10 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA25401; Mon, 14 Jun 1993 07:27:19 +1000 (from owner-Big-Internet) Return-Path: Received: from thumper.bellcore.com by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA25398; Mon, 14 Jun 1993 07:27:10 +1000 (from francis@thumper.bellcore.com) Received: by thumper.bellcore.com (4.1/4.7) id for big-internet@munnari.oz.au; Sun, 13 Jun 93 17:27:05 EDT Date: Sun, 13 Jun 93 17:27:05 EDT From: francis@thumper.bellcore.com (Paul Francis--formerly Tsuchiya) Message-Id: <9306132127.AA08558@thumper.bellcore.com> To: big-internet@munnari.oz.au Subject: What goes around comes around or: There is nothing new under the Sun(shine) or: How to quote history to further your aims or: A blast from the past or: If we do not learn from history, we are bound to repeat its mistakes Gang, As some of you may know, Pip is the topic of my PhD thesis. Naturally in the course of writing a thesis, one must cite relavent work, so I went digging.... What I found is that, 1) Pip had already largely been invented, by Jon Postel in RFC730 (Extensible Field Addressing), and 2) that all the current "discoveries" about addressing and routing had already been made, in a flurry of creative activity, in 1977 and 1978, by Postel, Sunshine, Cohen, Clark, Cerf, and perhaps others who didn't bother putting out IENs (or whose IENs or other publications I haven't bothered to read). So, for those of you who don't mind taking a few minutes to stroll down memory lane (though most of your memories, and mine, don't go back this far), and listening to platitudes about Pip, I offer the following.... The opening paragraph in Postel's May 1977 RFC730, "Extensible Field Addressing", says: This memo discusses the need for and advantages of the expression of addresses in a network environment as a set of fields. The suggestion is that as the network grows the address can be extended by three techniques: adding fields on the left, adding fields on the right, and increasing the size of individual fields. Carl Sunshine has described this type of addressing in a paper on source routing [1]. Well, right here in a nutshell is Pip. Postel's fields are nothing more than my FTIFs (forwarding table index fields), which allow adding fields on the left, the right, making them bigger, and adding in the middle (which Jon's can do too, but he doesn't mention it above). So, now you know. Pip stands for Postel's internet protocol--though I should be careful, as Jon credits Carl Sunshine as having described that type of addressing first. To give credit where it is due, I'm thinking of changing the name of Pip to Sip--Sunshine's internet protocol--or maybe SipV0, since it predates that other SIP.... Later in the RFC, Jon says: The prospect of interconnections of networks to form a complex multinetwork system poses additional addressing problems. The new Host-IMP interface specification has reserved fields in the leader to carry network addresses [2]. There is experimental work in progress on interconnecting networks [4, 5, 6]. We should be prepared for these extensions to the address space. Talk about understatement! And later still...... A problem with simple field addressing is the desire to specify only the fields that are necessary given the local context. A program interpreting the address is then unsure what the first field represents. Some clues are needed in the address specification for correct parsing to be possible. Dave Crocker has described a syntax for a similar problem in network access of data [8]. Pip does this too (puts only the necessary fields in the address). Pip uses the Routing Context field as the "clue" for correct parsing of the fields. And, now it is known that Dave Crocker is one of the original Pip contributors. Come out of the closet Dave!!! Jon gets to the meat of the thing in the following excerpt: Specific Sugestion Specifically i suggest that we adopt a field based extensible address scheme where each field is separated from its neighbors by a delimiter character and each field has a name. When an address is specified the name of the most general field must also be indicated. Definitions:
::= ":" ::= "NET" | "IMP" | "HOST" | "MESSAGE-ID" ::= | "/" ::= a decimal number Well, (my) Pip has a few differences from this, but the basic idea is there. Something to give the context of the field to be parsed (my Routing Context = Jon's field-name), and a series of fields (mine are binary not decimal, but had Jon's found their way into a packet, I'm sure they would have been binary). Perhaps the major difference between my Pip and Jon's Pip is that my Pip uses a source route mechanism for parsing the fields, whereas Jon's (though he really didn't get down to that level of specificity) presumably always parses the fields starting at the left-most one. In April of 1978, Danny Cohen shed more light on the nature of addresses in his IEN31, "On Names, Addresses and Routings (II)". After a long rambling introduction, Danny gets to the point, which is: I HATE TO ADMIT IT, BUT ... At the beginning of this note, and in an earlier note, I used a great line telling that "names tell what the processes are, and addresses tell where they are." It continues by "routings tell how to get there." I hate to admit that by now I have some reservations about this definition. My name is "Danny." My address is "ISI." When I was at Tech, my name was the same, but the address was different. This supports the definition. How about the addresses in a broadcasting media network? When a host changes its position (location) on the same Ethernet, its address does not change. Well, maybe these addresses are not real addresses, according to the definition. Admittedly, this is an uncomfortable thought. I believe that there is a better explanation. I suggest that an address is "the canonic routing from the root of the addressing-tree." It sounds recursive, doesn't it? To be more precise, an addressing scheme is a hierarchical organization of elements, with code assignment such that each element has a unique set of codes, corresponding to its position in the hierarchy. The notion that the address tells how-to-get-there from the root of the tree is very similar to the notion that absolute coordinates are really relative, with respect to the origin. Since we know (by default) how to get from the source to the UA root, and since the address tells how to get to the destination from the root, the address tells how to get from the source to the destination. Hence, by definition, addresses are routings. Yes! Addresses are routes! Well, perhaps the fact that Danny said this 15 years ago still won't help convince those doubters that still believe that addresses are addresses. Sigh.... Later on in the IEN Danny makes a proposal: Our proposal for addressing and routing is as follows: * Establish a UA scheme, of variable level structure. (UA is Universal-Address, such as the Pip Address......) * Disseminate as much knowledge to each participating node as deemed practical. * Allow the option of routing to be included in the headers of the messages. * Refuse delivery of messages to a destination with unknown routing * Establish internet-directory-assistance service. This last bit is crucial. Internet-directory-assistance (now known as DNS) must advertise the "route" from the root of the hierarchy to the leaves. In particular, if the packet format is a variable length string of fields, then DNS should advertise that string, ala Pip. So, at this point in the discourse (April 1978), Postel has provided the address format, and Cohen the architectural underpinning from which to understand that address. So, what happened? Why did we end up with IP and not Pip? We find a clue to the answer from IEN46, written by Clark and Cohen in June of 1978 called "A Proposal for Addressing and Routing in the Internet". After discussing several problems with routing and addressing, they make the following statement: The solution which has been proposed in the past to cope with this is to replace the address in the packet whith a route, called a source route since it is provided by the source of the packet. The disadvantage of having a route in a packet instead of an address is that the concept of an address is very useful one. For example, for accounting purposes it may be necessary to note the source and destination of a packet as it passes through a transit net. Clearly, it is desirable that the source and destination be uniquely identified for this purpose, something not easily done if the source and destination are specified only by a route. Thus, we propose that the address continue to be the primary piece of information in the packet, but that it be possible to include, in addition, an optional source route. So, here they recognize the need for a compact, simple, fixed length *something* to identify the source and destination of a packet. Sounds like the EID to me! So, the need for both an identifier and an "address" (still at that time arguable to be a route.....) was clearly recognized. However, they added the source route to handle the routing bit, and kept the address as the primary piece of information. I think this would have been fine except for the crucial thing mentioned by Cohen in IEN31: * Establish internet-directory-assistance service. Well, this was established, but it didn't contain the source route, just the address. So, the "routing" information in the packet was effectively limited to 32 bits. I was interested to find the following in the Clark/Cohen paper: 5. Migration What is the relationship between the scheme proposed here and the current internet header with a fixed size address field? Happily, adoption of the Huh? In 1978 they were worried about migration? Scheeese! addressing strategy involving regions together with the optional internet source route implies no immediate upheaval to packet formats or gateway code. Currently, every network is a region, and every gateway thus contains code for doing inter-region routing. Eventually, gateways will want to be modified as follows. When a region finally is defined which contains more than one network, then gateways inside that region will need to understand an additional component of the internet address. Thus, unless gateway code is rewritten for different regions, it will be necessary to write code which can deal, eventually, with a variable size component of the address. The address itself, however, can reasonably be a fixed size, since it is merely an address and not a route. In fact, it seems that the field as specified for the current internet header is sufficient in size, although perhaps marginally so. Well, something happened here. An argument was put forth that 32 bits is enough because the address doesn't have to do routing--the source route can handle the rest. Clearly it was recognized that a variable length *something* was needed, but the source route was deemed sufficient for that, and the 32-bit address won out in the end. So, perhaps what killed IP is not that the address is too short (though probably it is), but that the ability for DNS to hand a host a source route (which it could then put in the header so that the right thing could happen in the network) was not created. So, in fact Pip is a combination of Postel's Extensible Field Addressing (EFA) and Clark and Cohen's "address", though the "routing" part of the "address" has been largely moved over to the EFA (FTIF Chain), and the "address" (ID) is left with minimal routing role (the last hop) and identification. As an aside, if we go with SIP, I would strongly encourge the ability to advertise source routes by DNS, which can be handed to hosts, which will obediantly put them in the header. This, for all practical purposes, makes the SIP "address" variable length, thus allowing for more flexibility in routing and addressing, for instance policy routing. Such a scheme, I think, would be much closer to what IP was intended to be (at least by some). An IEN from Cerf the following month (July 1978) seems to meld with Clark/Cohen (IEN48, "The Catenet Model for Internetworking"). It generally confirms the Clark/Cohen proposal. It, however, has some interesting statements of its own: In order to limit the overhead of address fields in the header, it was decided to restrict the maximum length of the host portion of the internet address to 24 bits. The possibility of true, variable-length addressing was seriously considered. At one point, it appeared that addresses might be as long as 120 bits each for source and destination. The overhead in the higher level protocols for maintaining tables capable of dealing with the maximum possible address sizes was considered excessive. Not only is it interesting that a longer address (120 bits, almost as long as an NSAP), was seriously considered, but the reason for not going with it (memory overhead to "upper layer protocols") really shows how times have changed. Finally, Cerf's IEN seems to delegate source routing to its current, and very limited, role: One of the major arguments in favor of variable length "addressing" is to support what is called "source-routing." The structure of the information in the "address" really identifies a route (e.g., through a particular sequence of networks and gateways). Such a capability could support ad hoc network interconnections in which a host on two nets could serve as a private gateway. Though it would not participate in catenet routing or flow control procedures, any host which knows of this private gateway could send "source-routed" internet datagrams to that host. I find it interesting that the original ideas of Postel and Cohen (very Pip-like) evolved into the source route, which was then limited to a "special service" role (i.e., routing a packet through a private host on two nets). I guess I would characterize Pip has trying to get back to some of the earliest ideas on internet addressing and routing. PX ps..... By the way, I hope this little diatribe is in no way interpreted as a criticism of the work of Cerf, Postel, Clark, Cohen, Sunshine and others (Boggs, Shoch, Metcalfe, and many others). They're work is nothing short of brilliant, and the fact that we are doing nothing but rehash 15-year-old arguments is testimony to that. In particular, one could conjecture that, had the Extendable Field Addressing idea won the day, the resulting complexity might have prevented the internet from growing the way it did. (I certainly don't conjecture this, but one *could* :-). I hope somebody out there enjoyed reading this as much as I enjoyed discovering and writing it. I would love to get war stories from the participants on what *really* happened..... From owner-Big-Internet@munnari.oz.au Mon Jun 14 19:28:57 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA25975; Mon, 14 Jun 1993 19:29:12 +1000 (from owner-Big-Internet) Return-Path: Received: from mitsou.inria.fr by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA25968; Mon, 14 Jun 1993 19:28:57 +1000 (from huitema@mitsou.inria.fr) Received: by mitsou.inria.fr (5.65c/IDA-1.2.8) id AA12659; Mon, 14 Jun 1993 11:25:45 +0200 Message-Id: <199306140925.AA12659@mitsou.inria.fr> To: jnc@ginger.lcs.mit.edu (Noel Chiappa) Cc: big-internet@munnari.oz.au, whyman@mwassocs.demon.co.uk Subject: Re: Comments on Internet Draft on SIP 64-bit Addressing In-Reply-To: Your message of "Sat, 12 Jun 93 19:00:02 EDT." <9306122300.AA04963@ginger.lcs.mit.edu> Date: Mon, 14 Jun 93 11:25:43 +0200 From: Christian Huitema > I concur. Addresses need to be based, first and foremost, on the actual > network topology. Without real links over which traffic can flow, it's utterly > useless to the routing to hand out addresses which indicate a close > relationship. Noel, you should now better. Addresses cannot be at the same time hierarchical, to allow aggregation, and based on the network topology, which is anything but hierarchical. Christian Huitema From owner-Big-Internet@munnari.oz.au Tue Jun 15 01:22:29 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA09368; Tue, 15 Jun 1993 01:22:40 +1000 (from owner-Big-Internet) Return-Path: Received: from thumper.bellcore.com by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA09364; Tue, 15 Jun 1993 01:22:29 +1000 (from francis@thumper.bellcore.com) Received: from tsuchiya.bellcore.com by thumper.bellcore.com (4.1/4.7) id for big-internet@munnari.oz.au; Mon, 14 Jun 93 11:18:38 EDT Received: by tsuchiya.bellcore.com (4.1/4.7) id for whyman@mwassocs.demon.co.uk; Mon, 14 Jun 93 11:18:36 EDT Date: Mon, 14 Jun 93 11:18:36 EDT From: francis@thumper.bellcore.com (Paul Francis--formerly Tsuchiya) Message-Id: <9306141518.AA11818@tsuchiya.bellcore.com> To: Christian.Huitema@sophia.inria.fr, jnc@ginger.lcs.mit.edu Subject: Re: Comments on Internet Draft on SIP 64-bit Addressing Cc: big-internet@munnari.oz.au, whyman@mwassocs.demon.co.uk > > Noel, you should now better. Addresses cannot be at the same time hierarchical, > to allow aggregation, and based on the network topology, which is anything but > hierarchical. > I partially disagree. The internet topology is obviously a mesh, but it has strong hierarchical (ie, star) components--provider/subscriber being one and host/LAN being the other. We already make effective use of the host/LAN hierarchy. The provider/subscriber one is less clean, since subscribers are often attached to multiple providers (more commonly than hosts are attached to multiple LANs), but I believe that the multiple hierarchical addresses approach deals with this fairly well..... PX From owner-Big-Internet@munnari.oz.au Tue Jun 15 03:20:20 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA13844; Tue, 15 Jun 1993 03:20:28 +1000 (from owner-Big-Internet) Return-Path: Received: from GINGER.LCS.MIT.EDU by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA13841; Tue, 15 Jun 1993 03:20:20 +1000 (from jnc@ginger.lcs.mit.edu) Received: by ginger.lcs.mit.edu id AA12511; Mon, 14 Jun 93 13:20:07 -0400 Date: Mon, 14 Jun 93 13:20:07 -0400 From: jnc@ginger.lcs.mit.edu (Noel Chiappa) Message-Id: <9306141720.AA12511@ginger.lcs.mit.edu> To: Christian.Huitema@sophia.inria.fr, jnc@ginger.lcs.mit.edu Subject: Re: Comments on Internet Draft on SIP 64-bit Addressing Cc: big-internet@munnari.oz.au Addresses cannot be at the same time hierarchical, to allow aggregation, and based on the network topology, which is anything but hierarchical. Christian, you should know better. :-) Here's a proof: You can take an totally regular graph, and divide it into arbitrary non-overlapping, ubiquitous areas, by which I mean that i) each node in the graph is in at least and at most one area, and ii) you can get from any node in an area to any other node in that area without traversing a node which is not in that area. This gives you a second graph, with the nodes in the new graph being the areas, and the arcs in the new graph being those arcs which are inter-area links in the first graph (i.e. all arcs which connect pairs of nodes which are in different areas). You can then repeat the above process, so that each area is in at least and at most one meta-area, etc, etc. Now, give each meta-area is given a unique identifier, and each area within each meta-area is given an identifier which is unique within that meta-area, and each node within each area is given an identifier which is unique within that area. The address of each node consists of the identifier triple of its meta-area, area, and itself. (If that was a bit too abstract for some readers, just realize that each node has a hierarchical address of the form M.A.N, where M is its meta-area, etc, etc. Also, I assume you all realize that by "address" I mean "the name of the place the host attaches to the network". I'm assuming this is the definition you are using too.) Now, you have produced a hierarchical addressing scheme (which can be trivially used for routing) on an *absolutely* homogeneous and regular connection graph. Exactly the same process can be used on *any* graph, regular or not, thereby producing a hierarchial address which is based strictly on the graph topology. Since any physical network can be modeled as a graph, I believe this shows that, in fact, addresses *can* be both hierarchical (to allow aggregation), and based on the network topology, all at the same time. Now, there's a big explanation (which I'm not going to get into now :-) about the relationship between *how optimal* the routing will be in a such an addressing scheme, and how much *routing overhead* you have, but that's a whole different topic. I went into that in some detail on this mailing list a while back; see the following messages: Date: Sun, 1 Nov 92 13:38:21 -0500 Message-Id: <9211011838.AA25731@ginger.lcs.mit.edu> and Date: Mon, 2 Nov 92 22:58:47 -0500 Message-Id: <9211030358.AA01990@ginger.lcs.mit.edu> for more a more detailed exposition. Noel From owner-Big-Internet@munnari.oz.au Tue Jun 15 04:57:26 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA17611; Tue, 15 Jun 1993 04:57:46 +1000 (from owner-Big-Internet) Return-Path: Message-Id: <9306141857.17611@munnari.oz.au> Received: from alcor.process.com by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA17602; Tue, 15 Jun 1993 04:57:26 +1000 (from ULLMANN@PROCESS.COM) Date: Mon, 14 Jun 1993 14:52 -0400 From: ULLMANN@PROCESS.COM (Robert L Ullmann) To: jnc@ginger.lcs.mit.edu Cc: big-internet@munnari.oz.au Subject: Re: Comments on Internet Draft on SIP 64-bit Addressing Addresses cannot be at the same time hierarchical, to allow aggregation, and based on the network topology, which is anything but hierarchical. Christian, you should know better. :-) Here's a proof: You can take an totally regular graph, and divide it into arbitrary non-overlapping, ubiquitous areas, by which I mean that i) each node in the graph is in at least and at most one area, and ii) you can get from any node in an area to any other node in that area without traversing a node which is not in that area. [correct proof follows, except] Unstated assumption: that the graph is static. That, in fact, it sits still long enough to do this. Adding or removing single edges from the graph can have profound non-local effects. (Adding edges will not invalidate the abstracted hierarchy, but can render it very non-optimal.) The real network will have permanent topology changes (i.e. actual lines being added or removed, not link-state changes) occuring at the rate of many thousands/second. Most will have only local effect, but many will not. Best Regards, Robert From owner-Big-Internet@munnari.oz.au Tue Jun 15 06:23:27 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA20713; Tue, 15 Jun 1993 06:24:20 +1000 (from owner-Big-Internet) Return-Path: Received: from GINGER.LCS.MIT.EDU by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA20602; Tue, 15 Jun 1993 06:23:27 +1000 (from jnc@ginger.lcs.mit.edu) Received: by ginger.lcs.mit.edu id AA14154; Mon, 14 Jun 93 16:23:17 -0400 Date: Mon, 14 Jun 93 16:23:17 -0400 From: jnc@ginger.lcs.mit.edu (Noel Chiappa) Message-Id: <9306142023.AA14154@ginger.lcs.mit.edu> To: ULLMANN@process.com, jnc@ginger.lcs.mit.edu Subject: Re: Comments on Internet Draft on SIP 64-bit Addressing Cc: big-internet@munnari.oz.au, jnc@ginger.lcs.mit.edu Unstated assumption: that the graph is static. That, in fact, it sits still long enough to do this. Now you're getting into things like dynamic response to topology changes, which, while interesting, are more a function of the routing than the addressing, although (as explored below) there is a connection. Adding or removing single edges from the graph can have profound non-local effects. (Adding edges will not invalidate the abstracted hierarchy, but can render it very non-optimal.) As far as adding edges goes, yes, it can make the abstraction heirarchy chosen non-optimal, but the proof cited *arbitrary* area boundaries. I.e. I was explicitly not concerned with the optimality/cost of routing based on those boundaries (as the footnote pointed out). Any graph with extra edges will still meet the criteria, and thus the proof is good in all such cases as well. As far as deleting edges, this can have one of two results. Case A is that you don't cause the failure of condition ii) (i.e. "you can get from any node in an area to any other node in that area without traversing a node which is not in that area"). In this case, it's purely a routing thing, since the new graph still meets the conditions cited. Case B is a little more tricky; it's the "partitioned area" problem. I.e., area X is now in two pieces, such that X.1 and X.2 can now no longer communicate without leaving area X. Fixing this does not *necessarily* require redoing addresses, although that is one option. For example, IS-IS does area repair without modifying addresses. The exact mechanism you pick for handling this problem (and any real-world heirarchical routing architecture must handle it) depends on what you want for a cost/benefit tradeoff. The real network will have permanent topology changes (i.e. actual lines being added or removed, not link-state changes) occuring at the rate of many thousands/second. Most will have only local effect, but many will not. Exactly. If you will study the two messages I cited, you will discover that in them I discuss how this is the basis of *another* cost/benefit tradeoff (actually, balancing two sets of costs) which I discuss, viz., the balance between the costs of using a non-optimal address heirarchy, and the costs of redoing the addresses. Noel From owner-Big-Internet@munnari.oz.au Tue Jun 15 06:42:54 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA21353; Tue, 15 Jun 1993 06:43:18 +1000 (from owner-Big-Internet) Return-Path: Received: from vela.acs.oakland.edu by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA21345; Tue, 15 Jun 1993 06:42:54 +1000 (from bill.simpson@um.cc.umich.edu) Received: from via.ws07.merit.edu by vela.acs.oakland.edu with SMTP id AA24913 (5.65c+/IDA-1.4.4); Mon, 14 Jun 1993 16:42:27 -0400 Date: Mon, 14 Jun 93 11:27:14 EDT From: "William Allen Simpson" Message-Id: <1251.bill.simpson@um.cc.umich.edu> To: francis@thumper.bellcore.com (Paul Francis--formerly Tsuchiya) Cc: big-internet@munnari.oz.au Reply-To: bsimpson@morningstar.com Subject: Re: What goes around comes around > or: There is nothing new under the Sun(shine) > or: How to quote history to further your aims > or: A blast from the past > or: If we do not learn from history, we are bound to > repeat its mistakes > > As some of you may know, Pip is the topic of my PhD thesis. > Naturally in the course of writing a thesis, one must cite > relavent work, so I went digging.... > No, I didn't know. Very interesting stuff. Of course, Noel has been telling us that he has been talking about his plan for a decade. There might be another conclusion to be drawn: 1) the early internet architects already considered infinitely variable length addresses in the header (leader). 2) they thought about how to implement it. 3) they rejected it. Might we not gain from the same insights? Bill.Simpson@um.cc.umich.edu From owner-Big-Internet@munnari.oz.au Tue Jun 15 06:57:36 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA21890; Tue, 15 Jun 1993 06:57:52 +1000 (from owner-Big-Internet) Return-Path: Message-Id: <9306142057.21890@munnari.oz.au> Received: from alcor.process.com by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA21886; Tue, 15 Jun 1993 06:57:36 +1000 (from ULLMANN@PROCESS.COM) Date: Mon, 14 Jun 1993 16:53 -0400 From: ULLMANN@PROCESS.COM (Robert L Ullmann) To: jnc@ginger.lcs.mit.edu Cc: big-internet@munnari.oz.au Subject: Re: Comments on Internet Draft on SIP 64-bit Addressing Case B is a little more tricky; it's the "partitioned area" problem. I.e., area X is now in two pieces, such that X.1 and X.2 can now no longer communicate without leaving area X. Fixing this does not *necessarily* require redoing addresses, although that is one option. For example, IS-IS does area repair without modifying addresses. The exact mechanism you pick for handling this problem (and any real-world heirarchical routing architecture must handle it) depends on what you want for a cost/benefit tradeoff. Ah yes. Having invented the problem, we now invent a complex method of solving it by patching things up again; then delude ourselves into thinking we are making forward progress. 'Twould be better to have never invented areas at all, methinks ... :-) :-) Best Regards, Robert From owner-big-internet@munnari.oz.au Tue Jun 15 09:01:14 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA25860; Tue, 15 Jun 1993 09:01:22 +1000 (from owner-big-internet) Return-Path: Received: from vela.acs.oakland.edu by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA21387; Tue, 15 Jun 1993 06:43:28 +1000 (from bill.simpson@um.cc.umich.edu) Received: from via.ws07.merit.edu by vela.acs.oakland.edu with SMTP id AA24937 (5.65c+/IDA-1.4.4); Mon, 14 Jun 1993 16:42:50 -0400 Date: Mon, 14 Jun 93 11:38:35 EDT From: "William Allen Simpson" Message-Id: <1252.bill.simpson@um.cc.umich.edu> To: whyman@mwassocs.demon.co.uk Cc: big-internet@munnari.oz.au Reply-To: bsimpson@morningstar.com Subject: Re: Comments on Internet Draft on SIP 64-bit Addressing > Thank you for your clearly restrained response to my comments on SIP > addressing. As requested, I have transferred the discussion to the big internet > list. > One does not have to be as restrained in private email, as one might in a public list. It was not appreciated that you posted a private reply to a public list. Until you learn more about common courtesy, I guess the others on the SIP list were correct in just ignoring you entirely. My mistake. > > As to your comments, the SIP list is for implementors. Discussion of > > perceived differences between the proposals is best kept to the > > big-internet list. SIP already has 3 interoperable implementations, > > and is working on enhancements, not basic design. > > Unfortunately, I mis-read the text at the start of your internet draft > "Administrative Allocation of the 64-bit Number Space". It said that > "Comments on this memo should be submitted to the sip@caldera.usc.edu." > It was obviously stupid of me not to realise that this should have been > read as big-internet. It also escaped my attention that SIP is already > perfect. > Yes, comments on how to improve the plan should be sent to the SIP list. Saying, "I don't think 64-bits are enough", is not a constructive comment about the allocation plan, but a comment about "differences between the proposals". That is not appropriate for the SIP list. SIP is a WORKING group, not a debate society. Yes, SIP is already perfect. ;-) > > It clearly says allocation in the title -- why then are you surprised? > > > ... > its relationship with topology will have a major impact on the potential > for route aggregation and the overall efficiency of routing. I did not > think it wrong to ask that the SIP addressing plan justify itself > against a model topology and an assumed routing strategy. If you think > that routing based on address prefixes is just like good old IP then you > may be in for some surprises. > You are confusing addressing with allocation. The title is clear. For routing, you should review the SIP Routing specification. Finally, it is apparent that you did not read the text. Looking at a few tables and flaming is not a welcome technique for getting work done. Bill.Simpson@um.cc.umich.edu From owner-big-internet@munnari.oz.au Tue Jun 15 12:31:56 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA04453; Tue, 15 Jun 1993 12:32:05 +1000 (from owner-big-internet) Return-Path: Received: from GINGER.LCS.MIT.EDU by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA00972; Tue, 15 Jun 1993 11:10:26 +1000 (from jnc@ginger.lcs.mit.edu) Received: by ginger.lcs.mit.edu id AA15088; Mon, 14 Jun 93 21:10:04 -0400 Date: Mon, 14 Jun 93 21:10:04 -0400 From: jnc@ginger.lcs.mit.edu (Noel Chiappa) Message-Id: <9306150110.AA15088@ginger.lcs.mit.edu> To: ULLMANN@process.com, jnc@ginger.lcs.mit.edu Subject: Re: Comments on Internet Draft on SIP 64-bit Addressing Cc: big-internet@munnari.oz.au, jnc@ginger.lcs.mit.edu Ah yes. Having invented the problem, we now invent a complex method of solving it by patching things up again.... Hey, I just pulled one particular method of handling partition problems, *other than reassigning addresses*, off the top of my head, for illustration. I didn't say I *liked* it! There are many ways to do this (some of which you will probably like better), for instance what CIDR does; it advertises all the sub-objects of an object as individual entities when they are no longer topologically grouped. In other words, X.1 and X.2 get advertised at the same routing level as Y and Z, once X is no longer contiguous. There are still others. 'Twould be better to have never invented areas at all, methinks ... Hmm. Assuming you didn't mean this 100% tongue in cheek, I don't know any way of causing the routing to scale, other than using a heirarchy. Even though it *inevitably* causes problems, I think we are stuck with it. If you come up with something better, speak up, and stand by to collect your Turing Award lecture! Noel From owner-big-internet@munnari.oz.au Tue Jun 15 15:50:37 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA12714; Tue, 15 Jun 1993 15:50:46 +1000 (from owner-big-internet) Return-Path: Received: from moink.NMSU.Edu by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA09120; Tue, 15 Jun 1993 14:22:34 +1000 (from amolitor@moink.nmsu.edu) Received: by moink.nmsu.edu (5.61/eels); id AA20272; Mon, 14 Jun 93 22:22:26 -0600 Date: Mon, 14 Jun 93 22:22:26 -0600 From: amolitor@moink.nmsu.edu (Andrew Molitor) Message-Id: <9306150422.AA20272@moink.nmsu.edu> To: big-internet@munnari.oz.au Subject: theoretical nonesense - It's sort of painful to watch people make theoretical arguments, and dismiss problems as implementation details, apparently just so they can say glib things like 'addresses are routes' or 'bees are airplanes' Networking is all in the implementation details. A bit of theory here and there to show that the implementation will work is good (say, to show that routes will converge or something), but even there one tends to start with a heuristic. So let's try to keep the 'partitioning complete regular graphs' and so on to a minimum. Andrew From owner-big-internet@munnari.oz.au Tue Jun 15 18:54:39 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA20543; Tue, 15 Jun 1993 18:54:42 +1000 (from owner-big-internet) Return-Path: Received: from lager.cisco.com by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA15242; Tue, 15 Jun 1993 16:50:43 +1000 (from tli@cisco.com) Received: by lager.cisco.com id AA14612 (5.67a/IDA-1.5 for big-internet@munnari.oz.au); Mon, 14 Jun 1993 23:50:19 -0700 Date: Mon, 14 Jun 1993 23:50:19 -0700 From: Tony Li Message-Id: <199306150650.AA14612@lager.cisco.com> To: amolitor@moink.nmsu.edu Cc: big-internet@munnari.oz.au Subject: theoretical nonesense - Networking is all in the implementation details. A bit of theory here and there to show that the implementation will work is good (say, to show that routes will converge or something), but even there one tends to start with a heuristic. So let's try to keep the 'partitioning complete regular graphs' and so on to a minimum. Ahem. As one of the implementors involved who has written quite a bit of production code which now supports the Internet: HOGWASH Yes, networking is all in the implementation details. And there's too damn many details as it is. Theory is the abstraction mechanism for ignoring the details and concentrating on the problem. Detail is the chore of making sure that you dot the I's and cross the T's. Implementation is the art of doing both simultaneously. Now, Noel, as you were saying.... Tony From owner-Big-Internet@munnari.oz.au Tue Jun 15 22:55:28 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA29004; Tue, 15 Jun 1993 22:55:43 +1000 (from owner-Big-Internet) Return-Path: Received: from babyoil.ftp.com by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA28980; Tue, 15 Jun 1993 22:55:28 +1000 (from kasten@ftp.com) Received: by ftp.com id AA14763; Tue, 15 Jun 93 08:55:23 -0400 Date: Tue, 15 Jun 93 08:55:23 -0400 Message-Id: <9306151255.AA14763@ftp.com> To: ULLMANN@PROCESS.COM Subject: Re: Comments on Internet Draft on SIP 64-bit Addressing From: kasten@ftp.com (Frank Kastenholz) Reply-To: kasten@ftp.com Cc: jnc@ginger.lcs.mit.edu, big-internet@munnari.oz.au > Unstated assumption: that the graph is static. That, in fact, it > sits still long enough to do this. > > Adding or removing single edges from the graph can have profound > non-local effects. (Adding edges will not invalidate the abstracted > hierarchy, but can render it very non-optimal.) > > The real network will have permanent topology changes (i.e. actual > lines being added or removed, not link-state changes) occuring at > the rate of many thousands/second. Most will have only local effect, > but many will not. I would be willing to bet that any line changes, as you describe, would mostly occur within areas in the lowest one or to levels of hierarchy. This is based on the assumption that the lowest level "area" will be very similar to an administrative domain; something like Nearnet or the NSFNET Backbone, or FTP's corporate net, or perhaps a proper subset of what we today call the subnets within that domain. For example, links to the outside world from FTP have changed maybe 3 or 4 times over the past several years (one of which was due to a physical move of the company). Internally, however, our topography changes quite a lot, new nets are added, old ones removed, new routers added, links between existing routers and nets get added or removed. -- Frank Kastenholz FTP Software 2 High Street North Andover, Mass. USA 01845 (508)685-4000 From owner-big-internet@munnari.oz.au Wed Jun 16 01:40:15 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA05580; Wed, 16 Jun 1993 01:40:22 +1000 (from owner-big-internet) Return-Path: Received: from GINGER.LCS.MIT.EDU by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA03660; Wed, 16 Jun 1993 00:48:29 +1000 (from jnc@ginger.lcs.mit.edu) Received: by ginger.lcs.mit.edu id AA17573; Tue, 15 Jun 93 10:48:09 -0400 Date: Tue, 15 Jun 93 10:48:09 -0400 From: jnc@ginger.lcs.mit.edu (Noel Chiappa) Message-Id: <9306151448.AA17573@ginger.lcs.mit.edu> To: amolitor@moink.nmsu.edu, big-internet@munnari.oz.au Subject: Re: theoretical nonesense - Cc: jnc@ginger.lcs.mit.edu It's sort of painful to watch people make theoretical arguments, and dismiss problems as implementation details Believe it or not, I do have a certain amount of sympathy with people who decry approaches based solely on theory; while I was on the research staff at MIT, I conducted a running guerrilla campaign against what I saw as a too theoretical approach to life. However, I do get tired of being accused of being 'theoretical'. I have a real appreciation for the difficulties caused by 'implementation details'. This stems in part from my time at MIT, when, among other duties, I invented the concept of the multi-protocol router, and in the process of demonstrating that it was a valid idea, produced a fairly good completely portable one (still being sold, albeit much improved, as a product, by Proteon), which involved me personally writing 16K lines of C code. I kept the main path reasonably fast by counting all the memory references along it... I'm still writing code, it just happens that these days it's a C compiler with some novel features, not networking stuff. Networking is all in the implementation details. A bit of theory here and there to show that the implementation will work is good ... but even there one tends to start with a heuristic. It's equally misguided to get so far down in the bits. There are at least two ways to fail. The first is that you lose sight of the big picture, and you keep going in the same direction, making marginal improvements, even though a larger view would have pointed out it was time to change course; anyone want to build a better horse-buggy? The second is that lacking a good ground in whatever theory is available, you can head for an impossible goal; anyone want to try finding a geometric procedure for squaring the circle? So let's try to keep the 'partitioning complete regular graphs' and so on to a minimum. As I recall, this proof happened because someone made what I considered an untrue statement. I've been catching a lot of flack for 'hand-wavy' arguments on this list, so I thought I'd provide one that was a little harder to make this complaint about. Now, can we get back to discussing networking? Noel From owner-Big-Internet@munnari.oz.au Wed Jun 16 03:14:05 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA08871; Wed, 16 Jun 1993 03:14:19 +1000 (from owner-Big-Internet) Return-Path: Received: from vtvm1.cc.vt.edu by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA08842; Wed, 16 Jun 1993 03:14:05 +1000 (from VALDIS@vtvm1.cc.vt.edu) Received: from vtvm1.cc.vt.edu by VTVM1.CC.VT.EDU (IBM VM SMTP V2R2) with BSMTP id 2302; Tue, 15 Jun 93 13:13:46 EDT Received: from vtvm1.cc.vt.edu (VALDIS) by vtvm1.cc.vt.edu (Mailer R2.10 ptf000) with BSMTP id 2150; Tue, 15 Jun 93 13:13:45 EDT Date: Tue, 15 Jun 93 13:06:43 EDT From: Valdis Kletnieks Organization: Virginia Polytechnic Institute Subject: Re: Comments on Internet Draft on SIP 64-bit Addressing To: Frank Kastenholz , ULLMANN@PROCESS.COM Cc: jnc@ginger.lcs.mit.edu, big-internet@munnari.oz.au In-Reply-To: <9306151255.AA14763@ftp.com> Message-Id: <930615.130643.EDT.VALDIS@vtvm1.cc.vt.edu> On Tue, 15 Jun 93 08:55:23 -0400 you said: >I would be willing to bet that any line changes, as you describe, >would mostly occur within areas in the lowest one or to levels of Not a valid assumption. At our site, we have an internal topology change on the order of once every 2 months (next one is August when we kick our backbone onto a FDDI ring and add another backbone router). On the other hand, we have "something" happen to our T-1 on the order of once every week (it burped for about 5 minutes around 3AM today). As a matter of fact, we had to specifically disable Vernet/Suranet from advertising us to the core because every time we'd lose our primary link, we'd have a nice long routing flap with all sorts of evil as things tried to decide if packets were supposed to be traversing the T-1 to the Greensboro ENSS or if they were supposed to be going "backdoor" through vernet/suranet and emerging at UMD. Remember - when you're dealing with routing - *any* change that persists long enough to be noticed by something is a topology change... Valdis Kletnieks Computer Systems Engineer Virginia Polytechnic Institute From owner-big-internet@munnari.oz.au Wed Jun 16 09:40:26 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA22832; Wed, 16 Jun 1993 09:40:40 +1000 (from owner-big-internet) Return-Path: Message-Id: <9306152340.22832@munnari.oz.au> Received: from hadar.process.com by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA15784; Wed, 16 Jun 1993 06:29:18 +1000 (from ULLMANN@PROCESS.COM) Date: Tue, 15 Jun 1993 16:25 -0400 From: ULLMANN@PROCESS.COM (Robert L Ullmann) To: jnc@ginger.lcs.mit.edu Cc: big-internet@munnari.oz.au Subject: Re: graphs Hi, Hmm. Assuming you didn't mean this 100% tongue in cheek, I don't know any way of causing the routing to scale, other than using a heirarchy. Even though it *inevitably* causes problems, I think we are stuck with it. If you come up with something better, speak up, and stand by to collect your Turing Award lecture! (It was areas I was questioning, not hierarchy; the two are separable.) In a general graph, this is a difficult problem. If one is allowed to constrain the graph to special classes, it isn't too hard. In a graph with non-local fractal topology, one could "address" an element by the vector of parameters that generate that element; one can then follow edges from any other element to that one in a rigourous procedure, but the graph is not locally connected in areas. Tough to fit the real world into that one, though ... :-) Other classes of inverted parametric graphs with regular structure are fairly easy too, but fit the real world about as well. --- I was thinking more about the definition of "area": there is a tendency to define them too strictly, where the routing protocols must then explicitly discover partitioning, and then take explicit action to recover the connectivity. I think it would be better to use a loose definition of areas, where the hierarchical numbering allows the routing protocol to aggregate routes some distance from the (somewhat fuzzy) boundary of the area, not immediately at the border. Areas that are partitioned (in the stricter model) then simply fail to coelesce in the routing; the routing isn't doing anything differently. Sub-areas that then wander more-or-less permanently away from the containing area are then visible to the routing further away, but not an infinite distance away. This is how RAP is designed to work, doing somewhat delayed aggregation, and not requiring strict area borders or level definitions; it then doesn't need explicit logic to repair partitions. --- Now, to work on the general case of non-locality ... (Someone like Feynman observed that it is real tough to think about non-locality; we don't even have a word for it except in opposition to locality!) Best Regards, Robert From owner-big-internet@munnari.oz.au Wed Jun 16 11:47:37 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA27972; Wed, 16 Jun 1993 11:47:56 +1000 (from owner-big-internet) Return-Path: Received: from vtvm1.cc.vt.edu by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA08435; Wed, 16 Jun 1993 03:01:07 +1000 (from VALDIS@vtvm1.cc.vt.edu) Received: from vtvm1.cc.vt.edu by VTVM1.CC.VT.EDU (IBM VM SMTP V2R2) with BSMTP id 2224; Tue, 15 Jun 93 13:00:45 EDT Received: from vtvm1.cc.vt.edu (VALDIS) by vtvm1.cc.vt.edu (Mailer R2.10 ptf000) with BSMTP id 1747; Tue, 15 Jun 93 13:00:44 EDT Date: Tue, 15 Jun 93 12:36:48 EDT From: Valdis Kletnieks Organization: Virginia Polytechnic Institute Subject: Re: What goes around comes around To: William Allen Simpson , Paul Francis--formerly Tsuchiya , bsimpson@morningstar.com Cc: big-internet@munnari.oz.au In-Reply-To: <1251.bill.simpson@um.cc.umich.edu> Message-Id: <930615.123648.EDT.VALDIS@vtvm1.cc.vt.edu> On Mon, 14 Jun 93 11:27:14 EDT you said: > 1) the early internet architects already considered infinitely variable > length addresses in the header (leader). > > 2) they thought about how to implement it. > > 3) they rejected it. > >Might we not gain from the same insights? My understanding is that a lot of the fine technical points were chosen on the basis of different conditions than exist today. One of these conditions was that memory could cost as much as $20,000 a magabyte or so. For many years, engineers would do all sorts of contortions to avoid doing a Fourier transform - and then the FFT was derived. Changed the whole playing surface. Yes, there's insight to be gained - and that insight is "what *would* they have added *then*, if they had today's hardware resources"? I've seen a specific reference to "we would have done 112(?) bit addresses but decided it was too much memory usage". These days, 112 bits is a drop in the bucket memory wise - but maybe 112 bits is *still* a bad idea - maybe having addresses this huge causes some other problem and we want to use 32 bit flow IDs instead. I think we have to remember that we're operating on the lunatic fringe of crystal ball scrying. We're trying to design something that is deployable now, but will still look non-foolish in 15 years. 15 years ago, a Vax/780 was the hottest thing since sliced bread.... It would be interesting if the appropriate people were to fill in some of the gaps in the following matrix: "IP Classic" SIP TUBA IP/NG etc.. design point Host CPU (mips) ? ? ? ? design point router CPU (mips) ? ? ? ? design point host memory (K) ? ? ? ? design point router memory (K) ? ? ? ? design point network bandwidth ? ? ? ? It would also be helpful in knowing what values the designers thought things need to work until.. "Well, we need this to last at least X years, at which point it'll have to support X mips and Y bandwidth..." Knowing this data, we can then look to see if we might have a problem lurking in the background (similar to the bandwidth*RTT problems in IP). Valdis Kletnieks Computer Systems Engineer Virginia Polytechnic Institute From owner-big-internet@munnari.oz.au Wed Jun 16 17:52:28 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA12694; Wed, 16 Jun 1993 17:52:43 +1000 (from owner-big-internet) Return-Path: Received: from PANDANUS.NTU.EDU.AU by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA02040; Wed, 16 Jun 1993 13:33:46 +1000 (from coleman@PANDANUS.NTU.EDU.AU) Received: from [138.80.130.104] (COLEMAN.NTU.EDU.AU) by pandanus.cs.ntu.edu.au with SMTP id AA02265 (5.65c/IDA-1.4.4 for ); Wed, 16 Jun 1993 13:03:25 +0930 Message-Id: <199306160333.AA02265@pandanus.cs.ntu.edu.au> Date: Wed, 16 Jun 1993 13:02:27 +0930 To: big-internet@munnari.oz.au From: coleman@pandanus.ntu.edu.au (James P H Coleman) Subject: Routing idea - Y-Routing Cc: tanstey@pandanus.ntu.edu.au After watching the discussion on the big-internet and the following idea emerged: Y-Routers ======= A Y-Router (Y-R) is a 3 port router such that a packet coming in has two options on the direction to proceed, either to the left or to the right. this can be represented as a 1 or 0. Any other router can be considered to be a combination of Y-Rs. A 4 port router can be seen as the following: c | d b--+ / \ / + | a In this router there are a max of 2 decision necessary to route a packet through this router. a -> b is 11 or left turn followed by a left turn a -> d is 0 a -> c is 10 A nice feature of this is that the reverse track can be easily calculated. It is simply the bits reversed and inverted. For example: b -> a is 00 d -> a is 1 c -> a is 10 If we extend this so that the whole of the internet is considered to be a router with millions of ports, then with 64 decisions, a very large >> 10 E+12 nodes can be connected. This means that a route can be seen as a sequence of 1 bit instructions for the Y-Rs. Therefore, if a route can be determined for a packet, then the actual ----------------------------------------- transmission of the packet can be sped up enormously because all the router has to do is look at the top bit and based on that, determine which path to take. No lookup tables etc required at all. So the problem comes down to, how do we determine the route itself, and therefore build up the routing bit string. The Internet and Y-Routing/Addressing etc ========================================= Consider the Internet to be a binary tree from some specified point ( let us not worry about details for the moment here) with a Y-R at each point where there is a split. x1 x2 x3 x4 x5 x6 x7 x8 | | | | | | | | -+- -+- -+- -+- | | | | -1-+--0- -1-+--0- | | -----1---+---0------ | a Then every node xi is related to the central point a, and the path from a to that node can be specified. a -> x1 is 111 a -> x2 is 110 etc Each xi now has a unique identifier, that is the path from the node a. This is similar to the file system of Unix where each file is identified by the path to the root directory. Using this process, determining a route from a node to another is a trivial process and goes as follows: Route from x1 to x8 path x1 = 111 path x8 = 000 Let us put an imaginary 0 to the left of both these paths and starting from the left, bit-compare the two bit strings to find the position where the two bit strings differ. It is at this point that the two paths vary. eg /home/staff/coleman/bin & /home/staff/anstey/bin They differ at the 3rd level. In the case of x1 -> x8, the strings look as follows: x1(from) 0-111 x8(to) 0-000 * At the star (*) the two strings differ. The route from x1 to x8 is as follows: 1) starting from the right hand side of the from path (x1), invert the bits up to, but not including the stared one. 00 2) copy the stared bit from x1 1 3) skip the stared bit from x8 path 4) copy the rest left to right 00 The path from x1 to x8 is then: 00100 (ie right, right, left, right, right) What this means is that it is now extremely simple to calculate a route from one node to another given that you know the paths to the nodes. The path for a node is the path to the next connected Y-R plus the path from that router to the node. This information can be (relatively easily) maintained by a DNS. Problems ======== There are of course problems with this approach to do with the network being a binary treee etc. These problems should have solutions, if the solutions are relatively straight forward, as I suspect they are, which will mean a very slick routing (and addressing) scheme. Summary ======= There are some unresolved problems with this approach, not the least is the fact that the Internet needs to be considered a binary tree and how to maintain that tree with line outages etc. These problems are considerably out-weighed I by the following: 1) absolute simplicity of routing 2) absolute simplicity of determining routes 3) almost unlimited scalabitity of the whole;e approach These problems are being considered now. Work by: James P H Coleman and Tery Anstey From owner-big-internet@munnari.oz.au Wed Jun 16 18:32:00 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA14146; Wed, 16 Jun 1993 18:32:10 +1000 (from owner-big-internet) Return-Path: Received: from GINGER.LCS.MIT.EDU by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA05321; Wed, 16 Jun 1993 14:45:19 +1000 (from jnc@ginger.lcs.mit.edu) Received: by ginger.lcs.mit.edu id AA23140; Wed, 16 Jun 93 00:45:00 -0400 Date: Wed, 16 Jun 93 00:45:00 -0400 From: jnc@ginger.lcs.mit.edu (Noel Chiappa) Message-Id: <9306160445.AA23140@ginger.lcs.mit.edu> To: big-internet@munnari.oz.au, bsimpson@morningstar.com Subject: Re: What goes around comes around Cc: jnc@ginger.lcs.mit.edu No, I didn't know. Very interesting stuff. Of course, Noel has been telling us that he has been talking about his plan for a decade. Noel didn't quite get the point of this. He will charitably assume it wasn't meant unkindly, until it is explained. There might be another conclusion to be drawn: 1) the early internet architects already considered infinitely variable length addresses in the header (leader). 2) they thought about how to implement it. 3) they rejected it. Might we not gain from the same insights? The decision on dropping those happened slightly before I got active in the Internet Working Group, so I don't know all the reasons why they didn't go with variable length addresses (although I recall hearing a rumor at the time involving the number of registers available at interrupt time in TENEX to hold pointers... :-) What I *do* know is that nobody, but *nobody*, ever had any idea that IPv4 would *ever* be called upon to support a system of the size we see today. It was designed as a large scale testbed and trial service system; the initial address format consisted of an 8-bit network number, and a 24-bit rest! It has been kludged over the years (first via A/B/C, then subnets, and now CIDR) to handle a larger system, but we've about reached the end of the road. At this point, due to a lack of foresight in the design, we are now faced with a painful and expensive change. If you think there are any deep insights in the process of designing the IPv4 header which you can apply here, you're very confused. Fixed length addresses did not contribute in any substantial way to the sucess of TCP/IP, and it boggles my mind to think that anyone could think so, at least if they hasve spent any time analyzing why TCP/IP *was* successful. I'd suggest that the only lesson you can draw from IPv4 is the one I alluded to above; people put in a quick, simple design which seemed like it was efficient, and it came back to bite them very badly. Doesn't bode well for SIP. Saying, "I don't think 64-bits are enough", is not a constructive comment about the allocation plan, but a comment about "differences between the proposals". That is not appropriate for the SIP list. SIP is a WORKING group, not a debate society. ... You are confusing addressing with allocation. The title is clear. For routing, you should review the SIP Routing specification. It's true that reading the addressing plan document is probably not the best time to point out problems, but he was just trying to point out something which, if true, is something I'd think you'd want to know about. However, I'm not too surprised that you're not interested in hearing about it; it became clear pretty early on to some of us that the SIP designer(s) weren't interested in making substantial changes to the design in response to being told about places where they might have gone substantially off the rails. Exactly why, I am really puzzled by, since I'd think you all would want to know about things which would trip SIP up, so you could fix them, but I guess that brand of logic isn't for everyone. Seems odd to me, though, that people would put all this time and energy into something, and then condemn it to failure by making it second-rate. That's human nature for you, though, I guess; it happens all the time. Noel From owner-Big-Internet@munnari.oz.au Wed Jun 16 18:39:09 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA14423; Wed, 16 Jun 1993 18:39:25 +1000 (from owner-Big-Internet) Return-Path: Message-Id: <9306160839.14423@munnari.oz.au> Received: from bells.cs.ucl.ac.uk by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA14415; Wed, 16 Jun 1993 18:39:09 +1000 (from J.Crowcroft@cs.ucl.ac.uk) Received: from waffle.cs.ucl.ac.uk by bells.cs.ucl.ac.uk with local SMTP id ; Wed, 16 Jun 1993 09:38:48 +0100 To: big-internet@munnari.oz.au Subject: also ran, STop? Date: Wed, 16 Jun 93 09:38:45 +0100 From: Jon Crowcroft note that despite valiant efforts on PIP, SIP, TUBA, etc to create a full market choice for IPng there's probably more ST-II out there now:-) 2 router vendors and a major company (not microsoft) will be shipping.... anyone care to comment on the acceptability of this 'solution' jon From owner-big-internet@munnari.oz.au Wed Jun 16 19:50:53 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA16845; Wed, 16 Jun 1993 19:51:13 +1000 (from owner-big-internet) Return-Path: Received: from mitsou.inria.fr by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA12616; Wed, 16 Jun 1993 17:49:03 +1000 (from huitema@mitsou.inria.fr) Received: by mitsou.inria.fr (5.65c/IDA-1.2.8) id AA16498; Wed, 16 Jun 1993 09:49:37 +0200 Message-Id: <199306160749.AA16498@mitsou.inria.fr> To: jnc@ginger.lcs.mit.edu (Noel Chiappa) Cc: ULLMANN@process.com, big-internet@munnari.oz.au Subject: Re: Comments on Internet Draft on SIP 64-bit Addressing In-Reply-To: Your message of "Mon, 14 Jun 93 21:10:04 EDT." <9306150110.AA15088@ginger.lcs.mit.edu> Date: Wed, 16 Jun 93 09:49:37 +0200 From: Christian Huitema Noel, Hey, I just pulled one particular method of handling partition problems, *other than reassigning addresses*, off the top of my head, for illustration. The method you described is exactly that proposed by Kleinrock and Kamoun, who indeed go on quantifying the impact on routing quality. Ullmann is correct: the proof you gave assumes static graphs. Moreover, it assumes that you know the topology in advance, and can design the addressing plan ex nihilo. The assumption that the graph "only changes in local parts" is not well funded either. One frequent non local change is the "change provider". A consequence on a strict hierarchical plan (following K&K's algorithm) is indeed that one should do address renumbering. Then comes the case of a "multiple provider" attachment. Applying the algorithm you described leads to either placing those "multi-homed" areas near the top of the hierarchy (no aggregation), or alternatively to assign multiple addresses to every hosts in the multi-homed areas. Neither is very satisfactory; in fact, both are a departure from the curent IP architecture where there is no relation between your "network number" and the contracts you have with your providers. I am probably not the only one to have strong doubts about hierarchies and provider addresses -- the addressing BOF at Columbus was clearly unconclusive! The problem is indeed that if one does not believe in hierarchies one has to exhibit a routing architecture that allows to perform "flat routing" with a million networks internet. Which is an interesting theoretical exercise... Christian Huitema From owner-big-internet@munnari.oz.au Wed Jun 16 22:39:26 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA22458; Wed, 16 Jun 1993 22:39:55 +1000 (from owner-big-internet) Return-Path: Message-Id: <9306161239.22458@munnari.oz.au> Received: from nic.near.net by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA17737; Wed, 16 Jun 1993 20:21:33 +1000 (from jcurran@nic.near.net) Received: from nic.near.net by nic.near.net id aa09202; 16 Jun 93 6:21 EDT To: Noel Chiappa Cc: big-internet@munnari.oz.au Subject: Re: What goes around comes around In-Reply-To: Your message of Wed, 16 Jun 1993 00:45:00 -0400. <9306160445.AA23140@ginger.lcs.mit.edu> Date: Wed, 16 Jun 1993 06:21:05 -0400 From: John Curran -------- ] From: Noel Chiappa ] Subject: Re: What goes around comes around ] ... ] What I *do* know is that nobody, but *nobody*, ever had any idea that IPv4 ] would *ever* be called upon to support a system of the size we see today. It ] was designed as a large scale testbed and trial service system; the initial ] address format consisted of an 8-bit network number, and a 24-bit rest! It has ] been kludged over the years (first via A/B/C, then subnets, and now CIDR) to ] handle a larger system, but we've about reached the end of the road. As a side note, many folks would agree with the above, _except_ that CIDR isn't a kludge, but the removal of a kludge... /John From owner-Big-Internet@munnari.oz.au Thu Jun 17 01:10:17 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA28641; Thu, 17 Jun 1993 01:10:35 +1000 (from owner-Big-Internet) Return-Path: Received: from gibbs.oit.unc.edu by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA28638; Thu, 17 Jun 1993 01:10:17 +1000 (from ses@tipper.oit.unc.edu) Received: from tipper.oit.unc.edu by gibbs.oit.unc.edu (5.64/10.1) id AA03968; Wed, 16 Jun 93 11:09:53 -0400 Received: from localhost.oit.unc.edu by tipper (4.1/SMI-4.1) id AA13479; Wed, 16 Jun 93 11:11:51 EDT Message-Id: <9306161511.AA13479@tipper> X-Really-To: gibbs.oit.unc.edu To: Christian Huitema Cc: jnc@ginger.lcs.mit.edu (Noel Chiappa), ULLMANN@process.com, big-internet@munnari.oz.au Subject: Re: Comments on Internet Draft on SIP 64-bit Addressing In-Reply-To: Your message of "Wed, 16 Jun 93 09:49:37 +0200." <199306160749.AA16498@mitsou.inria.fr> Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Date: Wed, 16 Jun 93 11:11:51 -0400 From: Simon E Spero If I were to type the phrase "Static EIDs, Dynamic addresses", would it start another month long EID war? If so, I won't type it :-) From owner-Big-Internet@munnari.oz.au Thu Jun 17 02:56:44 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA02653; Thu, 17 Jun 1993 02:56:55 +1000 (from owner-Big-Internet) Return-Path: Received: from ftp.com by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA02647; Thu, 17 Jun 1993 02:56:44 +1000 (from kasten@ftp.com) Received: by ftp.com id AA02209; Wed, 16 Jun 93 12:56:51 -0400 Date: Wed, 16 Jun 93 12:56:51 -0400 Message-Id: <9306161656.AA02209@ftp.com> To: jnc@ginger.lcs.mit.edu, big-internet@munnari.oz.au Subject: Re: What goes around comes around From: kasten@ftp.com (Frank Kastenholz) Reply-To: kasten@ftp.com > If you think there are any deep insights in the process of designing the IPv4 > header which you can apply here, you're very confused. Fixed length addresses There is one deep, profound, insight. And that is that we can not say what the network will look like in 5 years, much less 10 or 15, so whatever the result of IPng is, it absolutely positively must be flexible, adaptable, and evolvable. -- Frank Kastenholz FTP Software 2 High Street North Andover, Mass. USA 01845 (508)685-4000 From owner-big-internet@munnari.oz.au Thu Jun 17 03:44:42 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA04293; Thu, 17 Jun 1993 03:44:52 +1000 (from owner-big-internet) Return-Path: Received: from thumper.bellcore.com by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA02099; Thu, 17 Jun 1993 02:41:09 +1000 (from francis@thumper.bellcore.com) Received: from tsuchiya.bellcore.com by thumper.bellcore.com (4.1/4.7) id for big-internet@munnari.oz.au; Wed, 16 Jun 93 12:40:46 EDT Received: by tsuchiya.bellcore.com (4.1/4.7) id for ses@tipper.oit.unc.edu; Wed, 16 Jun 93 12:40:44 EDT Date: Wed, 16 Jun 93 12:40:44 EDT From: francis@thumper.bellcore.com (Paul Francis--formerly Tsuchiya) Message-Id: <9306161640.AA00658@tsuchiya.bellcore.com> To: Christian.Huitema@sophia.inria.fr, ses@tipper.oit.unc.edu Subject: Re: Comments on Internet Draft on SIP 64-bit Addressing Cc: ULLMANN@process.com, big-internet@munnari.oz.au, jnc@ginger.lcs.mit.edu > > If I were to type the phrase "Static EIDs, Dynamic addresses", would it start > another month long EID war? If so, I won't type it :-) > If you were to type such a phrase, which I'm sure you wouldn't as it would probably lead to the war you mention, I would be inclined to agree wholeheartedly, and modify it slightly as follows..... "Static EIDs, Somewhat Dynamic addresses, Dynamic routes" PX From owner-big-internet@munnari.oz.au Thu Jun 17 05:39:50 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA08260; Thu, 17 Jun 1993 05:40:06 +1000 (from owner-big-internet) Return-Path: Received: from thumper.bellcore.com by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA00602; Thu, 17 Jun 1993 02:05:02 +1000 (from francis@thumper.bellcore.com) Received: from tsuchiya.bellcore.com by thumper.bellcore.com (4.1/4.7) id for big-internet@munnari.oz.au; Wed, 16 Jun 93 12:04:11 EDT Received: by tsuchiya.bellcore.com (4.1/4.7) id for tanstey@pandanus.ntu.edu.au; Wed, 16 Jun 93 12:04:09 EDT Date: Wed, 16 Jun 93 12:04:09 EDT From: francis@thumper.bellcore.com (Paul Francis--formerly Tsuchiya) Message-Id: <9306161604.AA00576@tsuchiya.bellcore.com> To: big-internet@munnari.oz.au, coleman@pandanus.ntu.edu.au Subject: Re: Routing idea - Y-Routing Cc: tanstey@pandanus.ntu.edu.au > > Therefore, if a route can be determined for a packet, then the actual > ----------------------------------------- > transmission of the packet can be sped up enormously because all the router > has to do is look at the top bit and based on that, determine which path to > take. No lookup tables etc required at all. > > So the problem comes down to, how do we determine the route itself, and > therefore build up the routing bit string. The notion of this kind of "source route" has surfaced from time to time, such as Sirpent and Paris. But, this idea of how to figure out the "source route" is really intriguing. > > > Problems > ======== > There are of course problems with this approach to do with the network > being a binary treee etc. These problems should have solutions, if the > solutions are relatively straight forward, as I suspect they are, which > will mean a very slick routing (and addressing) scheme. > Of course, one concern is the sensitivity of addresses to single failures (a link here or a node there). But, perhaps you could lessen the sensitivity by having 4-bit or 8-bit switches instead of binary switches..... I look forward to seeing more of this work..... PX From owner-big-internet@munnari.oz.au Thu Jun 17 05:59:55 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA09364; Thu, 17 Jun 1993 06:00:11 +1000 (from owner-big-internet) Return-Path: Received: from OPAL.ACC.COM by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA00509; Thu, 17 Jun 1993 02:00:02 +1000 (from art@opal.acc.com) Received: by opal.acc.com (4.1/SMI-4.0) id AA03253; Wed, 16 Jun 93 08:59:24 PDT Date: Wed, 16 Jun 93 08:59:24 PDT From: art@opal.acc.com (Art Berggreen) Message-Id: <9306161559.AA03253@opal.acc.com> To: big-internet@munnari.oz.au Subject: Re: What goes around comes around > >What I *do* know is that nobody, but *nobody*, ever had any idea that IPv4 >would *ever* be called upon to support a system of the size we see today. It >was designed as a large scale testbed and trial service system; the initial >address format consisted of an 8-bit network number, and a 24-bit rest! It has >been kludged over the years (first via A/B/C, then subnets, and now CIDR) to >handle a larger system, but we've about reached the end of the road. At this >point, due to a lack of foresight in the design, we are now faced with a >painful and expensive change. Amen, I'd like to underscore this, since I've been around since the first, four node prototype, ArpaNet. Anyone remember 1822 "short" headers? When DARPA started all of this, 6 BITS of IMP ID and 2 BITS of host ID were considered enough to interconnect that computers that DARPA wanted to network. Admittedly, this predates the growth of the idea of creating internets. Later DARPA wanted to create survivable computer communications over a variety of communications channels and a hostile evironment (like nukes taking out a large chunk). From this, the TCP/IP we know started to evolve. It just happens that its characteristics just happened to fit very well with the realities of hooking everything together into what has become the Internet (along with the fact that as a large research project, there was a lot of room for experimentation and modification). The view I remember early on, was that of a few LARGE military and university networks being connected. I don't recall many people predicting the explosive growth in LANs (remember LANs were invented about the same time) and the adoption of these technologies for general commercial usage. Hindsight is wonderfully 20/20, but the only prediction I'm willing to make for 15 years from now is that things WILL BE DIFFERENT. Art From owner-Big-Internet@munnari.oz.au Thu Jun 17 09:02:24 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA15724; Thu, 17 Jun 1993 09:02:49 +1000 (from owner-Big-Internet) Return-Path: Received: from motgate.mot.com by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA15712; Thu, 17 Jun 1993 09:02:24 +1000 (from dupont@mdd.comm.mot.com) Received: from pobox.mot.com ([129.188.137.100]) by motgate.mot.com with SMTP (5.65c/IDA-1.4.4/MOT-2.14 for ) id AA15225; Wed, 16 Jun 1993 17:59:55 -0500 Received: from mdd.comm.mot.com (mdisea.mdd.comm.mot.com) by pobox.mot.com with SMTP (5.65c/IDA-1.4.4/MOT-2.14) id AA24399; Wed, 16 Jun 1993 17:59:53 -0500 Received: from dragon.mdd.comm.mot.com by mdd.comm.mot.com (4.1/SMI-4.1) id AA25054; Wed, 16 Jun 93 15:59:51 PDT Received: from phoenix.mdd.comm.mot.com by dragon.mdd.comm.mot.com (4.1/SMI-4.1) id AA16502; Wed, 16 Jun 93 15:59:49 PDT Date: Wed, 16 Jun 93 15:59:49 PDT From: dupont@mdd.comm.mot.com (Pierre Dupont) Message-Id: <9306162259.AA16502@dragon.mdd.comm.mot.com> To: big-internet@munnari.oz.au, coleman@pandanus.ntu.edu.au Subject: Re: Routing idea - Y-Routing Cc: tanstey@pandanus.ntu.edu.au coleman@pandanus.ntu.edu.au (James P H Coleman) writes: > >After watching the discussion on the big-internet and the following idea >emerged: > >Y-Routers >======= >A Y-Router (Y-R) is a 3 port router such that a packet coming in has two >options on the direction to proceed, either to the left or to the right. >this can be represented as a 1 or 0. > [ discussion omitted ] > >Summary >======= > >There are some unresolved problems with this approach, not the least is the >fact that the Internet needs to be considered a binary tree and how to >maintain that tree with line outages etc. > >These problems are considerably out-weighed I by the following: > > 1) absolute simplicity of routing > 2) absolute simplicity of determining routes > 3) almost unlimited scalabitity of the whole approach > >These problems are being considered now. > >Work by: James P H Coleman and Tery Anstey > > The binary tree approach to routing is currently used to some extent in SS7 networks. In these networks, all routers (STPs) are replicated for reliability, and nodes always connect to router-pairs. Thus for every routing hop there is always a choice between two identical routers. To provide load balancing between routers and to allow successive packets to follow the same path through the network, the source node specifies a 5-bit SLS field (signaling link selector). Whenever a routing decision must be made, the low-order SLS bit is examined to select between one of the replicated routers. The SLS is then rotated so that a different bit is used for the next hop decision. By selecting different SLS values, a source node can guarantee an even load across all routing pairs along the path. By using the same SLS, a source node can guarantee that packets will follow the same path through the network (barring a router failure somewhere along the path). Of course routing decisions must still be made to select the next hop router pair. The binary SLS only helps in selecting between one of two identical routes. From owner-Big-Internet@munnari.oz.au Thu Jun 17 09:50:24 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA17487; Thu, 17 Jun 1993 09:50:50 +1000 (from owner-Big-Internet) Return-Path: Received: from MITCHELL.CIT.CORNELL.EDU by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA17472; Thu, 17 Jun 1993 09:50:24 +1000 (from Scott_Brim@cornell.edu) Received: from [132.236.236.19] (CU-DIALUP-0109.CIT.CORNELL.EDU) by mitchell.cit.cornell.edu (4.1/1.34/Honig-1.3) id AA02367; Wed, 16 Jun 93 19:50:07 EDT Message-Id: <9306162350.AA02367@mitchell.cit.cornell.edu> Date: Wed, 16 Jun 1993 19:50:45 -0400 To: jnc@ginger.lcs.mit.edu (Noel Chiappa), big-internet@munnari.oz.au From: Scott_Brim@cornell.edu X-Sender: swb@132.236.199.25 Subject: Re: What goes around comes around Noel, aren't these pretty harsh criticisms of a design which has succeeded so far beyond its original goals? >At this >point, due to a lack of foresight in the design, we are now faced with a >painful and expensive change. >people put in a quick, simple design which seemed like it was >efficient, and it came back to bite them very badly. From owner-big-internet@munnari.oz.au Thu Jun 17 13:13:35 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA24772; Thu, 17 Jun 1993 13:14:40 +1000 (from owner-big-internet) Return-Path: Received: from GINGER.LCS.MIT.EDU by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA29613; Thu, 17 Jun 1993 01:36:13 +1000 (from jnc@ginger.lcs.mit.edu) Received: by ginger.lcs.mit.edu id AA25649; Wed, 16 Jun 93 11:35:51 -0400 Date: Wed, 16 Jun 93 11:35:51 -0400 From: jnc@ginger.lcs.mit.edu (Noel Chiappa) Message-Id: <9306161535.AA25649@ginger.lcs.mit.edu> To: ULLMANN@process.com, jnc@ginger.lcs.mit.edu Subject: Re: graphs Cc: big-internet@munnari.oz.au, jnc@ginger.lcs.mit.edu It was areas I was questioning, not hierarchy; the two are separable. The gears in my head did an amazing cross-mesh when I read this, but it cleared up a bit when I read the rest of your message. The reason is that I view each layer of the heirarchy as selected a smaller and smaller subset of the general graph; for these subsets to be *useful* subsets to the routing, they must have some topological relationship, which more or less implies that they are "areas" of some sort. Thus, the statement above causes springs and gears to come out of my brain when I put it in; it doesn't compute! In a graph with non-local fractal topology, one could "address" an element by the vector of parameters that generate that element; one can then follow edges from any other element to that one in a rigourous procedure, but the graph is not locally connected in areas. ... Other classes of inverted parametric graphs with regular structure are fairly easy too, but fit the real world about as well. True, you have uniquely named each element by a process which selects smaller and smaller sets, but it's not clear how useful the structure in these names would be to a routing architecture. Since I didn't really follow your example, I'll have to stop there! I was thinking more about the definition of "area": there is a tendency to define them too strictly, where the routing protocols must then explicitly discover partitioning, and then take explicit action to recover the connectivity. Don't assume that the strict addressing model I used in my proof is one that I think is best for real life. I made it simple, to make the proof simple. Dealing with topological change is a tricky problem, inasmuch as there is a sort of isomorphism between a network topology, and an abstraction heirarchy which is used to name it. Leaving aside how to handle short-term events (which are probably headed for reversal in any event), which are probably best handled by means other than adjusting the abstraction heirarchy, over time there is a cost associated with the growing divergence between the heirarchy and the topology. Again, see those two messages for more detail. I think it would be better to use a loose definition of areas, where the hierarchical numbering allows the routing protocol to aggregate routes some distance from the (somewhat fuzzy) boundary of the area, not immediately at the border. I have thought for a long time that routing architectures should allow abstraction naming boundaries (i.e. area boundaries) to differ from abstraction action boundaries (i.e. the place where the routing starts tracking just X in stead of X.1 .. X.n). I also now think that it is probably best not to have the strict restriction that each K level entity appears in at least and at most one K-1 level entity. I believe that these two separate concepts equate to what you said, yes? Areas that are partitioned (in the stricter model) then simply fail to coelesce in the routing; the routing isn't doing anything differently. This is an acceptable method of handling short-term, reversible topology changes. However, as mentioned above, this won't work so well for long-term, permanent changes, as over time it will result in a build-up of non- useful routing overhead; entropy, if you will. Left too long, this results in the usual, i.e. heat-death. Sub-areas that then wander more-or-less permanently away from the containing area are then visible to the routing further away, but not an infinite distance away. I'm wondering about your placing of limits on this mechanism; what do you do with a situation which is outside the limits? Suppose subarea A.x.y.z.1.2.3 moves into area B.; i.e. a long way away. You have to have a way of dealing with this, right? What do they do, renumber? If so, then you do have the same ultimate mechanism that I do, it's perhaps just a slight difference of what the boundary is before you get to it. Now, to work on the general case of non-locality ... I didn't follow this brief allusion? Noel From owner-big-internet@munnari.oz.au Thu Jun 17 15:42:53 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA00748; Thu, 17 Jun 1993 15:43:17 +1000 (from owner-big-internet) Return-Path: Received: from venera.isi.edu by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA12295; Thu, 17 Jun 1993 07:31:00 +1000 (from lwei@ISI.EDU) Received: from nam.isi.edu by venera.isi.edu (5.65c/5.61+local-12) id ; Wed, 16 Jun 1993 14:29:58 -0700 Date: Wed, 16 Jun 1993 14:30:14 -0700 From: lwei@ISI.EDU Posted-Date: Wed, 16 Jun 1993 14:30:14 -0700 Message-Id: <199306162130.AA17977@nam.isi.edu> Received: by nam.isi.edu (5.65c/4.0.3-4) id ; Wed, 16 Jun 1993 14:30:14 -0700 To: big-internet@munnari.oz.au, coleman@pandanus.ntu.edu.au Subject: Re: Routing idea - Y-Routing Cc: tanstey@pandanus.ntu.edu.au The Y-router idea looks remarkably similar to what has been done in the ISI ATOMIC switches, which are composed of small elements of "X-router"s, or if the "X" is rotated by 45 degrees, "+ routers". It appears that X-routers inherently allow larger aggregate bandwidth than Y-routers because of the redundant linkages inside --- which avoids contention for common paths among different port-pairs. But at the smallest unit level, it is a matter of whether to route on "1 bit" or "2 bit" addresses. -- Liming > A 4 port router can be seen as the following: > > c > | d > b--+ / > \ / > + > | > a From owner-big-internet@munnari.oz.au Thu Jun 17 15:59:15 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA01465; Thu, 17 Jun 1993 15:59:54 +1000 (from owner-big-internet) Return-Path: Received: from venera.isi.edu by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA12499; Thu, 17 Jun 1993 07:37:58 +1000 (from prue@ISI.EDU) Received: from los.isi.edu by venera.isi.edu (5.65c/5.61+local-12) id ; Wed, 16 Jun 1993 14:37:41 -0700 Date: Wed, 16 Jun 1993 14:37:40 -0700 From: prue@ISI.EDU Posted-Date: Wed, 16 Jun 1993 14:37:40 -0700 Message-Id: <199306162137.AA23487@los.isi.edu> Received: by los.isi.edu (5.65c/4.0.3-4) id ; Wed, 16 Jun 1993 14:37:40 -0700 To: big-internet@munnari.oz.au Subject: Re: What goes around comes around Cc: Prue@ISI.EDU > From owner-Big-Internet@munnari.oz.au Mon Jun 14 14:03:15 1993 > Date: Mon, 14 Jun 93 11:27:14 EDT > From: "William Allen Simpson" > Subject: Re: What goes around comes around > > > or: There is nothing new under the Sun(shine) > > or: How to quote history to further your aims > > or: A blast from the past > > or: If we do not learn from history, we are bound to > > repeat its mistakes > > > > As some of you may know, Pip is the topic of my PhD thesis. > > Naturally in the course of writing a thesis, one must cite > > relavent work, so I went digging.... > > > No, I didn't know. Very interesting stuff. Of course, Noel has been > telling us that he has been talking about his plan for a decade. > > There might be another conclusion to be drawn: > > 1) the early internet architects already considered infinitely variable > length addresses in the header (leader). > > 2) they thought about how to implement it. > > 3) they rejected it. > > Might we not gain from the same insights? My understanding of what happened in the primordial soup that gave birth to the Internet concerning addressing was that Danny Cohen and probably others were in favor of variable length IP addressing. Others were concerned that routing on, or coding to variable length addresses would be too difficult. Besides who could conceive of a world needing more that 32 bits for addressing? So my belief is that Danny and probably others didn't reject the idea so much as they gave up trying to push the idea in favor of specification progress. Walt Prue From owner-Big-Internet@munnari.oz.au Thu Jun 17 17:32:44 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA04629; Thu, 17 Jun 1993 17:33:39 +1000 (from owner-Big-Internet) Return-Path: Received: from PANDANUS.NTU.EDU.AU by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA04616; Thu, 17 Jun 1993 17:32:44 +1000 (from coleman@PANDANUS.NTU.EDU.AU) Received: from [138.80.130.104] (COLEMAN.NTU.EDU.AU) by pandanus.cs.ntu.edu.au with SMTP id AA05725 (5.65c/IDA-1.4.4 for ); Thu, 17 Jun 1993 17:02:15 +0930 Message-Id: <199306170732.AA05725@pandanus.cs.ntu.edu.au> Date: Thu, 17 Jun 1993 17:01:16 +0930 To: big-internet@munnari.oz.au From: coleman@pandanus.ntu.edu.au (James P H Coleman) Subject: Re: Routing idea - Y-Routing Cc: coleman@PANDANUS.NTU.EDU.AU >> Problems >> ======== >> There are of course problems with this approach to do with the network >> being a binary treee etc. These problems should have solutions, if the >> solutions are relatively straight forward, as I suspect they are, which >> will mean a very slick routing (and addressing) scheme. >> > >Of course, one concern is the sensitivity of addresses to single >failures (a link here or a node there). This is true. Consider the following situations: Multiple Links between two routers =================================== ---A=======B--- It is up to the router to decide which link to use on the basis of some form of load-balancing. There are no "real" routing questions here. Link Failure with no alternative ================================ ---A---x ---B--- To bad - drop the packet and return an icmp message Link Failure with alternative (temporary) ============================= ---A---x -----B--- | | | | ---C----- The packet, arriving at A, with a route to B must be re-routed through C and then to B. It is up to router A to re-determine the new route from the current position to the final destination and put that new route into the packet, and then send it off. Congestion Control requiring re-routing ======================================= ---A----------B--- | | | | ---C----- Those packets re-routed are treated as if the direct linkl from A to B was temporarily cut. (see above) Prem Link Changes ================= This is another problem all together. Every router has an address relative to the root (ie a path). If a router is repositioned then the path to the router changes BUT the path of all those nodes/routers below the router still have the same relative path to the router has being moved. eg item Z has path: a/b/c/r/1/2/Z let us say router r has being moved to: a/g/h/j/k/r then the new path for item Z is as follows: a/g/h/j/k/r/1/2/Z so only those units below r (and including r) need to be renumbered. Okay, how does a unit get its number - should it be allocated one as is currently the case. Why should they so long as each unit has a unique identifier of some form and that ID is automatically allocated the number by some system (suggestion: DNS). I suggest that the unique ID be the domain name. Summary: 1) Every node/router has a unique domain name and is always referenced by use of the domain name, never by its "address". 2) The DNS can easily determine its path (path of the router next higher in the hierarchy with the addition of an extra component) and can easily (:)) inform a machine of its path simply by looking it up in its relatively small tables. The DNS can also perform its current role of giving the path of some other machine. NB This is not dynamic assignment of the form currently used] 3) Moving a router means informing all sub-routers of the change and informing all DNSs of their new address. This process can be automated. The result of all this is that within minutes a perm change in the network structure will be reflected in the paths of all the lower levels within minutes. Packets that are in transit can just be dropped. No real interruption to service at all. More importantly - no need for manual re-numbering. Aside: As an aside, this process can also be used to implement mobile hostsby having a server redirect the packets. Routing is done on paths, not networks. In fact, networks as such no longer exist, except for administrative purposes in which case a net is defined by a router. James From owner-Big-Internet@munnari.oz.au Fri Jun 18 01:19:15 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA23800; Fri, 18 Jun 1993 01:19:39 +1000 (from owner-Big-Internet) Return-Path: Received: from GINGER.LCS.MIT.EDU by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA23787; Fri, 18 Jun 1993 01:19:15 +1000 (from jnc@ginger.lcs.mit.edu) Received: by ginger.lcs.mit.edu id AA21575; Thu, 17 Jun 93 11:19:10 -0400 Date: Thu, 17 Jun 93 11:19:10 -0400 From: jnc@ginger.lcs.mit.edu (Noel Chiappa) Message-Id: <9306171519.AA21575@ginger.lcs.mit.edu> To: big-internet@munnari.oz.au Subject: Re: What goes around comes around Cc: jnc@ginger.lcs.mit.edu From: John Curran > [The IP address] has been kludged over the years ... to handle a larger > system As a side note, many folks would agree with the above, _except_ that CIDR isn't a kludge, but the removal of a kludge... Ooops, sorry, didn't mean to cast aspersions! Let me rephrase that as "has been modified over the years within limiting and painful constraints ...". CIDR especially is an elegant solution within some strict bounds. From: Simon E Spero If I were to type the phrase "Static EIDs, Dynamic addresses", would it start another month long EID war? I think the combatants are pretty worn out! I dunno, most days I think we've made progress (although I admit it has been slow, painful and tiring :-)! From: francis@thumper.bellcore.com (Paul Francis--formerly Tsuchiya) I would be inclined to agree wholeheartedly, and modify it slightly as follows..... "Static EIDs, Somewhat Dynamic addresses, Dynamic routes" I concur completely with this formulation. From: Vince Fuller IMHO, it would be a serious mistake for the community to rush into picking a long-term IP successor based primarily on how rapidly it can be deployed rather than on the functionality it offers. I concur. I'd like to see us delay the choice as long as possible, to allow more time for work in such still researchy areas as resource allocation, etc. It will also allow us to get a better idea of how deployment of new technologies (such as ATM) will make us want to change the basic service model, i.e. no-state datagram network. Noel From owner-Big-Internet@munnari.oz.au Fri Jun 18 02:46:22 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA27459; Fri, 18 Jun 1993 02:46:40 +1000 (from owner-Big-Internet) Return-Path: Received: from LOBSTER.WELLFLEET.COM by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA27452; Fri, 18 Jun 1993 02:46:22 +1000 (from rcallon@wellfleet.com) Received: from cabernet.wellfleet (cabernet.wellfleet.com) by lobster.wellfleet.com (4.1/SMI-4.1) id AA03393; Thu, 17 Jun 93 12:42:25 EDT Received: by cabernet.wellfleet (4.1/SMI-4.1) id AA10259; Thu, 17 Jun 93 12:46:13 EDT Date: Thu, 17 Jun 93 12:46:13 EDT From: rcallon@wellfleet.com (Ross Callon) Message-Id: <9306171646.AA10259@cabernet.wellfleet> To: Christian.Huitema@sophia.inria.fr, jnc@ginger.lcs.mit.edu Subject: Re: Comments on Internet Draft on SIP 64-bit Addressing Cc: big-internet@munnari.oz.au I am probably not the only one to have strong doubts about hierarchies and provider addresses -- the addressing BOF at Columbus was clearly unconclusive! The problem is indeed that if one does not believe in hierarchies one has to exhibit a routing architecture that allows to perform "flat routing" with a million networks internet. Which is an interesting theoretical exercise... Christian; Depending upon what you mean by "networks", a million is probably MUCH too small. We would be doing a great disservice if we were to try to deploy a next generation IP which could not comfortably scale to a network in every small business and in every home. Now, flat routing with a *billion* networks, that is a scary thought. Ross From owner-big-internet@munnari.oz.au Fri Jun 18 03:40:57 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA29528; Fri, 18 Jun 1993 03:41:03 +1000 (from owner-big-internet) Return-Path: Received: from GINGER.LCS.MIT.EDU by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA23387; Fri, 18 Jun 1993 01:06:28 +1000 (from jnc@ginger.lcs.mit.edu) Received: by ginger.lcs.mit.edu id AA21535; Thu, 17 Jun 93 11:06:13 -0400 Date: Thu, 17 Jun 93 11:06:13 -0400 From: jnc@ginger.lcs.mit.edu (Noel Chiappa) Message-Id: <9306171506.AA21535@ginger.lcs.mit.edu> To: Christian.Huitema@sophia.inria.fr, big-internet@munnari.oz.au Subject: Re: Comments on Internet Draft on SIP 64-bit Addressing Cc: jnc@ginger.lcs.mit.edu Ullmann is correct: the proof you gave assumes static graphs. Sure. I wanted to keep it simple, and I was only trying to respond to the exact statement you made, which was (thankfully :-) very simple. After all, I can only respond to what you actually say, no? :-) If you'd made a more complicated statement, of the form: "Addresses cannot be at the same time i) hierarchical (to allow aggregation), ii) based on the network topology, and iii) provide efficient and flexible routing with low overhead" I'd have had a harder time, since concepts like "efficient routing" aren't yes/no, but have to be quantified by some complex mathematical analysis, and I'm not good at that kind of math. (Not to mention which nobody would bother reading it! :-) Kleinrock and Kamoun, who ... go on quantifying the impact on routing quality. Speaking of complex math, some recent papers (e.g. "Routing with Polynomial Communication-Space Tradeoff") by Baruch Awerbuch (baruch@ theory.lcs.mit.edu) are starting to do rigorous math on routing optimality and overhead in various heirarchical routing schemes. Frankly, my eyes glaze over on about page 5 (my brain isn't wired for this stuff), but some of you might like it. The assumption that the graph "only changes in local parts" is not well funded either. I don't recall stating the opposite? One frequent non local change is the "change provider". A consequence on a strict hierarchical plan (following K&K's algorithm) is indeed that one should do address renumbering. This can be handled in the short term (during a transition) as a partition, perhaps by advertising this piece of the topology as an independant object within that area of the topology with this it does not have a common prefix. (I.e. if A.x.1 gets moved and plugged into A.y, you will have to advertise A.x.1 throughout A as an independant thing, but outside of A you don't need to do anything special). However, in the long run you will have to renumber, else entropy will get you, as I indicated in a previous message. Then comes the case of a "multiple provider" attachment. Applying the algorithm you described leads to either placing those "multi-homed" areas near the top of the hierarchy (no aggregation), or alternatively to assign multiple addresses to every hosts in the multi-homed areas. Neither is very satisfactory Dave Clark has been talking about this case for a long time, and yes, it is a difficult problem to solve this one *efficiently*; perhaps the most difficult problem in the whole routing game. I don't like either of these two solutions (the multi-adrress solution is no solution; multiple options at several layers of the network result in a combinatorial explosion in the number of addresses needed), but there are others. For instance, a single address serves to uniquely identify the location of a host, but before constructing a route, you find out something about the local topology, and from that discover there are multiple providers that will get you there. Cleaner, but perhaps more expensive. Remember, just because the address is heirarchical, it doesn't mean the routing *has to be*. It all depends on how much routing overhead you are willing to pay for; the more overhead, the more efficient (and the less strictly hierarchical) your routes will be. both are a departure from the curent IP architecture where there is no relation between your "network number" and the contracts you have with your providers. Sigh, this is a "have your cake and eat it too" proposition. There has to be *some* identifier which tells you where in the topology something really is; the routing needs this to work efficiently. If you change providers, this has to change, since where the host is located in the topology *has changed*! Now, maybe you have some *other* invariant identifier which stays the same no matter where you are, but you'll have to map from this one into the first one before the routing can use it. Right? I am probably not the only one to have strong doubts about hierarchies and provider addresses Hey, I agree it's painful, but so's thermodynamics. Doesn't mean we can get around it, though. The problem is indeed that if one does not believe in hierarchies one has to exhibit a routing architecture that allows to perform "flat routing" with a million networks internet. Exactly. Which is why I've spent the last decade+ trying to understand how to bludgeon heirarchical routing into doing what we want, and what the ultimate theoretical limits of very large scale routing are. Nimrod, anyone? (Speaking of which, there's going to be an announcement shortly of major progress which has been occurring offstage; don't ask me for details, just hold on a bit!) Noel From owner-big-internet@munnari.oz.au Fri Jun 18 05:14:59 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA03126; Fri, 18 Jun 1993 05:15:16 +1000 (from owner-big-internet) Return-Path: Received: from babyoil.ftp.com by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA29065; Fri, 18 Jun 1993 03:28:54 +1000 (from kasten@ftp.com) Received: by ftp.com id AA09184; Thu, 17 Jun 93 13:28:41 -0400 Date: Thu, 17 Jun 93 13:28:41 -0400 Message-Id: <9306171728.AA09184@ftp.com> To: rcallon@wellfleet.com Subject: Re: Comments on Internet Draft on SIP 64-bit Addressing From: kasten@ftp.com (Frank Kastenholz) Reply-To: kasten@ftp.com Cc: Christian.Huitema@sophia.inria.fr, jnc@ginger.lcs.mit.edu, big-internet@munnari.oz.au > I am probably not the only one to have strong doubts about hierarchies and > provider addresses -- the addressing BOF at Columbus was clearly unconclusive! > The problem is indeed that if one does not believe in hierarchies one has to > exhibit a routing architecture that allows to perform "flat routing" with a > million networks internet. Which is an interesting theoretical exercise... > > Christian; > > Depending upon what you mean by "networks", a million is probably MUCH too > small. We would be doing a great disservice if we were to try to deploy a > next generation IP which could not comfortably scale to a network in every > small business and in every home. > > Now, flat routing with a *billion* networks, that is a scary thought. The original call for IPng (from the ROAD warriors) was either 10E9 or 10E12 networks (I do not recall which). That's either 1,000 Million, or 1 Million Million networks... -- Frank Kastenholz FTP Software 2 High Street North Andover, Mass. USA 01845 (508)685-4000 From owner-Big-Internet@munnari.oz.au Fri Jun 18 05:41:08 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA04192; Fri, 18 Jun 1993 05:41:34 +1000 (from owner-Big-Internet) Return-Path: Received: from MITCHELL.CIT.CORNELL.EDU by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA04173; Fri, 18 Jun 1993 05:41:08 +1000 (from Scott_Brim@cornell.edu) Received: from [132.236.199.71] (SLUF.CIT.CORNELL.EDU) by mitchell.cit.cornell.edu (4.1/1.34/Honig-1.3) id AA15053; Thu, 17 Jun 93 15:40:55 EDT Message-Id: <9306171940.AA15053@mitchell.cit.cornell.edu> Date: Thu, 17 Jun 1993 15:42:20 -0400 To: kasten@ftp.com From: Scott_Brim@cornell.edu X-Sender: swb@132.236.199.25 Subject: Re: Comments on Internet Draft on SIP 64-bit Addressing Cc: big-internet@munnari.oz.au At 1:28 PM 6/17/93 -0400, Frank Kastenholz wrote: >The original call for IPng (from the ROAD warriors) was either 10E9 >or 10E12 networks (I do not recall which). That's either 1,000 >Million, or 1 Million Million networks... You don't recall which because it got changed as we were starting up. Vint asked for 1e9 domains at the initial lunch meeting, but when our mission statement came out it asked for 1e9 networks. There are designs which seem to meet 1e9 networks that I doubt would be able to handle 1e9 domains. Scott From owner-Big-Internet@munnari.oz.au Fri Jun 18 17:00:42 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA01141; Fri, 18 Jun 1993 17:01:14 +1000 (from owner-Big-Internet) Return-Path: Received: from mitsou.inria.fr by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA01136; Fri, 18 Jun 1993 17:00:42 +1000 (from huitema@mitsou.inria.fr) Received: by mitsou.inria.fr (5.65c/IDA-1.2.8) id AA21778; Fri, 18 Jun 1993 09:01:09 +0200 Message-Id: <199306180701.AA21778@mitsou.inria.fr> To: kasten@ftp.com Cc: big-internet@munnari.oz.au Subject: Re: Comments on Internet Draft on SIP 64-bit Addressing In-Reply-To: Your message of "Thu, 17 Jun 93 13:28:41 EDT." <9306171728.AA09184@ftp.com> Date: Fri, 18 Jun 93 09:01:08 +0200 From: Christian Huitema Frank, I mentioned 1 million because current solutions for flat routing scale at best to smtg like 20000. The idea was "even doing it for 1000000 is an interesting challenge now". The IPng calls for a billion nets and a trillion hosts; these figures are not drawn out of thin air, and can be backed by some statistics. The Internet is currently doubling size every year, and counts 13000 nets. At that rate, the million network mark is reached within 6 years, and the trillion mark within 16 years -- if the rate stays constant for 16 years, which may be another debate. IPng is certainly requested to last at least 16 years! Christian Huitema From owner-Big-Internet@munnari.oz.au Fri Jun 18 17:42:26 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA02486; Fri, 18 Jun 1993 17:42:40 +1000 (from owner-Big-Internet) Return-Path: Received: from mitsou.inria.fr by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA02480; Fri, 18 Jun 1993 17:42:26 +1000 (from huitema@mitsou.inria.fr) Received: by mitsou.inria.fr (5.65c/IDA-1.2.8) id AA21887; Fri, 18 Jun 1993 09:43:06 +0200 Message-Id: <199306180743.AA21887@mitsou.inria.fr> To: jnc@ginger.lcs.mit.edu (Noel Chiappa) Cc: big-internet@munnari.oz.au Subject: Re: Comments on Internet Draft on SIP 64-bit Addressing In-Reply-To: Your message of "Thu, 17 Jun 93 11:06:13 EDT." <9306171506.AA21535@ginger.lcs.mit.edu> Date: Fri, 18 Jun 93 09:43:05 +0200 From: Christian Huitema > (Speaking of which, there's going to be an announcement shortly of major > progress which has been occurring offstage; don't ask me for details, just > hold on a bit!) > > Noel Suddenly, a heavy clock of silence draped the Internet. Angels stopped blowing their trumpets, and a million networkers almost suffocated while holding their breath... Christian Huitema From owner-Big-Internet@munnari.oz.au Sat Jun 19 21:35:29 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA01534; Sat, 19 Jun 1993 21:36:25 +1000 (from owner-Big-Internet) Return-Path: Received: from sunic.sunet.se by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA01509; Sat, 19 Jun 1993 21:35:29 +1000 (from rafal@camk.edu.pl) Received: from alfa.camk.edu.pl by sunic.sunet.se (5.65c8-/1.28) id AA06703; Sat, 19 Jun 1993 13:33:39 +0200 Received: from dzeta.camk.edu.pl by alfa.camk.edu.pl (4.1/RP-1.0) id AA01894; Sat, 19 Jun 93 13:33:51 +0200 Date: Sat, 19 Jun 93 13:33:50 +0200 From: rafal@camk.edu.pl (Rafal Pietrak) Message-Id: <9306191133.AA01894@alfa.camk.edu.pl> Received: by dzeta.camk.edu.pl (4.1/SMI-4.1) id AA16104; Sat, 19 Jun 93 13:32:59 +0200 To: big-internet@munnari.oz.au Subject: Re: Routing idea - Y-Routing Hi, The more I think about the Y-router concept the more I like it. Of cource there are problems to solve, but ... 1) Noel told us some time ago, about the idea of routers (forwarders) and route servers, being separate entities. This fits nicely to the 'binary' routing of Y-architecture (IMHO). Forwarders are Y-routers, routes (paths) are provided by the root of the Internet tree. 2) Now, the root of paths in the whole world does not have to be uniq. Let's imagine that there are 100,000 independant tree structures layered on the Internet link topology, with thair roots spread randomly. Every host has one such 'root' quite near itself, and this 'local root' sees Internet from its particular perspective. 3) The link structure of the current Internet is such, that it doesn't form a tree (from arbitraty perspective). Hosts by deffinition would be multi-homed (meny paths go from host A to host B). One needs EID (no I don't wont to start the EID war again -- just list options). 4) The paths providerd by such 'local root' are NOT globally uniq (of cource). The IP header should contain: - noneuniq binary path of a route _between_ source and destination - current hop indicator - source EID - destination EID (Note, that there is no need for TTL :) 5) 'local root' path servers resambly quite nicely the concept of 'areas' in the internet -- objects that could aggregate addresses. Here the area _is_ 'local root'; Its 'area' is the whole Inetnet, only seen from local perspective. Nobody needs global hierarchy anymore. 6) If route servers ('local roots') are to provide paths to every host in the Internet, quering host will receive hundreds of possible Y-paths. The originating host _could_ then spray the destination with small packet on every path, and use first 3-10-20 reply packet paths to continue communication on (load balancing for granted ;-). Link failures would not be catastrophic, for other paths are available. Intermediate link congestion could be acted upon by a host, on the reception of 'source quench' packets from a router (forwarder) along that path. 7) What I find particulary atractive in the Y-architecture, is that in future, routers (forwarders) will be exposed to ever increasing link speeds, and have to do forwarding as fast as possible -- Y-routing is so simple, that it can be hardwired in silicon. On the other hand, end nodes (hosts) are cheeper and faster these days, thus decisions (i.e. on routing) can be moved there. -Rafal From owner-big-internet@munnari.oz.au Sun Jun 20 06:18:36 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA16932; Sun, 20 Jun 1993 06:18:51 +1000 (from owner-big-internet) Return-Path: Received: from ux1.cso.uiuc.edu by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA11784; Sun, 20 Jun 1993 03:21:45 +1000 (from nagle@netcom.com) Received: from netcom4.netcom.com by ux1.cso.uiuc.edu with SMTP id AA01561 (5.67a8/IDA-1.5 for ); Sat, 19 Jun 1993 12:20:33 -0500 Received: by netcom4.netcom.com (5.65/SMI-4.1/Netcom) id AA14130; Sat, 19 Jun 93 10:22:11 -0700 Newsgroups: info.big-internet Path: nagle From: nagle@netcom.com (John Nagle) Subject: Re: Routing idea - Y-Routing Message-Id: Organization: NETCOM On-line Communication Services (408 241-9760 guest) References: <199306160333.AA02265@pandanus.cs.ntu.edu.au> Date: Sat, 19 Jun 1993 17:22:08 GMT Lines: 57 Apparently-To: info-big-internet@ux1.cso.uiuc.edu coleman@pandanus.ntu.edu.au (James P H Coleman) writes: >After watching the discussion on the big-internet and the following idea >emerged: >Y-Routers >======= >A Y-Router (Y-R) is a 3 port router such that a packet coming in has two >options on the direction to proceed, either to the left or to the right. >this can be represented as a 1 or 0. Routing in hypercube-type multiprocessors works much like this. NCube Corp. makes such machines. A 64-cpu machine is organized as a 2x2x2x2x2x2 6-dimensional hypercube. Each CPU has a connection to all 6 of its neighbors. Each CPU has an ID which is a 6-bit number indicating its position in the hypercube. To route an inter-CPU message, the sending CPU XORs the destination address with its own address. Each 1 bit indicates a direction in N-space in which the message must be moved. So the CPU picks one of the 1 bit positions (randomly, or based on queue length) and sends the message to its neighbor CPU in the indicated direction. The receiving CPU repeats this process, and when the receiving CPU does its XOR, the result will have one fewer 1 bits than at the preceding stage, so this approach is loop-free. When an XOR results in no 1 bits, the message has reached its destination. The topology doesn't have to be quite this rigid. A node need not have connections to all its neighbors in N dimensions for this to work. But there must always be a connection to a neighbor which is nearer to the destination than the sending node for all possible source/destination pairs, so there's a stringent restriction on the numbering plan. Hypercube routing can thus be seen as an N-dimensional generalization of Y-R routing. This is actually a reasonable way to organize a big switch internally. Didn't Datakit work something like this? The pure binary tree scheme first described for Y-R routing leads to heavier loads as you approach the root of the tree. A significant fraction of the load would land on the root node. So we don't want a pure tree; something with more connectivity is needed. At the other extreme, a hypercube is too strongly connected to build economically. The bit-path source routed approach has come up before, generally in virtual circuit systems. There you're willing to go to some trouble to set up a path when the connection is made, but message passing on active connections is made as simple as possible. This is the usual telephony approach: all the smarts are in call setup; the switch fabric is dumb. Doesn't ATM work something like this? If you like source-routed approaches, it's worth taking a detailed look at how the phone industry does it. Their approach does scale up well. It's worth noting that if you allow any re-routing, as suggested above, the rerouting process will lengthen the bit string for Y-R routing. Thus, the loop-free property is lost, and you need TTL or some equivalent message to detect loops. John Nagle From owner-Big-Internet@munnari.oz.au Mon Jun 21 01:07:06 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA19931; Mon, 21 Jun 1993 01:07:13 +1000 (from owner-Big-Internet) Return-Path: Message-Id: <9306201507.19931@munnari.oz.au> Received: from research.att.com by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA19928; Mon, 21 Jun 1993 01:07:06 +1000 (from hgs@research.att.com) Received: by inet; Sun Jun 20 11:06 EDT 1993 Date: Sun, 20 Jun 93 11:06:12 EDT From: hgs@research.att.com (Henning G. Schulzrinne) To: big-internet@munnari.oz.au Subject: Re: Routing idea - Y-Routing See also the papers by Cidon et al. on the PARIS architecture, where a similar source routing method is employed (with a few more bits per hop). They claim it to be faster than the label-swapping used by ATM; routing bits are trimmed as they are no longer needed, shortening the packet as it approaches its destination. See (among other papers): jhsn = Journal of High-Speed Networks @ARTICLE{Cido92:Critique, AUTHOR="Cidon, Israel and Derby, Jeff and Gopal, Inder and Kadaba, Bharath", TITLE="A critique of {ATM} from a data communications perspective", JOURNAL=jhsn, YEAR=1992, VOLUME=1, NUMBER=4, PAGES="315--336", ABSTRACT="Fast packet switching is emerging as the preferred technology for future high speed, integrated networks. Asynchronous transfer mode (ATM) is an approach to FPS that is in the process of standardization and is the preferred approach of the carrier community. Concurrently, alternative approaches to FPS based on variable sized packets have been proposed by segments of the data communications industry. These approaches include frame relay and an approach developed by IBM called PARIS. The purpose of this paper is to examine the suitability of ATM for data communications relative to some of these alternative approaches.", KEYWORDS="ATM; PTM; fast packet switching; gigabit networks; data", ANNOTE="Uses 9-byte ATM per-cell overhead; arguments: header/padding overhead; extra delay due to higher overhead; adaptation layer processing; cell discarding during overload (avalanche effect)", KEYWORDS="ATM; PTM; fast packet switching; gigabit networks; data", ENTRYBY="Sc" } --- Henning Schulzrinne (hgs@research.att.com) AT&T Bell Laboratories (MH 2A-244) 600 Mountain Ave; Murray Hill, NJ 07974 phone: +1 908 582-2262; fax: +1 908 582-5809 From owner-Big-Internet@munnari.oz.au Fri Jun 25 22:54:23 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA09042; Fri, 25 Jun 1993 22:54:39 +1000 (from owner-Big-Internet) Return-Path: Received: from sun2.mhs-relay.ac.uk by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA09039; Fri, 25 Jun 1993 22:54:23 +1000 (from cmk@aberystwyth.ac.uk) Via: uk.ac.aberystwyth; Fri, 25 Jun 1993 13:53:23 +0100 Received: by deca (5.57/aberclient-4.0) id AA08289; Fri, 25 Jun 93 13:52:16 +0100 Date: Fri, 25 Jun 93 13:52:16 +0100 From: cmk@aberystwyth.ac.uk Message-Id: <9306251252.AA08289@deca> To: big-internet@munnari.oz.au Subject: Please subscribe me E cmk@aber (UK) \S Clive King \V \F M cmk@aber.ac.uk (inet) \N Technical Support Group, \O +44 \A +44 970 A ...!mcsun!ukc!aber-cmk \A Dept of Computer Science, \I 970 \X 617172 I (uucp) \I University of Wales, \C 622427 L \L Aberystwyth, Dyfed. \E SY23 3DB. UK. From owner-Big-Internet@munnari.oz.au Wed Jun 30 18:11:15 1993 Received: by munnari.oz.au (5.83--+1.3.1+0.50) id AA15010; Wed, 30 Jun 1993 18:11:28 +1000 (from owner-Big-Internet) Return-Path: Message-Id: <9306300811.15010@munnari.oz.au> Received: from bells.cs.ucl.ac.uk by munnari.oz.au with SMTP (5.83--+1.3.1+0.50) id AA14992; Wed, 30 Jun 1993 18:11:15 +1000 (from J.Crowcroft@cs.ucl.ac.uk) Received: from waffle.cs.ucl.ac.uk by bells.cs.ucl.ac.uk with local SMTP id ; Wed, 30 Jun 1993 09:11:00 +0100 To: big-internet@munnari.oz.au Subject: where in the world is that router...? Date: Wed, 30 Jun 93 09:10:59 +0100 From: Jon Crowcroft for a variety of reasons, i believe all IPng routers should have GPS receivers in 1. you could auto-configure georgraphic based addressing 2. you could timestamp and/or location stamp cryptoi sealed packets and make it impossibler to spoof being a router unless you could spoof the delay from there or be there. 3. numerous other securitry benefits 4. network performance monitoring/logging could be synchronsied (via ntp etc) to provide global view/analysis hitherto hard..and impossible if FIXes didnt have ethernets and van hadn't given us tcpdump... spose this should go to comp.protocols.ntp or whatever, but... jon