next up previous contents index
Next: Compilation Configuration Process Up: Developer's Guide Previous: Developer's Guide


Among other things, Gated is a portable routing protocol development platform, that factors out (and separately provides) functionality common to most protocol implementations. This functional factorization has three important advantages: 1) it simplifies the task of a routing protocol implementor, 2) when two or more routing protocols instances (i.e. participants in routing information interchange) are run on the same router, it enables harmonious sharing of computation and memory resources, and 3) it isolates the machine dependent part of protocol implementations to enable portability.

In the abstract, Gated models the operation of a human-configurable router as comprising (in the steady state) of the following primitive operations (in some order): receive protocol messages from neighbor routing entities, perform route computations, update one's own forwarding information base (FIB), and send protocol messages to neighbors.

Based on this model, we can factor out the following general mechanisms required, to varying degrees, by all routing protocol implementations:

Some of these mechanisms are provided by classical operating systems (such as UNIX). However, the underlying operating system's mechanisms can be inefficient for routing protocol implementations.

For this reason, Gated implements its own, highly optimized versions of these mechanisms. Gated, in its role as a routing daemon for BSD-based systems, was also built to run more than one protocol instance in a single box; using GateD's common substrate, these protocol instances could be made to share processor and memory resources more effectively.

Following is an overview of each of these mechanisms.

Mechanisms for Scheduling Protocol Computations

A single Gated daemon may run multiple routing protocol instances. It must be able to fairly allocate computational resources to these different routing protocol instances (e.g. a BGP instance and an OSPF instance). To this end, Gated provides support for tasks, timers, and jobs.

A task, is the thread of execution of a sequence of related primitive operations (such as reading a message, processing the message). These related operations can be scheduled independently of (i.e. arbitrarily interleaved with) the operation of other protocol instances or other operations within the same protocol instance.

Different protocol implementations use tasks differently. The simplest way to use tasks is to allocate a single task to all computation that happens within a protocol. Some, like BGP which maintains a transport connection to each individual peer, assign a task to protocol activity associated with the peer .

GateD's timer abstraction allows protocol instances to express periodic or time-delayed computations. An example of such a computation is the monitoring of the state of a peer connection, or sending keep-alive messages in BGP.

GateD's job abstraction allows a protocol instance to schedule some computation for some convenient time in the future. The OSPF implementation, for instance, schedules an SPF computation using jobs.

Memory Management Mechanisms

Gated uses the underlying operating system's memory allocator for its memory needs. However, it uses its own, highly space-optimized, allocator for descriptor blocks (e.g. the task state block, other protocol control blocks and so on).

Communication Mechanisms

For routing protocol message transport (unreliable datagram, or reliable byte-stream connections), protocol implementations almost always use the underlying operating system interface. Some earlier protocol implementations used GateD's interface to unreliable datagram transport.

To simplify protocol implementations, Gated provides abstract data types for physical interfaces, and routing neighbor gateways. These data types encapsulate information about these physical entities commonly used by different protocols.

Route Storage Mechanisms

Another common function of routing protocol implementations is the storage and processing of routes, and updating the router's forwarding information base. Gated provides a central routing database, in which protocol instances running on the same router store their reachability information. The module providing this functionality also directly updates the kernel's routing table.

Gated's AS Path Module for efficient storage and processing of BGP AS paths can also be included here. This module provides an easily processable representation for BGP aspaths.

Configuration Mechanisms

Finally, Gated provides abstract data types that encapsulate configuration information common to most protocol implementations. These abstract data types encapsulate such things as autonomous system numbers that the entity is running in, policy specifications and so forth.

next up previous contents index
Next: Compilation Configuration Process Up: Developer's Guide Previous: Developer's Guide

Laurent Joncheray
Wed Jun 12 15:35:22 EDT 1996