ActionScripting in Flash MX

3.7 Router architecture

This section reviews some of the basic operations and design choices applicable to modern routers. These have a fundamental impact upon price, performance, and the features available from today's commercial router platforms, and, as many engineers recognize, these design choices can significantly influence the network design. Note that here we are primarily interested in packet switching; for an overview of circuit-switching architectures refer to [11].

3.7.1 Router operations

The range of features supported by routers has mushroomed over the last decade, incorporating features such as multiprotocol operations, bridging, and basic firewalling. This is partly because of the drive for tighter integration and also because routers traditionally sit at key boundaries in the network infrastructure. Apart from specialized backbone routers optimized for packet forwarding, routers are becoming almost general-purpose forwarding devices, likely to be involved in the following operations:

Clearly, some of these operations are extremely complex and resource intensive, and for high-performance routing applications (such as enterprise and backbone nodes) it is important that the architecture of these devices is highly optimized for high-speed forwarding.

3.7.2 Router applications

Routers can be loosely classified into three classes, broadly divided by application: backbone routers, enterprise routers, and access routers. Each class of router is designed to deal with a different set of challenges and is, therefore, broadly differentiated based on factors such as performance, software functionality, port density, media support, and price.

Backbone routers

Backbone routers are used on public networks such as the Internet, telco networks, and large private internetworks. The primary issues here are, therefore, reliability and performance. Backbone routers enable organizations to build large, private international internetworks over high-bandwidth, long-haul trunks. They also enable ISPs and telcos to connect enterprise networks over public networks such as the Internet. The key characteristics of a backbone router are summarized as follows:

