Subject: Re: IPv6: Past mistakes repeated?

From: "Steven M. Bellovin" <[email-masked]>
Date: Mon, 24 Apr 2000 09:19:39 -0400

In message <BB2831D3689AD211B14C00104B14623B1E7569@HAZEN04>, "David A Higginbot
ham" writes:
>I agree! Why create a finite anything when an infinite possibility exists?
>On another note, I have heard the argument that a unique identifier already
>exists in the form of a MAC address why not make further use of it?

Would it surprise anyone to hear that all of that was considered and 
discussed, ad nauseum, in the IPng directorate?  That's right -- we weren't 
stupid or ignorant of technological history.  There were proponents for 
several different schemes, including fixed-length addresses of 64 and later 
128 bits, addresses where the two high-order bits denoted the multiple of 64 
to be used (that was my preference), or CLNP, where addresses could be quite 
variable in length (I forget the maximum).

But the first thing to remember is that there are tradeoffs.  Yes, infinitely 
long addresses are nice, but they're much harder to store in programs (you can 
no longer use a simple fixed-size structure for any tuple that includes an 
address) and (more importantly) route, since the router has to use the entire 
address in making its decision.  Furthermore, if it's a variable-length 
address, the router has to know where the end is, in order to look at the next 
field.  (Even if the destination address comes first, routers have to look at 
the source address because of ACLs -- though you don't want address-based 
security (and you shouldn't want it), you still need anti-spoofing filters.)  
I should add, btw, that there's a considerable advantage to having addresses 
be a multiple of the bus width in size, since that simplifies fetching the 
next field.)

As I said, I (and others) preferred a limited form of variable-length addresses. 
Given the various tradeoffs, we "lost".  One reason is something that was 
pointed out by a number of people:  code that isn't exercised generally doesn't
work well.  If we didn't have really long addresses in use from the beginning, 
some major implementations wouldn't support them properly.

Some minor points.  Using a MAC address was considered and rejected.  
First, not all machines have them.  Second, some machines have more than one 
-- which should be used?  Third, although MACs are supposed to be globally 
unique, accidents happen and there have been collisions.  Fourth, they're two 
short -- 48 bits then, moving towards 64 bits today.  Fifth, there's the issue 
of privacy.  Sixth -- and this rules out pure geographic addressing schemes -- 
IP addresses are tied to the routing system.  We don't know any other way to 
route large numbers of networks other than by using the high-order bits of the 
address.  If you want addresses allocated geographically, your routing has to 
be geographic.  (There have been designs for that, I should add, such as the 
Metropolitan Area Exchanges.  But for those to work, assorted ISPs would have 
to co-operate on a large scale, something that I don't think will happen.)  
Phone numbers are allocated geographically, but that only works because 
historically, most areas only had one monopoly phone company.  That has 
changed today, in many parts of the world, leading to complexities such as (in 
the U.S.) local number portability -- but telephone networks do one lookup per 
call, not one per packet.

		--Steve Bellovin

---

From: "Anthony Atkielski" <[email-masked]>
Date: Mon, 24 Apr 2000 22:18:09 +0200

> But the first thing to remember is that there are
> tradeoffs.  Yes, infinitely long addresses are nice,
> but they're much harder to store in programs (you
> can no longer use a simple fixed-size structure for
> any tuple that includes an address) ...

Sure you can.  You just allocated the fixed space generously, _and_ you
include code that traps any address with more bytes than you can handle.  If
that ever happens, you rebuild your table with a larger fixed space.  You
might include code to catch addresses that approach the limit so that you
have time to rebuild the table at your leisure, rather than when the routing
actually fails, of course.

> ... and (more importantly) route, since the router
> has to use the entire address in making its decision.

Why does it need the entire address?

You only need the entire address if addresses are assigned arbitrarily from
the address space, such that no subset of the complete address is in itself
sufficient to complete any portion of the routing.  That is indeed a problem
today, with address allocation that does not necessarily strictly following
routing requirements.  But that was imposed by the very fact of trying to
allocate a fixed space in advance.  In a variable-length address space, you
don't have to anticipate any kind of advance allocation--you can just add
digits to addresses where they are required, and routers only need to look
at enough of an address to figure out where it should go next.  In a
variable-length scheme, you can be sure that any address that begins with
19283 always goes down the route you have for 19283, no matter what the
remaining digits are.  (Naturally, you could route with finer granularity at
some nodes, if you wanted to, but you wouldn't necessarily be obligated to
do that.)

> Furthermore, if it's a variable-length address, the
> router has to know where the end is, in order to look
> at the next field.

Just put that up front.  For example, prefix the address with a length byte.
If the byte is zero, the address is four bytes long (compatible with IPv4).
If it is one, the address is five bytes long.  And so on, up to 254+4= 258
bytes long.  If the byte is 255, however (unlikely, but this scheme would
provide for _any_ address length), then the _next_ byte specifies additional
bytes to be added to 254 (i.e., lengths of 254 through 508 bytes).  This
second byte follows the same pattern, and so on.  You'll never run out of
addresses this way, ever.

It's not really hard.  You just have to write the code up front to handle
it.  And if you don't want to allow for infinite capacity (you have to stop
somewhere, in any practical implementation), you just make darn sure that
you have code that will trap any address longer than you can handle.  If
anything ever hits the trap, you change some parameters and recompile, and
you're back online.

