karn@JUPITER.BELLCORE.COM (Phil R. Karn) (08/18/87)
The recent discussion about varying subnet sizes was interesting. I have implemented a "generalized subnetting" scheme in my own IP routing code that handles this and many similar problems quite well. Basically, I completely ignore the usual rules that distinguish class A, B and C addresses. Instead I keep an explicit subnet mask with each entry in the routing table. (Actually, I use integers between 0 and 32, but the semantics are the same). When a packet is to be routed, I search the routing table for the "best" match under control of the mask. That is, if my routing table contains target width interface gateway 128.96.33.101 32 sl0 128.96 16 ec0 0 0 ec0 128.96.41.1 and I present the address 128.96.33.101, all three entries match. In this case, I select the entry with the greatest width, i.e., the first one. Note that the last entry always matches every address; it is the default route. The first one is a host-specific entry, matching only one IP address. Note that the routing table points to an INTERFACE name, not a gateway address. The gateway field is optional. It is filled in only if the target is to be reached through a gateway on a multiple access subnet, in which case the gateway field is passed down to the subnet driver for translation into a subnet address. If the gateway field is null, the subnet driver is given the target IP address for translation; this would be done if the target is directly on the same subnet. If the subnet is a point-to-point link, the gateway address field is ignored altogether since the subnet has no need for link level addresses. With this scheme you can construct a completely arbitrary internet out of ad-hoc point-to-point links, incompletely connected broadcast subnets (e.g., amateur packet radio), partitioned networks as well as "real" subnets like Ethernets without filling up your routing table with lots of host-specific entries. You can "bunch up" address groups that begin with a common bit pattern, regardless of whether they are really all hosts on the same subnet, or you can split off one or more hosts that are behind a point-to-point link, for example. It works very well. Phil
Mills@UDEL.EDU (08/19/87)
Phil, You have described the scheme used in the intrepid fuzzballs, although those animals use a full 32-bit mask to allow arbitrary field geometries. The problem is that the scheme is not particularly fast and is hard to hash. The solution may be an algorithm that quickly turns a description such as yours into a partition of the 32-bit space which can be hashed and used in a match-once fashion. The fuzzscheme, now indigenous to the NSFNET Backbone, provides a hand way to build ARPANET tunnels through other nets, which has been found a handy feature during times when routing is otherwise broken. Dave
karn@FALINE.BELLCORE.COM.UUCP (08/19/87)
I thought this probably wasn't original, but I'm glad to see somebody else considers it worthwhile. I too was concerned about the speed of the algorithm. I originally implemented it in a totally brute-force fashion. A "for" loop searches the hash table 32 times starting with the widest possible mask and working down until it hits a match. I assumed I would have to place a cache on top of this to get decent performance. To my delight, however, I discovered that going all the way down to the default entry still took only 6 milliseconds -- on a Taiwanese PC/XT turbo clone! Given the channel speeds involved in the environment I wrote my software for, I didn't consider further optimization to be a high priority task. Sometimes brute force is good enough... Phil
Mills@UDEL.EDU (08/19/87)
Phil, Well, brute force is not enough when there are 270 vanilla IP entries in the table, not to mention subnets, tunnels and crooked passageways. A gateway popping 6 ms per packet (133 packet/s) is probably too slow for any trunkline use. In my experience the depth of search is seldom more than three, one for the martian filter, one for the subnet and one for the net. Tunnels and defaults add another one each, but these are seldom used. With fuzzballs type-of-service adds another level for each TOS combination and an alternate-routing feature (fallback) adds another. With these last the tables get so intricate and delicate that I hesitate to use them outside the lab. This is where we need some clever algorithmic translation between the handy descriptions you and I are using and the actual table structure/cache that drives the routing function. Dave