Telephony Routing over IP (TRIP) is a policy-driven inter-domain routing protocol that is used to advertise information about the reachability of telephony destinations along with other associated information.What makes this protocol particularly useful is that it is independent of the signaling protocol used (i.e., H.323, SIP). TRIP has been modeled after the Border Gateway Protocol (BGP). However, it has also been enhanced with characteristics of the Open Shortest Path First (OSPF) and the Server Cache Synchronization Protocol. In this project, the existing TRIP Parser has been used to design a full implementation of the protocol, complete with storage of routing tables, Decision Manager for route selection, route advertisment, configuration of local policy data,and interfaces allowing protocol to be used in within a proxy.

The implementation of the TRIP protocol closely follows the guidelines laid out in RFC 3219. It demonstrates how LSs learn information from one another and use that information to select the best route(s) to a destination.

When an Location Server (LS) starts up, it looks to its governing Provision Server (PS) for local policy data. This data is configurable by the network operator. It retrieves the following data:

As soon as the LS reads all its policy data, it attempts to connect to all of its peers by sending an OPEN message to them telling them that it is interested in opening a connection. If the connection is acceptable, a peering session is established during which the following messages are exchanged: KEEPALIVE (to maintain the connection), UPDATE (containing routing information, and NOTIFICATION (in the event of an error). In addition, the LS continually listens on port 6069 for any incoming messages. Any local routes specified are injected at start-up time.

Routing information is stored in one of the four routing tables of the TRIB database- Adj-TRIB-In, Adj-TRIB-Ext, Loc-TRIB, and Adj-TRIB-Out. The Decision Process uses the Best Route Selection algorithm to select the best routes to a destination. This algorithm is based on Dijkstra's algorithm, similar to the one BGP uses. As routing information is received at an LS, a preference value is assigned for any external routes. The preference value serves as one of deciding factors in the process. LSs within an ITAD have synchronized information.

Route advertisement to external peers is accomplished by aggregating routes in the Loc-TRIB table and filling up the Adj-TRIB-Out table with these routes. Then the Adj-TRIB-Out table of each external peer is examined to see what routes have been updated, and a list of UPDATE messages is created out of them. This list is then sent to the external peer.

Details about the enhancements made to the TRIP Parser completing the implementation of the protocol can be found here.

The IP Telephony Group (IPTEL) of the Internet Engineering Task Force (IETF) initially wanted to have a protocol that simply distributed gateway information between gateway providers and IP telephony providers, but a global directory for such information proved to be much too grand . The problem is that a telephone call that enters an IP network, destined for a PSTN, might be governed by the policies of numerous policies of the parties who own the networks through which it traverses. A scheme was developed so that such information can be exchanged and databases of reachable telephone numbers could be created and stored locally by the providers.

An Internet Telephony Administrative Domain (ITAD) to TRIP is what an Autonomous System (AS) is to BGP. Routing information is propagated in a similar manner. A TRIP speaker is called a Location Server (LS). LSs that belong to the same provider form an ITAD. TRIP has the functionalities to route between and within ITADs. It is responsible for keeping routing information within a single ITAD synchronized.

TRIP LSs propagate the following information to one another: reachability of telephony destinations, routes towards these destinations, and information about gateways towards those telephony destinations residing in the PSTN. When one LS connects to another, what is known as a Peering Session has been established, and routing tables are exchanged. The LSs are called Internal-Peers if they reside within the same ITAD, External-Peers otherwise.

There are four different messages by which the TRIP protocol communicates: OPEN, KEEPALIVE, NOTIFICATION, and UPDATE. OPEN messages are first exchanged when a peer connection is established, and if that is successful, then KEEPALIVE messages are periodically exchanged to ensure that peers are functioning. NOTIFICATION messages are used to let peers know that some sort of an error has occurred. UPDATE messages are used to transfer routing information between LSs. They are important because they help construct the connectivity graphs of the ITADs.

A TRIP LS receives 3 types of routes from different sources:

Once received, the routes are stored in the Telephony Routing Information Base (TRIB) which exists in each LS. This database has the following components:

Route selection algorithms are run on the routes of the Adj-TRIB-In and Adj-Trib-Ext of the internal LS of an ITAD.

Route selection and route advertisements work in the following manner. An UPDATE message is received when the protocol is in the Established state. Once it is placed in the appropriate Adj-TRIBs-In, depending on what type of route it is, the LS might run its Decision Process, depending on what is already in the table. After that, information must get flooded to all other internal peers based on mechanisms similar to that of OSPF and Server Cache Synchronization Protocol(SCSP).

The Decision Process selects routes for advertisement by applying local policies in its Policy Information Base (PIB). In fact, an order of preference for a given route is calculated based on the attributes of a given route. The Decision Process operates on the Adj-TRIBs-In table and works in three phases:

This program is a complete implementation of the TRIP routing protocol. It has been coded in C++. The two primary modules of this program are the TRIP Core and the LS Functionality. The TRIP Core implements the structure of the four messages exchanged through TRIP: OPEN, KEEPALIVE, UPDATE, and NOTIFICATION, along with utilities to create, parse, and transport these messages. The LS Functionality handles connections between LS peers as well as exchange and storage of routing information. The different states that comprise the TRIP Finite State Machine are implemented in this module. The LSServer module contains an implementation of an LS which can be started in order to exchange routing information with other LSs in the system. The other two components of the program are the Utilities module and the Tools module which aid the parsing and transport of connections. Here, the architecture of the TRIP Core and LS Functionality is described in more detail.

The TRIP Core defines the structure of the OPEN, KEEPALIVE, UPDATE, and NOTIFICATION messages in TRIP. There is a class supporting the format of each type of message. Each message has a header telling you what type of message is being sent, and the length of the message (in octets). The fields contained by the message differ according to type. The TRIP Core also contains the network interface to send and receive those messages, as well as parsing-related classes for the encoding and decoding of messages. Below is an outline of the architecture of the classes that make up the TRIP Core.

The classes listed below are involved in the implementation of the four different messages exchanges through the TRIP protocol:

These classes help send and receive messages through the TRIP network:

TRIPTranceiver
The main class involved in this process. The TRIPTranceiver class is used to send and receive these messages over the network. It uses the TRIPMsgParser class to parse incoming messages. It also uses the TRIPUtil class to read data from and write data to a network connection.

Other classes in this module are involved in the various attributes of the four messages.

TRIPUtil
This has utility functions for reading/writing data to/from a network connection.

Other supporting classes include:

TRIPData
Holds binary data for any TRIP Core class of variable length.

TRIPBadDataException
This is used for exceptions when there are any errors in the formats of any one of the four messages.

The LSFunctionality uses the classes of the TRIP Core for its operations. It is in charge of three thing: the handling of connections between peers, the storage of the routing tables, and route advertisement and selection. It also contains an interface by which to read PolicyData. Most of the classes in this module are singleton classes meant to ascertain the state of the LS during the routing. The following decribes the architecture of the LS Functionality.

ProvisionInterface
Serves as an interface through which an LS can read local policy data as configured by its Provision Server (PS). It is a singleton class which parses the configuration files containing the policy data and contains accessor method to retrieve that data. It provides the LSSessionManager with an array of information such as the ITAD value, the port number, values to use for the various timers involved in the routing process, peers, local routes to inject, LSs to discard in the routing process, the local preference and metric values among other things.

LSSessionManager
The LSSessionManager is able to read the local policy data provided by the LS’s Provision Server. In addition, any local routes that are read are injected in this class, as soon as the server socket is created to listen for incoming routing data. The LSSessionManager can be thought of as the driver for the program. In it, the LS tries to connect to all of the LSs in the system to see from where it may get routing data. It also listens for any incoming OPEN messages and starts peering sessions with other LSs. It can be run both as a thread within a proxy or a standalone application.

LSPeerSession This class specifically implements the peer session. It too, runs as a thread. An LSPeersession drives the FSM for a connection. There are three types of peer sessions to consider as implemented by these classes, depending on the capabilities of the LS, i.e., whether or not UPDATE messages can be sent/received:

LSTopology
Represents the inter-domain connectivity graph handled by the LSTopology class. Each LS is identified by its TRIPId, and a list of its associated peer sessions is also stored. There are functionalities to add and remove connections, and other LSs in the ITAD are notified of any changes that occur in this graph.

This next set of classes are used to store the routing tables:

TRIBAgent
Manages the four routing tables of TRIP: Adj-TRIB-In, Adj-TRIB-Ext, Loc-TRIB, and Adj-TRIB-Out.

TRIPTrieCache
Implements the actual structure of the routing tables as a Trie Tree structure. A Trie Tree allows for quick access to routes, as they are arranged by an alphabetical key. The Trie tree allows for two orders:

TRIPTrieElement
Represents an single node in the TRIPTrieCache, containing the value of the route.

TRIPTrieUtil
Has conversion tools for integers and characters.

TRIPRouteElement
The route itself is contained by an object of this type. In it, information such as a route’s destination, next hop, sequence number, and transaction ID are all stored.

TRIPWorkSet
Holds a selected group of routes from a routing table for processing. Each route in a set is associated with an Address Family-Protocol combination.

TRIPProtoKey
Embodies the Address Family-Protocol combination.

These classes are involved in the Decision Process:

DecisionProxyAgent
This is a singleton class which is run as a thread within the application. As Update messages arrive at an LS, they are placed into a FIFO as Update Events that need to be processed. It then calls either the DecisionAgent or the IncomingPolicyAgent to process the route.

TRIPUpdateEvent
Encapsulated an UPDATE message as an event, storing it with the associated set of routes and TRIPItadKey.

IncomingPolicyAgent
Places all new routing data extracted from an UPDATE message into the appropriate Adj-TRIB-In table according to the TRIPItadKey associated with the UPDATE message. If the route is said to be withdrawn, it sets it as so. The IncomingPolicyAgent also assigns routes received from external ITADs preference values to be used in the Best Route Selection algorithm.

DecisionAgent
The DecisionAgent updates the the Ext-TRIB and Loc-TRIB tables as the Adj-TRIB-In table changes and as the Best Route Selection algorithm is performed. The Best Route Selection algorithm is performed in this class itself. When external routes are processed, then both the External-TRIB and Loc-TRIB tables are processed, whereas when internal routes are processed, only the Loc-TRIB table is processed.

These classes are used to advertise routing information:

OutgoingPolicyAgent
Manages the route advertisement process. It aggregates routes in the Loc-TRIB and then populates the data in the Adj-TRIB-Out table for each external table with those routes for each external peer. Local policy data also affects how the Adj-TRIB-Out is populated.

OutgoingPolicyTimerAgent
Serves as a timer for the OutgoingPolicyAgent.

Advertiser
Takes care of advertising routes to all external LSs. The advertisement process is carried out by processing the Adj-TRIB-Out of each external peer and creating a list of UPDATE messages from all of the updated routes in that table and sending it to the respective peer.

Aggregator
Aggregates routes in the Loc-TRIB table.

These two classes are involved in the implementation of the Finite State Machine of TRIP:

TRIPState
This class has the implementation for an FSM describing the current state of the connection owned by the associated LSPeerSession. Each state (Unkown, Idle, Connect, Active, OpenSent, OpenConfirm, and Established) is derived from this class.

TRIPDef
Defines constant values and types for use in the LSFunctions module of the program.

TRIP can be utilised within a proxy server with the use of the following:

LSApiServer
This is to be as an interface through which incoming client requests can be listened for when TRIP is being used to route from within some sort of proxy server.

LSRouteInterface
Serves as a client interface through which an LS can make requests for routing data when TRIP is used within another proxy server.

Several tests were conducted to ensure that the protocol was working properly. For example, to see how information was exchanged by LS peers, the program was run on different test topologies. And the integration of policy data was watched for during the runs of the program. Here are some screenshots of how the program runs:

An OPEN message being sent by an LS.

An UPDATE message is being sent. This UPDATE has to do with a local route being injected.

The topology formation.

Print outs of the TRIB tables.