> Even if the destination address comes first, routers have
> to look at the source address because of ACLs -- though
> you don't want address-based security (and you shouldn't
> want it), you still need anti-spoofing filters.

Hmm... I don't know.  If you restrict the address field to routing only, do
you still need anti-spoofing?  A given address can lead to only one
endpoint, unless I'm missing something here.

> One reason is something that was pointed out by a number
> of people:  code that isn't exercised generally doesn't
> work well.  If we didn't have really long addresses in
> use from the beginning, some major implementations wouldn't
> support them properly.

It's a lot easier to fix a bug than to rewrite the protocol from scratch
when it runs out of capacity.

> There have been designs for [geographic addressing], I
> should add, such as the Metropolitan Area Exchanges.
> But for those to work, assorted ISPs would have
> to co-operate on a large scale, something that I
> don't think will happen.

Why would they have to cooperate in a variable-length scheme?  They would
only allocate addresses on their branch.  They could route within their
branch without knowing or caring about other branches (as long as they know
the high-order digits identifying their own branches, which someone else
would assign to them).  And if they ever saw addresses with high-order
digits that didn't match their own assigned digits, they'd know that the
address meant "elsewhere."  Of course, finer granularity would be possible,
but not required.

That's how telephones work.  If you call someone in Mongolia from the U.S.,
the U.S. exchanges don't have to know or care about the trailing digits in
the number; they only have to look at enough of the number to know to route
the call towards Mongolia.  Can you imagine what the telephone system would
be like if every country had to know every detail about the numbering system
of every other country?

> Phone numbers are allocated geographically, but that
> only works because historically, most areas only had
> one monopoly phone company.

That's not a requirement.  Just assign additional companies an additional
branch.   At most, the new companies would add one digit to the address.

> ... but telephone networks do one lookup per call, not
> one per packet.

I should think you'd be able to optimize this, especially since, with a
variable-length scheme, you only need to look as far as necessary to pick a
route.  If you have a route for 12847, you know that 12847xxxxxx is always
going to take that route.  Depending on how many outbound routes you have,
this could be very fast indeed.

  -- Anthony

---

From: [email-masked]
Date: Mon, 24 Apr 2000 21:39:28 -0400

> at enough of an address to figure out where it should go next.  In a

Actually, we argued a *lot* about fixed/variable.  The reason 128
bit fixed won out was to a large extent due to the people from
various large high-performance router companies wanting a way to 
switch packets *quickly*.  At the time, a DS3 was considered REALLY
fast, and only a few places had FDDI campus backbones.

