Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Subnet Modeling Approach For Creating Synthetic Routing Tables

IP.com Disclosure Number: IPCOM000010648D
Original Publication Date: 2003-Jan-02
Included in the Prior Art Database: 2003-Jan-02
Document File: 6 page(s) / 56K

Publishing Venue

IBM

Abstract

The routing table is a key feature in the testing of packet forwarding engines like routers. The primary motivation of a performance test is to impact the complete routing table by packets. Conventional packet generators have hardware limitations, which prevent generation of a large number of distinct packets to hit all the entries in the routing table. To overcome this limitation, an address increment feature available in all conventional traffic generators is used. To complement this feature, the routing table needs to be recreated with all the key characteristics preserved. This article describes an algorithm for generating a synthetic routing table from a real world routing table. The algorithm models subnets from the routing table and attempts to mimic the prefix length and class distribution characteristics of the real world routing table.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 32% of the total text.

Page 1 of 6

Subnet Modeling Approach For Creating Synthetic Routing Tables

     Disclosed is an algorithm which outlines a procedure for creating Synthetic Routing Tables (SRT) and setting up traffic generators to generate packets to impact all the routes in the SRT. The SRT is created from a snap-shot of a Real World Routing Table (RWRT) and mirrors the key properties of the RWRT.

     The routing table is a key feature in the testing of packet forwarding engines like routers. The primary motivation has been to use a real-world routing table (RWRT) to evaluate the performance under real world conditions. During performance evaluation, the router is loaded with such a routing table and its ports are connected to sources of traffic, typically traffic generators. The traffic generators generates traffic to hit the IP routes in the routing table in the router under test. It is desired that the traffic generated by the traffic generators hit all the routes in the routing table. Traffic generators setup streams of traffic on each port and each stream impacts one route in the routing table. Multiple packets from the same stream are identical. To impact the whole routing table, the number of streams required would be same as the number of routes. But, due to hardware limitations, only a small number of streams are permitted which prevents the set up from impacting all the routes in the routing table.

     Typically, traffic generators have an address increment feature which allow the increment of the network or host portions of IP destination addresses in each stream. So, for every packet generated by a particular stream, the network or host portion of its IP address is incremented. If an IP address is represented as x1.x2.x3.x4, then by setting up 256 streams with x1.0.0.0 (x1=0..255) as initial IP address and continuously incrementing x2, x3 and x4, it is possible to cover the whole IP address space. So, by incrementing the network or host portions of IP addresses it is possible to use all the routes in the routing table. But a RWRT does not have a contiguous route space (referred to as 'gaps') causing a lot of packets to be dropped due to the lack of routes. So, to ensure that the gaps are closed without impacting the performance of the router, an SRT, which has a contiguous route space, is created. The synthetic routing table essentially mimics the original RWRT in certain key attributes viz. prefix length distribution, class distribution and subnet size distribution.. An SRT combined with the incremental address feature allows all routes to be hit.

The benefits of this approach are outlined below:
1. The key attributes of the real world routing table are captured by subnet modeling.
2. The number of streams required to hit all the routes cannot be greater than 256.
3. This approach is good for benchmark tests as identical traffic is guaranteed for all the devices under test.
4. Flexibility to increase or decrease the size of the routing table.
5. Degree of closene...