2.5 Design techniques for optimizing addressing

2.5 Design techniques for optimizing addressing

This section provides some general guidelines for implementing addressing models and also provides details on specialist techniques in common use in large-scale internetworks today.

2.5.1 General guidelines for addressing models

Addressing models for internetworks play a crucial role in improving efficiency, conserving bandwidth, ensuring scalability, improving general maintenance, and troubleshooting. When devising an addressing scheme there are several basic rules, as follows:

• Legal or private addressing—Based on the size of your network and the extent of communications over public networks, decide whether you want to implement a registered or private addressing model. If using a registered set of class C addresses, ensure that you get a large enough block of contiguous addresses to allow for future expansion. Some ISPs may be short of addresses in contiguous blocks, and you may have to select another ISP. Private addressing is much more flexible, but you must control external interfaces rigorously and install NAT or application gateways in front of any public interfaces.

• Impose structure—Before allocating addresses work out the overall structure of your network design. Focus on the main functional, topological, and geographical boundaries and work out where the key interfaces are. Your model should display a natural hierarchy that mirrors the inherent high-level structure and distribution characteristics of your organization. A structured model will be much more scalable than a flat or random model. If your network is large enough to warrant an ASN and meets the topology constraints imposed by IANA, use registered AS numbers.

• Delegate authority—Wherever possible, delegate authority for address allocation on a regional basis. Providing that the basic ground rules are documented, this will improve your ability to react to changes while maintaining consistency.

• Associate physical features—Allocate blocks of addresses to match this hierarchical model. Addresses should be allocated according to physical location rather than by group function. Groups move, expand, dissolve, and may become distributed, and this will be hard to track.

• Impose meaning and consistency—Try to impose some meaning and consistency into the addresses you allocate. For example, IP subnet 1 through N could be allocated according to floor levels or building numbers on a campus network. HostID 1 could be the default router on each subnet. In mixed-protocol environments it may be appropriate to map different addressing schemes accordingly. For example, in a private address IP network, the IPX network number 2021 could correspond to an IP network number 20.2.1.0. All of these features will greatly improve troubleshooting.

• Maximize efficiency—Optimize the address space allocated to you, using techniques such as variable-length subnet mask, classless inter-domain routing, and route summarization.

• Dynamic configuration—Where possible use dynamic means to allocate addresses and configuration data, preferably via DHCP or BOOTP. Static configurations do not scale.

• Build in security—Consider security as part of the design. On public interfaces try to hide or minimize the exposure of your internal network by using techniques such as NAT and Split DNS.

• Document the model—Any model should be clearly documented and readily available to all interested parties. Failure to do this will lead to inconsistency, duplicate addressing, and potentially serious wastes of time and resources firefighting unnecessary problems.

Often the network designer may be involved in renumbering an existing model, and there are special considerations to be aware of. For the interested reader, references [60, 61] provide a useful insight into this topic.

2.5.2 Network Address Translation (NAT)

Network Address Translation (NAT), defined in [62], was initially proposed as a short-term solution to the problem of IP address exhaustion, since NAT provides an immediate solution for attaching unregistered IP networks to public networks such as the Internet. NAT is also commonly used to secure internal network details from the outside world. NAT operates based on the observation that, typically, only a small proportion of the hosts in a private network are communicating externally. If each host is dynamically and transparently provided with a legal IP address only when external communication takes place, then only a small address pool is required. NAT is commonly used to enable networks that have private or illegal addresses to communicate with Internet services. Without address translation any traffic originating from the private intranet using illegal addresses would at best result in external traffic reaching the desired services but responses being routed to some other location (i.e., the real owner of those addresses, who would doubtless be unhappy to receive such traffic). Three modes of NAT are typically available, as follows:

• Static Address Translation (SAT)—A permanent one-to-one mapping of internal-to-external IP addresses. This may be configured for both incoming (static destination mode) and outgoing (static source mode) traffic. This is typically used for fixed services where you need the addresses to be persistent (such as HTTP or SMTP servers or router addresses). For example, you may need to maintain consistency with external services such as DNS or require fixed addresses for network management status polling. It may also be difficult to troubleshoot key services if their addresses are dynamically assigned. The downside is that you must maintain these static associations.

• Dynamic Address Translation (DAT)—A dynamic one-to-one mapping of internal-to-external IP addresses from a small pool of legal IP addresses. This is the simplest and most common mode for large-scale host address translation, where the addresses do not need to be consistent and low maintenance is required.

• Port Address Translation (PAT)—A dynamic many-to-one mapping of internal addresses to a single external legal IP address. Sometimes referred to as address overloading. Effectively many private addresses are multiplexed onto a single official source IP address using different UDP and TCP port numbers to identify internal hosts. This mode is especially useful if you have a very small pool of public addresses. Generally this mode allows outgoing connections only for security reasons (often referred to as hide mode); this topic is described further in Chapter 5.

Figure 2.15 illustrates the basic concepts of NAT on a public-private edge device. NAT dynamically translates the source IP address of an outgoing packet into an official IP address. For incoming packets destined for the private network it does the reverse, translating the official IP destination address into the corresponding private IP address before it can be forwarded. Clearly, this is a stateful process requiring the NAT module to establish and maintain data structures for flows. A timeout value is typically configured to enable NAT to free up IP associations so that addresses in the pool can be reused. The default idle timer is typically about 15 minutes. Connection-oriented protocols usually indicate very clearly when a session is about to be terminated (e.g., TCP uses the FIN bit in a three-way exchange to close a session). This knowledge can be used to preempt the timer and free up the address immediately if required. For statically mapped addresses NAT must be preconfigured by the administrator. Clearly, statically assigned NAT addresses must not overlap with addresses in the dynamic address pool. In Figure 2.15, we see that incoming packets on either interface may be matched against a rule base to see if they should be NATed. Typically, we NAT on packets traveling from the internal (private) network to the public network. If a source IP address requires NATing, then it may either be allocated statically (from a list of hard-coded addresses) or dynamically (from a small pool of legal addresses). Dynamic allocation may provide a unique IP address per source address or a single IP address using multiple ports to differentiate sessions.

Figure 2.15: NAT concepts.

Typically a NAT device is run at edge devices or as part of the ISP's router or firewall configuration on the customer's premises. The NAT addresses assigned at the WAN interfaces need to be officially registered addresses (described in section 2.1.5) if used for any external public or Internet access. If using NAT on a multiport router or firewall router, then NAT should be configured to comply with normal routing operations (i.e., the NAT IP addresses configured for different interfaces should appear to be from separate networks or subnets).

NAT issues

NAT is not always protocol transparent and must, therefore, be regarded as a useful tool rather than a panacea. Usually only TCP and UDP packets are translated by NAT. SNMP and the ICMP protocol (which runs over IP) may not be fully supported (check with your equipment vendor). In the latter case, if ICMP is not supported, then pinging a NATed address will not work, which can impair troubleshooting. NAT operations with applications such as multimedia, H.323, NetBIOS, DNS, SQLNET, and those that offer dynamic port negotiation are achievable but much more difficult. Address translation means that applications that use embedded IP addresses may not operate correctly; if these addresses are internal (i.e., unregistered), then they must also be NATed or the application may simply not work. For example:

• ICMP messages often contain embedded IP addresses within their payloads.

• DNS queries may return addresses or send addresses within their pay-loads.

• FTP interactions may use an ASCII-encoded IP address as part of the PORT command.

• A public Web page may unfortunately specify hyperlinks as local IP addresses instead of DNS names. Since these addresses are advertised publicly but will not have been translated, any attempt to follow a link will lead to an entirely different device (i.e., the real owner of the public registered address). A final point is that, in general, if there are multiple NATs operating in a network, their translation mechanisms should be synchronized, or at least carefully configured, to avoid potential ambiguities.