In the gigabit range there are products such as the M40 (Juniper) and Cisco 7500. Notably, the M40 supports in-service software upgrades (the ability to upgrade the router code online without bringing down the router). At the top end of this class of routers are the so-called carrier class terabit router platforms, for which there are only a small handful of competing vendors (the term carrier class implies extremely high levels of fault tolerance and compliance with the Network Equipment Building Specification [NEBS], a Bellcore originated de facto standard for carrier class equipment). Products in this class include the NX64000 (Lucent), TSR (Avici Systems), Aranea Terabit Router-1 (Charlotte's Web Networks), Pluris 2000 Series TNR (Pluris), Versalar 25000 (Nortel), and the Cisco 12016.

Enterprise routers

Enterprise routers are typically employed within a campus or enterprise network. In this environment there may be thousands of LAN users interfacing with a wide diversity of interfaces. The key characteristics of an enterprise router are summarized as follows:

The job of designing an enterprise router is not easy; it must resolve the conflicting design goals of providing a rich feature set at each port, reducing the cost per port, and ensuring ease of configuration, QoS support, and strong management and diagnostic features. Examples of routers in this class include the Cisco AGS+ and 7000 series and the Xyplex 9000 Series.

Access routers

Access routers allow home users and small businesses to access the Internet via an Internet Service Provider (ISP). They are also used in remote offices for central-office connectivity. In the past, access networks began life as modem pools attached to terminal concentrators, serving a large number of low-speed dial-up circuits. In recent years this model has changed dramatically with the emergence of high-speed modems, ISDN, xDSL, and cable modems. ADSL is about to add an extra magnitude of affordable bandwidth into the SOHO environment, and this will increase the load on access routers yet further. The key characteristics of an access router are summarized as follows:

Examples of routers in this class include the Cisco IGS and 2500 series, the AN range (Bay Networks), and Xyplex 3000 series.

Reducing port costs

Both enterprise and access routers are subject to very tight cost constraints, and stiff competition means there is always pressure to minimize the price per port. This ratio depends on factors such as memory size and type, interface logic, processing architecture, and the complexity of the protocol used between the port and the routing processor. Cost reduction is a serious consideration for all components on these platforms, and a constant concern for designers. Considerations include the following:

For the interested reader [12] provides an excellent review of this subject.

3.7.3 Router architecture and design

A router is essentially a specialized network computing device optimized for packet switching and as such typically contains CPU, ROM, RAM, some form of bus, possibly flash media, and NVRAM. In order to implement high-speed routing, the architecture of a generic router embodies several key components: a routing processor, switching fabric, and interface cards providing one or more input ports and output ports. While this may seem of academic interest to the casual observer, hard-bitten routing engineers understand all too well the implications of router architecture on performance and scalability in real networks. In the routing world, performance is often critical, especially as we go up the food chain into the backbone domain. The performance characteristics of a router become very exposed when CPU-intensive features such as quality of service are required on top of basic packet forwarding.

Packet switch evolution

We can broadly divide packet switches into three generations, as follows:

We will now briefly review the key components of router architecture and their potential impact on features and performance.

Routing processor

The routing processor participates in routing protocols and creates a forwarding table that is used in packet forwarding. The routing processor also runs the software used to configure and manage the router. It handles any packet whose destination address cannot be found in the forwarding table in the line card. Route processing can be implemented in several configurations, including the following:

The architecture employed depends on a number of factors—the class of router, level of fault tolerance required, hardware specification, price, and the following:

Another factor in these design options is whether the routing database itself is centralized, distributed but shared, or fragmented (distributed among routing processors, each with their own routing database). For backbone and large enterprise routers handling many interfaces it is advantageous to have a centralized or closely coupled distributed routing database; however, this requires either substantial horsepower and resources or a highly sophisticated multiprocessor architecture. Some mid-range enterprise and access routers employ a collapsed routing architecture, where each route processor acts like an independent router inside the chassis, connected over a common medium fabric (often internalized Ethernet, FDDI, or ATM cores). Although some highly flexible designs have been deployed, this may mean that internal routes (i.e., routes between cards in the chassis) appear in the routing table just like external routes, potentially slowing down route lookup.

Interface modules

An interface module (sometime called an IO card or line card) is the physical point of attachment for local and wide area circuits to the router. Interface cards typically support one or more physical ports, depending upon the media type, the amount of logic required on the card, and the size of the connectors. Incoming packets are fed into an input port, and outgoing packets are fed to an output port. Many media technologies operate in full duplex mode, so in some cases the input and output ports may refer to the same physical interface, differentiated only by the direction of traffic flow.

Switching fabric

The switching fabric interconnects input ports with output ports. If the switching fabric has a bandwidth greater than the sum of the bandwidths of the input ports, then packets are queued only at the outputs, and the router is called an output-queued router. Otherwise, queues may build up at the inputs, and the router is called an input-queued router. Fabrics may be physically represented as a traditional backplane (typically one set of large connectors at the back of the chassis) or as a midplane (two opposing sets of connectors in the middle of the chassis). Midplane chassis tend to offer greater flexibility but at the cost of additional complexity. One thing to take special note of is the physical connector presentation. Ideally the backplane/ midplane should present female interfaces, since this has the least potential for damage internally. If this is not the case, you run the risk of having to replace the whole chassis if you inadvertently damage the pins of a male connector.

Bus fabric

The traditional and simplest switching fabric to implement is a bus, which interconnects all the input and output ports. It is relatively easy to build a router today using a personal computer equipped with multiple line cards. The problems with this architecture are that the bus is a single point of failure and throughput is constrained by both the capacity of the bus and the overheads imposed by bus arbitration logic.

Shared-memory fabric

In a shared-memory router incoming packets are stored in a shared memory and only pointers to packets are switched. This increases switching capacity. However, there is an intrinsic performance limitation with shared-memory switch fabrics. The speed of the switch is limited to the speed at which we can access memory. Although memory sizes have roughly doubled every 18 months, memory access times have improved by only about 5 percent annually. Unlike crossbar switches, however, shared-memory switches do not suffer from Head-of-Line (HOL) blocking, and multicasting is relatively straightforward to implement.

Crossbar fabric

The crossbar fabric is the simplest form of switching fabric, comprising an N × N matrix of N input buses, N output buses, and N2 crosspoints (this can be visualized as 2N buses). A crossbar radically improves performance by enabling multiple simultaneous data paths to operate through one or more switching fabrics and is at best case N times faster than a second-generation switch.

On the downside, the control status of each crosspoint must be under continuous control for every flow of packets transferred in parallel across the crossbar fabric, and this requires a scheduler. Therefore, with the crossbar architecture, although much improved, the scheduler ultimately constrains performance through the fabric. Furthermore, although a crossbar is internally nonblocking, if multiple packets at the input port want to go to the same destination then output blocking occurs. This can be resolved by either running the crossbar N times faster than the input ports (difficult and expensive) or by placing buffers inside the crossbar. Crossbars do not scale well. Multicasting is complex in a crossbar switch and requires the switch to fabric to be quiet during the period of the multicast.

Hybrid media fabrics

During the mid-1990s some innovative designs emerged that used pseudo-media buses inside the chassis. Some of these devices also implemented a kind of symmetric multiprocessing (promoted by BAY Networks and Xyplex). Some of these implementations were closer to real symmetric multiprocessing than others. For example, Xyplex implemented a highly flexible midplane (as opposed to backplane) architecture in their 9000 series, using three internal Ethernet buses. This design is a form of multiprocessing; however, each route processor operates like a discrete router, even to the point of exchanging routing protocol over the internal media buses. A number of IO ports are dedicated to each processor, and ports can be soft-switched internally or externally, enabling a high degree of flexibility in the design.

This design offers an impressive number of topology options and appears to offer scalability and good fault tolerance. Scalability is limited only by the speed of the internal bus, and individual slots could run different processors to match different types of applications. Each slot is autonomous; in the event of a route processor failing, only the IO ports connected to that slot are affected. Hot swapping is available. Managed load-sharing power supplies are available. The disadvantages are that this is an expensive architecture to implement. Each slot has its own OS and routing processor and requires large amounts of RAM as we move into the backbone domain. Another disadvantage is that routing is taking place internally (e.g., OSPF peering across internal buses) and route entries for internal networks appear in the routing tables.

ATM-like fabrics

In the early 1990s designers began to tackle large ATM switch architectures. Although ATM did not dominate the networking world as predicted, designers of IP routers saw an opportunity to improve throughput and offer (conceptually) mixed-media services by wrapping segmentation and reassembly modules around ATM-like switching fabric cores. With this architecture ATM PVCs are mapped between all ports in the router (i.e., a fullmesh ATM backbone in a box). During the forwarding process, a longest-prefix match determines the destination port for an IP packet. The packet is then fragmented into 53-byte ATM cells and switched over the appropriate PVC to the output port, where it is reassembled back into an IP packet before transmission. From the IP perspective the ATM core could be viewed as a transparent fat pipe; however, this architecture does not allow the possibility of providing different service guarantees, and these designs suffer some of the inherent problems of ATM, including the following.

Despite these issues, ATM fabrics have appeared in many recent router designs. For further information, the interested reader is referred to [11, 12, 14] for more details of switch design and buffering techniques.

Issues in switch design

Buffering

One of the hardest problems in switch design today is not the fabric design but the buffering component. In short, there are three main buffering techniques, as follows:

For further information on buffering techniques, the interested reader is referred to [14]. For details on performance improvements, and arbitration algorithm design in relation to input queuing, see [15, 16].

Route lookup

Perhaps the single most important performance issue for backbone routers is route lookup time. The operation is based on the most specific (longest) IP prefix. This would be an O(N) operation per packet just to build a set of candidates and is completely unacceptable. This issue is amplified if small packets represent a high proportion of the traffic, since this ultimately means more lookups per second. The two main factors that affect the speed of a route lookup algorithm are memory access time and the data structures used to construct the forwarding table. Performance can be improved in a number of ways, including the following:

Instead of reducing the cost of route lookups, backbone routers can use two techniques to avoid route lookups altogether, as follows:

There are clearly a number of useful solutions to the fast route lookup problem, and several of these techniques will no doubt be incorporated into new generations of router designs. An excellent review of router design trends is given in [12].

3.7.4 Scheduling techniques

The simplest method of scheduling packets from a buffer is to release them in the order of arrival, a strategy commonly referred to as first come, first served (FCFS) or first in, first out (FIFO). Many first-generation routers provided a single FIFO as their own scheduling option (perhaps with one additional queue for control and management traffic). With mixed local and wide area routing there can be a much greater imbalance in line speeds, leading to frequent buffer overflows or timeouts if the amount of remote data is too large to be sustained.

Traffic prioritization and queuing mechanisms have become increasingly sophisticated over recent years and are closely associated with service guarantees. In addition to FCFS/FIFO, queuing strategies currently deployed include priority queuing, custom queuing, Weighted Fair Queuing (WFQ), and Random Early Detection (RED).

3.7.5 Router operating systems

Historically, routers have been viewed as hardware devices optimized for high-speed packet forwarding; consequently, the operating systems implemented in these systems were often not much more than stripped-down schedulers. Many router operating systems are derived from early versions of Free BSD UNIX, and there is increasing interest today in LINUX. Both of these environments have access to a huge suite of essentially free routing software developed over many years and publicly available on the Internet. Over the past decade, however, router hardware has become almost a commodity, and the software component of the router has been increasingly viewed as the true value item. Router vendors such as Cisco have differentiated themselves largely on increasingly rich and sophisticated software functionality, ranging from huge tracts of protocol support to exotic queuing systems and bandwidth management features.

Related

Категории