The problem is that the router guys wanted to fast-path the case of
"no IP option field, routing entry in cache" so that after seeing
only the first few bytes, they could know what interface to enqueue
the outbound packet on *before the entire packet had even come in*.
So for them, the idea of being able to take a known fixed-lenght field
that happened to line up nicely on the hardware memory cache lines,
stuffing it through an associative-lookup cache or other hardware
assist, and knowing in one or three cycles how to route it, was
VERY enticing.

Of course, an OC48 instead of a DS3 only makes it more crucial -
do the math, and figure out how many nanoseconds you have to make
a routing decision when reading off an OC48...

> it.  And if you don't want to allow for infinite capacity (you have to stop

It's easy to do for an end-user workstation that's already bogged down
by the bloat inherent in <insert your least favorite OS vendor here>.

It's hard to do for something that's truly high-performance.

> endpoint, unless I'm missing something here.

Well, at least around here, we also look at the *source* address on
all packets inbound to our routers to see if they make sense.  If it's
coming in from off-campus, it shouldn't have a prefix that belongs to
our AS.  If it's coming into our backbone from a building subnet, the
source better be in that subnet's range.  And so on.  RFC2267 talks
about it in more detail.

				Valdis Kletnieks
				Operating Systems Analyst
				Virginia Tech

---

From: "Anthony Atkielski" <[email-masked]>
Date: Tue, 25 Apr 2000 20:16:28 +0200

From: <[email-masked]>

> The problem is that the router guys wanted to fast-path
> the case of "no IP option field, routing entry in cache"
> so that after seeing only the first few bytes, they could
> know what interface to enqueue the outbound packet on
> *before the entire packet had even come in*.

But this would be even faster with a variable-length address than with a
fixed-length address.  You just read address bits until you find a match,
and ignore the rest.

> It's easy to do for an end-user workstation that's
> already bogged down by the bloat inherent in <insert
> your least favorite OS vendor here>.
>

Something that is high-performance usually costs a lot more than an end-user
workstation, too, especially with the 90% gross margin that the vendor adds
to the hardware price.  It's reasonable to expect to get what you pay for.

  -- Anthony

---

From: [email-masked]
Date: Tue, 25 Apr 2000 15:52:05 -0400

> fixed-length address.  You just read address bits until you find a match,

Umm.. No.

"until you find a match" works totally differently in the silicon world
than for programming.

Today's homework assignment:  Using 7400-series logic chips, design and
implement an 8-bit adder (you may ignore the carry out of the high bit).
For bonus credit - implement an arbitrary-length adder, the number of bits
being specified in-band (do NOT use the signalling bits as input to the adder).

When you understand the difference, enlightenment will soon follow.

(And yes, I thought variable-length was a Cool Idea too, until one of the
Cisco crew made the case for router convenience...)

Somebody with a better memory than I can point at the big-internet archives,
where this was all thrashed out the FIRST time...

-- 
				Valdis Kletnieks

---

From: John Stracke <[email-masked]>
Date: Tue, 25 Apr 2000 16:58:32 -0400

> fixed-length address.  You just read address bits until you find a match,

That's *slow*.

Remember, fast routers are built out of logic gates, not software.  Dynamic
tree structures are hard to build out of gates (no recursion).

> to the hardware price.  It's reasonable to expect to get what you pay for.

Well, yes.  Backbone providers pay lots and lots of money to get routers that
actually work.  If all they got was gated running on a workstation, the
backbones wouldn't be performing anywhere near current levels.  (Proof: that's
what the old T3 NSFNet routers were, RS/6000s with special hardware to talk to
the T3.  Supposedly, they couldn't even keep up with T3s, let alone modern
OC-mumbles.)

--
/==============================================================\
|John Stracke    | http://www.ecal.com |My opinions are my own.|
|Chief Scientist |=============================================|
|eCal Corp.      |"Collect call from reality, will you accept  |
[email-masked]|the--" *click*                               |
\==============================================================/