Performance issues

As we have discussed, NAT performs address translation on the fly. This is a reasonable amount of work in itself, but a NAT device has more work to do, and you need to be aware of this for performance reasons, including the following:

• Checksum fixes—When NAT translates an IP address, the IP checksum is invalidated and must be recalculated (fortunately the checksum algorithm is a trivial one's complement integer addition of the IP header content, but this must be done per packet).

• Embedded addresses—For some applications there may be even more work to do; HTTP, FTP, and NetBIOS can pass important addresses in payload fields. For example, the FTP PORT command contains an IP address in ASCII format. This level of translation requires more work but is still relatively straightforward. Some protocols are harder or impossible to work with.

• IP fragmentation—This can cause latency problems if fragments need to be reassembled before NATing. For example, if the protocol uses embedded addressing (as described above), then reassembly may be necessary so that the data space can be examined.

As a result, NAT often introduces a significant performance hit on the host system, dependent upon the number of concurrent sessions and the volume of traffic. On edge devices this is offset by the speed of the WAN link; the slower the WAN interface, the less problematic this will be. On high-speed WAN interfaces (such as multimegabit ATM interfaces) or devices such as firewalls (which can concentrate thousands of concurrent sessions over multiple wide area feeds), NAT may become a real bottleneck. For this reason some sites may wrap CPU-intensive devices such as firewalls inside wire-speed switching equipment, where the NAT is performed on the switches themselves. Some NAT implementations may also be configured to provide simple session-based load distribution.

Security issues

One concern with NAT is that host addresses are hidden outside the local domain. While this is often desirable for security reasons (NAT is often supported on firewalls for this very reason, as described in Chapter 5), it also presents a problem for network management and diagnostic processes. Reference [61] suggests the possibility of developing a NAT MIB that could be queried by SNMP to find the active local-to-global address mappings. While this seems a viable approach, it also raises the issue of secure access to the MIB via a trusted SNMP application. Since SNMP is still largely deployed in an untrusted mode, this requires widespread adoption of secure forms of SNMP.

2.5.3 Subnetting

In section 2.1.2 we introduced the concepts of natural network masks. As we saw in section 2.1.5, one of the main problems with natural masks is that they are not granular enough, and this has led to serious inefficiencies in the allocation of IP addresses, since the vast majority of networks are not populated according to byte boundaries. Subnetting is a method of locally extending the natural mask by using bits from the hostID space contiguously (noncontiguous masks are possible but not recommended, since they can lead to some nasty debugging challenges). By moving the boundary that separates the hostID from the netID, effectively expanding the netID, multiple additional networks can be created from a single IP address, with a reduced number of hosts on each subnetwork. The designer can trade off how many hosts and networks are required on a per-site basis. The new subnet mask can be represented in dotted-decimal notation in much the same way as an IP address is represented:

• <netID><subnetID><hostID>

Tables 2.4 and 2.5 illustrate the range of contiguous mask configurations for a class B and class C address, respectively. For example, if you were to subnet a class B network by stealing 4 bits from the hostID space, then the mask would be 255.255.240.0, providing 2⁴ - 1 networks (i.e., 15) and 2¹² - 2 hosts (i.e., 4,094). There is nothing to stop you from extending the mask over multiple bytes—for example, class A addresses could be subnetted using a /24 prefix, but this is usually not necessary

Table 2.4: IP class B subnet configuration. Subnet addresses that are OK to use are indicated in the final column. Addresses that have been excluded are either subnet broadcasts or host broadcast/my addresses.

Bits Used		Mask (binary)				Mask (Decimal)	Prefix	Created		OK
Subnet	Host							Subnets	Hosts
0	16	11111111	11111111	00000000	00000000	255.255.000.000	16	0	65,534	✕
1	15	11111111	11111111	10000000	00000000	255.255.128.000	17	1	32,766	ü
2	14	11111111	11111111	11000000	00000000	255.255.192.000	18	3	16,382	ü
3	13	11111111	11111111	11100000	00000000	255.255.224.000	19	7	8,190	ü
4	12	11111111	11111111	11110000	00000000	255.255.240.000	20	15	4,094	ü
5	11	11111111	11111111	11111000	00000000	255.255.248.000	21	31	2,046	ü
6	10	11111111	11111111	11111100	00000000	255.255.252.000	22	63	1,022	ü
7	9	11111111	11111111	11111110	00000000	255.255.254.000	23	127	510	ü
8	8	11111111	11111111	11111111	00000000	255.255.255.000	24	255	254	ü
9	7	11111111	11111111	11111111	10000000	255.255.255.128	25	511	126	ü
10	6	11111111	11111111	11111111	11000000	255.255.255.192	26	1,023	62	ü
11	5	11111111	11111111	11111111	11100000	255.255.255.224	27	2,047	30	ü
12	4	11111111	11111111	11111111	11110000	255.255.255.240	28	4,095	14	ü
13	3	11111111	11111111	11111111	11111000	255.255.255.243	29	8,191	6	ü
14	2	11111111	11111111	11111111	11111100	255.255.255.252	30	16,383	2	ü
15	1	11111111	11111111	11111111	11111110	255.255.255.254	31	32,767	0	✕
16	0	11111111	11111111	11111111	11111111	255.255.255.255	32	65,535	0	✕

Table 2.5: IP class C subnet configuration. Subnet addresses that are OK to use are indicated in the final column. Addresses that have been excluded are either subnet broadcasts or host broadcast/my addresses.

Bits Used		Mask (binary)				Mask (Decimal)	Prefix	Created		OK
Subnet	Host							Subnets	Hosts
0	8	11111111	11111111	11111111	00000000	255.255.255.000	24	0	254	✕
1	7	11111111	11111111	11111111	10000000	255.255.255.128	25	1	126	ü
2	6	11111111	11111111	11111111	11000000	255.255.255.192	26	3	62	ü
3	5	11111111	11111111	11111111	11100000	255.255.255.224	27	7	30	ü
4	4	11111111	11111111	11111111	11110000	255.255.255.240	28	15	14	ü
5	3	11111111	11111111	11111111	11111000	255.255.255.248	29	31	6	ü
6	2	11111111	11111111	11111111	11111100	255.255.255.252	30	63	2	ü
7	1	11111111	11111111	11111111	11111110	255.255.255.254	31	127	0	✕
8	0	11111111	11111111	11111111	11111111	255.255.255.255	32	255	0	✕

There are effectively two types of subnetting in common use today. They are essentially variations on the same theme, as follows:

• Bit-wise (static) subnets—where all subnets in the subnetted network use the same subnet mask. This is simple to implement and easy to maintain, but it implies some wasted address space for small networks, since the mask must match the largest requirement for subnets. For example, if we subnet a class B address to accommodate several regional groups within the organization and one of those groups requires 12 subnets, then our extended bit mask must be at least 4 bits long, even though some groups may require only one or two subnets.

• Variable-Length Subnet Masks (VLSM)—where the network is comprised of subnets that use different length subnet masks. Given the example just described, we could vary the length of the subnet mask according to the specific requirements of individual groups, and this is a much more efficient way of allocating address space. A well-thought-out design can accommodate localized expansion of the address space with minimum disruption to other parts of the network. Not all hosts and routers support variable-length subnetting.

Since VLSM is essentially a refinement of static subnetting, both schemes can be used together. Hosts that support only static subnetting do not prevent variable-length subnetting from being used, as long as the routers (and routing protocols) between subnets support VLSM. Such routers recognize subnet masks and route packets based on the most specific mask. On subnetted networks, where older end systems do not understand subnet masks, some routers provide support for proxy ARP (described in section 2.2.1). When deploying VLSM, it is important that you do not allow address spaces created by using different subnet masks to overlap. This would eventually result in duplicate addresses on the network as the network expands and these overlapping addresses get allocated multiple times.

Example 1: Subnetted class C

Assume we have a class C address, 193.168.54.0, natural mask 255.255.255.0. Assume also that we want to subnet this address to partition the network into at least four subnets, making the most efficient use of the address space. So how many bits do we need to provide four subnets? To answer this first consider how many bits we have to play with. Since the class C mask is already 24 bits long, we only have 8 bits remaining, and clearly with only 254 host addresses we need to be as economical as possible. So how many bits are required to give us four permutations? Clearly, one bit will only give us two possible subnetworks: 0 and 1. Not enough. Two bits will give us four possible subnetworks: 00, 01, 10, 2. So should two bits be enough? However, we cannot use all 1s, since these must be reserved for subnet broadcasts, and some older networks may also require all 0s to be reserved (as described in section 2.1.3). So to be safe we must use at least 3 bits, giving us eight possible subnetworks, of which at least one is unavailable. So our subnet mask should be 255.255.255.224 (binary 2222.2222.2100000.00000000), leaving us with 5 host bits (2⁵ - 2 = 30 hosts) per subnet. The following chart illustrates this concept.

Binary	Decimal	Note
21	224	Subnet broadcast
20	192	Subnet 6
101	160	Subnet 5
100	128	Subnet 4
02	96	Subnet 3
010	64	Subnet 2
001	32	Subnet 1
000	0	Subnet 0—possibly old-style subnet broadcast

Note that routers that support Classless InterDomain Routing (CIDR) can make full use of all the 0s and 1s subnet addresses in this example. With CIDR there is no natural mask to consider and, therefore, no concept of subnets, so all bits in the network space are treated as a contiguous network address. CIDR is covered in section 2.5.4.

Example 2: Subnetted class B

Assume that the IP address of a workstation is 140.21.32.2. With a natural mask this would equate to network address 140.21 and host address 32.12. If, however, we subnet this class B network address by extending the natural mask by 5 bits (i.e., a prefix of /21 and a mask of 255.255.248.0), this gives us 31 new subnetworks plus the reserved address, 248, for subnet broadcasts. Since we have 2 bits left for the hostID, this gives us 2² - 2 = 2,046 host addresses per subnet.

Example 3: VLSM with class B

Assume we have a class B address, 130.50.0.0, and an organization with seven functional workgroups as illustrated in Figure 2.16. This is typical of many large organizations. Let us assume that this network was installed several years ago, and addresses were allocated in a linear fashion; over time this scheme has become almost random, since several reconfigurations have left the network effectively at the mercy of the users. At the present time the network is bridged—effectively a single IP domain. If we analyze the makeup of each functional group, we find that these groups are logically separated into smaller workgroups (typically teams within a functional group). The approximate number of hosts per work group is listed in the following chart.

Figure 2.16: A single class B network with 7 functional work groups.

Clearly, if our address allocation is linear/random and a natural class B mask is used, then there is no way to segment the traffic (at Layer 3) on this network without a major reconfiguration.

Functional Group	Workgroups	Hosts/Workgroup	Total Hosts
Finance	2	100	200
Human Resources	1	50	50
Manufacturing	2	800	1,600
Engineering	4	1,000	4,000
Marketing	2	200	400
Sales	3	90	270
TOTAL	14		6,520

Our first option is to impose some hierarchy on the network using static subnet masks. To provide up to 14 subnets we will need at least a 4-bit subnet mask—hence, 255.255.240.0. This would give us up to 4,094 hosts per subnet. This concept is illustrated in the following chart.

Functional Group	Subnet	Bits	Address
Finance	1	0001	16
	2	0010	32
Human Resources	3	002	48
Manufacturing	4	0100	64
	5	0101	80
Engineering	6	020	96
	7	021	22
	8	1000	128
	9	1001	144
Marketing	10	1010	160
	11	102	176
Sales	12	200	192
	13	201	208
	14	210	224
Broadcast	15	22	240

If we planned, for example, to install routers in this network at a later date, then we could still configure this addressing scheme now, but leave the natural network mask (255.255.0.0) in place. Once routers are installed, we could change the mask to 255.255.240.0 to enable routing between subnets. Furthermore, all of these networks can be summarized externally as one class B network if the natural mask is propagated over the external links.

This works fine, but we can already see that there are large disparities in the relative size and subnet requirements of these groups, and clearly a static mask is going to be very wasteful, especially if the network grows substantially in the future. What we need, ideally, is a more flexible way of handing out address space. We, therefore, examine the possibilities with Variable-Length Subnet Masks (VLSM). Let us assume that the network has expanded and we are now faced with the requirements shown in the following chart.

Functional Group	Workgroups	Hosts/Group	Total Hosts
Finance	2	200	400
Human Resources	1	150	150
Manufacturing	3	2,000	6,000
Engineering	5	2,500	12,500
Marketing	18	60	1,200
Sales	25	80	2,400
TOTAL	54		22,650

If we applied our static mask here, we would need at least a 6-bit mask (255.255.252.0) to provide 54 subnetworks. This would be grossly inefficient. What we need is a way of handling some of the larger subnets, such as engineering and manufacturing, as well as the smaller subnet populations, such as human resources and sales. Our largest subnet requirement is 25, requiring at least a 4-bit mask. Apart from marketing and sales, all other functional groups require less than 15 subnetworks. If we are to allow for future expansion, we could at the very least apply two separate masks according to size. For those groups requiring less than 15 subnets we can use a 4-bit mask (255.255.240.0), and for those networks requiring 15 or more subnets we could apply an 8-bit mask (255.255.255.0). This concept is illustrated in the following chart.

Functional Group Finance	Mask	Bits	Address
Finance	4	0001xxxx	130.50.16.0
		0010xxxx	130.50.32
Human Resources	4	002xxxx	130.50.48
Manufacturing	4	0100xxxx	130.50.64
		0101xxxx	130.50.80
		020xxxx	130.50.96
Engineering	4	021xxxx	130.50.22
		1000xxxx	130.50.128
		1001xxxx	130.50.144
		1010xxxx	130.50.160
		102xxxx	130.50.160
Marketing	8	2000001	130.50.192.1 to 130.50.192.18 (18)
		||
		2010010
Sales	8	201002	130.50.192.19 to 130.50.192.43 (25)
		||
		210102

Note that this allocation scheme is not contiguous, nor is it depleted. There is an unused gap between marketing and sales to allow for expansion either way.

2.5.4 Supernetting or Classless InterDomain Routing (CIDR)

In section 2.1.5 we covered the issue of IP address space depletion. IPv6 will overcome this problem in time, but what can be done in the interim? One idea was to use a range of class C addresses instead of a single class B address. The problem there is that each network must be routed separately, because standard IP routing understands only classes A, B, and C network addresses (see Chapter 3). Within each of these types of network, subnetting (i.e., using a subnet mask larger than the natural network mask) can be used to provide better granularity of the address space within each network, but there is no way to specify that multiple class C networks are actually related. The result of this is referred to as the routing table explosion problem: A class B network of 3,000 hosts requires one routing table entry at each backbone router, whereas the same network, if addressed as a range of class C networks, would require 16 entries.

The solution to this problem is a scheme called Classless InterDomain Routing (CIDR). CIDR, also called supernetting, is described in [41, 63, 64]. Supernetting works by relaxing the normal rules of IP addressing, so that the IP address prefix can be shorter than the natural mask length (hence, the term classless). For example, the class C address 196.20.136.0 can be represented as a supernet using the format 196.20.0.0/16. This represents all networks starting with the prefix 196.20.

Supernetting is a powerful technique, which can be used to group contiguous blocks of routes together for route summarization. This process is more formally called aggregation. For example, to summarize a block of eight class C addresses with a single routing entry, the following representation would suffice: 196.20.136.0/21 (i.e., a mask of 255.255.248.0). This single routing entry would, from a backbone point of view, summarize the address block from 196.20.136.0 to 196.20.143.0 as a single network, as illustrated in the following code segment:

 2000100 00010100 10001000 00000000 = 196.20.136.0 // Class C address 2222 2222 221XXX XXXXXXXX  255.255.248.0 // Supernet mask ----------------------------------  logical_AND 2000100 00010100 10001XXX XXXXXXXX = 196.20.136  // IP prefix 2000100 00010100 100022 00000000 = 196.20.143.0  // Class C address 2222 2222 221XXX XXXXXXXX 255.255.248.0  // Supernet mask -----------------------------------  logical_AND 2000100 00010100 10001XXX XXXXXXXX = 196.20.136  // Same IP prefix 

The current Internet address allocation policies and guidelines for CIDR are described in [63]. They are summarized as follows:

• IP address assignment reflects the physical topology of the network and not the organizational topology; wherever organizational and administrative boundaries do not match the network topology, they should not be used for the assignment of IP addresses. In general, network topology will closely follow continental and national boundaries and, therefore, IP addresses should be assigned on this basis.

• There will be a relatively small group of networks that carry a large amount of traffic between routing domains and that will be interconnected in a nonhierarchical manner across national boundaries. These are referred to as Transit Routing Domains (TRDs). Each TRD will have a unique IP prefix. TRDs will not be organized in a hierarchical manner where there is no appropriate hierarchy. However, wherever a TRD is wholly within a continental boundary, its IP prefix should be an extension of the continental IP prefix.

• There will be many organizations that have attachments to other organizations that are for the private use of those two organizations and that do not carry traffic intended for other domains (transit traffic). Such private connections do not have a significant effect on the routing topology and can be ignored.

• Most routing domains will be single-homed (i.e., they will be attached to a single TRD). They should be assigned addresses that begin with that TRD's IP prefix. All of the addresses for all single-homed domains attached to a TRD can, therefore, be summarized into a single routing table entry for all domains outside that TRD. This implies that if an organization changes its Internet service provider, it should change all of its IP addresses. This is not the current practice, but the widespread implementation of CIDR is likely to make it much more common.

• There are a number of address assignment schemes that can be used for multi-homed domains, including the following:

  • The use of a single IP prefix for the domain. External routers must have an entry for the organization that lies partly or wholly outside the normal hierarchy. Where a domain is multihomed but all of the attached TRDs are topologically nearby, it would be appropriate for the domain's IP prefix to include those bits common to all of the attached TRDs. For example, if all of the TRDs were wholly within the United States, an IP prefix implying an exclusively North American domain would be appropriate.

  • The use of one IP prefix for each attached TRD, with hosts in the domain having IP addresses containing the IP prefix of the most appropriate TRD. The organization appears to be a set of routing domains.

  • Assigning an IP prefix from one of the attached TRDs. This TRD becomes a default TRD for the domain, but other domains can explicitly route by one of the alternative TRDs.

  • The use of IP prefixes to refer to sets of multihomed domains having the TRD attachments. For example, there may be an IP prefix to refer to single-homed domains attached to network A, one to refer to single-homed domains attached to network B, and one to refer to dual-homed domains attached to networks A and B.

• Each of these has various advantages, disadvantages, and side effects. For example, the first approach tends to result in inbound traffic entering the target domain closer to the sending host than the second approach, and, therefore a larger proportion of the network costs are incurred by the receiving organization.

Because multihomed domains can vary significantly in character and none of the above schemes is suitable for all such domains, there is no single policy that is best; reference [63] does not specify any rules for choosing between them.

CIDR implementation

The implementation of CIDR in the Internet is primarily based on the BGPv4 protocol (see Chapter 3). The implementation strategy, described in [64] involves a staged process through the routing hierarchy beginning with backbone routers. Service providers are divided into four types, as follows:

• Type 1—Those that cannot employ any default interdomain routing.

• Type 2—Those that use default interdomain routing but require explicit routes for a substantial proportion of the assigned IP network numbers.

• Type 3—Those that use default interdomain routing supplemented with a small number of explicit routes.

• Type 4—Those that perform all interdomain routing using only default routes. The CIDR implementation involves an implementation beginning with the Type 1 network providers, then the Type 2, and finally the Type 3 providers. CIDR has already been widely deployed in the backbone, and over 9,000 class-based routes have been replaced by approximately 2,000 CIDR-based routes.

2.5.5 Hierarchical addressing and route summarization

An important technique, which optimizes routing resources and routing performance, is hierarchical addressing. This technique is available only to routing protocols that have the ability to support hierarchical models such as OSPF and IS-IS (described in Chapter 3). Hierarchical routing is a valuable technique used in building large networks. As networks grow their use of finite routing resources, such as memory, CPU, and bandwidth grow, and, therefore, a more efficient design will reduce the overall resource deterioration. In Chapter 3 we see that in flat routed designs (i.e., not flat in the sense of bridged networks) the OSPF routing table grows linearly with the number of IP segments O(n), but with hierarchical routing we can slow the growth to a logarithmic rate, O(log[n]). Clearly this is a major improvement.

Hierarchical routing partitions the internetwork by segmenting the network recursively into manageable chunks, each grouped by address and subnet mask to form a tree-like structure. At the very lowest level we are using flat routing within the partition, but in this case the routers require only minimal knowledge of other partitions in the network; they just need to know how to get there. Consider the network models illustrated in Figures 2.17 and 2.18. Here we have a simple three-layer hierarchy, with nine level 1 partitions, three level 2 partitions, and one level 3 partition. We start with a class A network, 12.0.0.0, using a classic 8-bit mask. We then subdivide the network into three partition—12.1.0.0, 12.2.0.0, 12.3.0.0—mask 255.255.0.0, and then further subdivide these partitions as shown.

Figure 2.17: Three-layer hierarchical routing scheme—bird's-eye view.

Figure 2.18: Three-layer hierarchical routing scheme—tree view.

When routers need to forward to destinations outside their immediate partitions, they rely on higher-level routing to complete the task. This approach significantly reduces routing table size. For example, suppose we have 25 segments in every level 1 partition, and we examine a router in the 12.1.1.0/24 partition, as follows:

• If flat routing is implemented, the routing table will have 9 × 25 = 225 entries.

• If we use a hierarchical scheme, each level 1 router will have only 25 + 4 = 29 entries (25 local level 1 entries, plus two level 2 entries, 12.1.2.0/16, 12.1.3.0/16, plus two level 3 entries, 12.2.0.0/8, 12.3.0.0/8).

Clearly, we can see the benefit in table size (87 percent), but this will also mean that convergence is speeded up, since the routing algorithm has to scan less routing entries when building its forwarding tables. The Internet employs a hierarchical routing hierarchy for these very reasons. However, there are some disadvantages, in that suboptimal paths may be chosen in a hierarchical scheme, resulting in longer paths than would be achieved with flat routing. Note that the preceding example illustrates the simplest form of route summarization, where subnet routes are collapsed into a single network route. Routing protocols that support VLSMs may support route summarization at any bit boundary (rather than just by natural mask). Some routing protocols summarize automatically; others may require manual configuration. Further information on this subject can be found in Chapter 3, where its association with specific routing protocols is covered in depth.