7   Liberouter

Recent experiences indicate CESNET can play a very useful coordination role in research projects with many participating institutions beside CESNET. This model has been successful especially for complex projects like DataGrid (see Chapter) or in the last two years Liberouter. An effective and targeted cooperation of diverse research organisations seems to be a general problem, evidence of which is for example the effort invested by the EU into support for "Networks of Excellence" in the 6th Framework Programme. CESNET can serve in such cases as a needed neutral platform, assume overall responsibility for the research results and, last but not least, provide such distributed teams with all facilities that are necessary for a successful cooperation - videoconferencing equipment, Web portals and other services.

The basic aim of the Liberouter project is to develop a PC-based IPv6 and IPv4 router. At present approximately 50 persons collaborate on this project, about half of that number being students of five universities (MU and VUT in Brno, ČVUT and VŠE in Prague and ZČU in Plzeň).

The Liberouter should provide the following benefits beyond a software-only PC router:

  1. Higher throughput in the range of 5-10 Gbps, i.e., roughly ten times the throughput of a PC with standard hardware.
  2. Uniform configuration interface comparable to commercial routers.

The first goal is addressed by a hardware accelerator based on the technology of Field-Programmable Gate Arrays (FPGA). In the case of the second goal we decided to pursue a more general solution and create a generic configuration system, which could be used for all common router platforms and also for an effective configuration of entire networks.

The results of the project are publicly available including source code. We use appropriate open-source licenses for different parts of the project, namely:

We were also involved in the preparation of CESNET licensing policies and directives for intellectual property protection.

7.1   Hardware accelerator

The architecture of the hardware accelerator as described in the last year's report [Gru03] remains valid. Its leading idea is the so-called hardware-software co-design, which tries to find an optimum division of functions between hardware and software. In the case of an IP router such a division is quite straightforward:

An important principle allowing us to reuse most of the existing software is a full integration of the specialised hardware into the operating system environment. In other words, the operating system deals with our hardware accelerator in exactly the same way as if it was a common multiport Ethernet card.

We started the year 2003 already with the first prototype of the main board named COMBO6. During January and February the board had been activated and tested. We discovered two minor design flaws that do not affect card's functions but do not allow to achieve the planned performance. We nevertheless decided to manufacture four additional cards using the same design, which have been used by our developers. Then in the second half of 2003 we designed a new corrected revision of the card.

The COMBO6 card is itself not equipped by any communication interfaces. These are supposed to be added by means of an add-on daughter interface card. Two such cards were designed and manufactured in 2003:

  1. COMBO-4MTX with four metallic ports of Gigabit Ethernet, see Figure.
  2. COMBO-4SFP with four ports of Gigabit Ethernet in the form of SFP cages. SFP GBIC adapters are available for a variety of media (single- and multi-mode fibre, CWDM and even metallic). See Figure.
[Figure]

Figure 7.1: COMBO-4MTX card

[Figure]

Figure 7.2: COMBO-4SFP card

Figure shows the resulting "sandwich", where COMBO6 is connected with the COMBO-4SFP interface card through special connectors.

[Figure]

Figure 7.3: COMBO-4SFP card attached to COMBO6

A card with two ports of 10GE is also being designed. However, we face certain difficulties due to a limited availability of 10GE chipsets. The first 10GE card, to be finished during the first quarter of 2004, therefore internally splits the clean 10GE channel into four channels, each with 1 Gbps. For the next spin we will then either use a suitable 10GE chipset, if it is available by then, or implement all necessary functions ourselves in the FPGA.

For a more detailed description of the hardware design see the paper [NAF03] and technical reports 12/2003 and 13/2003.

7.2   Firmware

The most difficult development task, unfinished so far, is undoubtedly the firmware, i.e., special programs for the gate array that handle packet reception from an input network interface, processing the header data, decision about the appropriate action and, finally sending it to the right interface.

[Figure]

Figure 7.4: Block diagram of the COMBO6 firmware

Figure shows an overall diagram of the firmware, which consists of the following blocks:

HFE (Header Field Extractor)
The task of this module is to extract all necessary information from the link and network layer headers (L2 and L3 status registers, source and destination MAC and IP addresses, source and destination port, VLAN tag etc.) and store them in a structure called Unified Header (UH). It is 596 bits long and contains the data items at fixed offsets.
DRAM (Dynamic Random Access Memory)
During header processing the entire packet waits in the dynamic memory of the COMBO6 card. The other modules deal only with its DRAM address and only at the end of the process the OPE module picks the packet contents from the DRAM and assembles the outgoing packet.
LUP (Look-up Processor)
The most complex module, which has to decide about the fate of every single packet, in the first place whether it should be forwarded at all, and if so, how it has to be modified and what are the proper outgoing interfaces. One can imagine the look-up process as a search tree that reads, step by step, the fields in the Unified Header and according to their contents decides about further actions. Our LUP implementation addresses this problem in two phases: First one is a fast search in the associative memory (CAM), which can cover at most one half of the UH bits though and, moreover, is not suitable for an effective matching of ranges (e.g., port ranges). The remaining UH bits are thus handled by an algorithm that is implemented directly in the FPGA. The design of the LUP module is described in [ICN04].
REP (Replicator)
This module replicates packets as necessary, or rather just pointers to packets. This is useful primarily for multicast but also for supporting functions like tcpdump.
QUE (Output Queue)
A packet that is ready for sending is inserted into one of the output queues. In the current firmware version, the set of these queues is managed in the mode of priority queues.
OPE (Output Packet Editor)
The task of OPE is to reassemble the entire packet and modify the header data according to both the requirements of a particular communication protocol (for example the TTL field in the IPv4 header) and the instructions issued by the LUP module.

Most of the firmware modules described above are present in four instances - one for each input or output port. The number of output queues (QUE) is configurable in the firmware design.

Figure also suggests that all modules can communicate with the PCI bus. This data path is used e.g., for the handling of exceptions that cannot be processed in the hardware (yet).

All modules mentioned above are now under simultaneous development. The developers also already started the tedious process of integration of the entire firmware design and its placement in the gate array.

7.2.1   Methods and tools of firmware development

Programs for the gate arrays are being developed in the VHDL language (Very High Speed Integrated Circuits Hardware Description Language). The firmware developers have access to a professional VHDL development environment consisting of the programs Leonardo Spectrum, FPGA Advantage, HDL Designer and Modelsim. In some ways, however, these programs do not support the style of work of a distributed team:

  1. The default user interface is graphical, which makes the shared and/or remote access difficult and also does not allow the development tasks and sequences to be effectively automated and documented.
  2. Open source development relies to a large extent on contributions from independent volunteers that help with debugging and in some cases also with the development proper. As long as there is no free development kit, a real VHDL programming and debugging is available only to those with access to the expensive professional environment.

Solving the first issue turned out to be quite easy, thanks to the fact that all development steps from the VHDL source code to the microcode of a particular chip are performed by programs with a command line interface anyway. We thus created an alternative development environment that is based on the traditional make command. The development cycle can now be fully controlled from a line terminal and, moreover, the Makefiles help document the individual compilation procedures and make them repeatable.

The ultimate solution to the problem of opening the VHDL development to a wider community - a free development environment - is not in sight and so we resorted to a partial solution, namely adding another abstraction layer to the firmware design, so-called nanoprocessors. These are processors implemented inside the FPGA with a very small but highly specialised instruction set. Hence, the firmware modules described above are implemented in two stages: First a nanoprocessor is designed and then a "nanoprogram" is written for it using the nanoprocessor's instruction set. Whereas the first stage (implementation of a nanoprocessor) required the full-fledged VHDL development kit, nanoprograms can be written or modified relatively easily.

A direct interaction with the machine code is not really enjoyable even for nanoprocessors and so we tried to create a more comfortable development environment enabling the use of assembler-like language for nanoprocessor programming. Filip Höfer solved this issue very elegantly in his Bc. thesis [Hof03]. The resulting program nsim is a generic compiler, simulator and debugger for any nanoprocessor - the instruction set and semantics is passed to the nsim program by means of a simple declarative language. The only missing link in the nanoprocessor development tool chain is a disassembler, but it is now also being developed.

[Figure]

Figure 7.5: Screenshot of the xnsim program

In order to be able to perform combined simulations of several nanoprocessors, and also for presentation purposes, we created a graphical front-end to nsim named xnsim, see Figure. This program is able to simulate and visualise individual steps of data processing in the COMBO6 firmware. The upper part of the window displays the firmware modules and dynamical exchange of information between them, while the lower parts shows the nanoprocessor instructions being executed and their output. The simulation operates on a sequence of packets that are given to the xnsim program as input in the tcpdump format.

7.3   System software

Communication between the COMBO6 card and the host operating system has two main forms:

  1. COMBO6 card together with a daughter interface card works as a plain multiport Ethernet adapter.
  2. For some purposes (firmware download, debugging) special mechanisms are needed.

We are developing software support for both forms of communication under NetBSD and Linux operating systems.

The first form of communication is enabled by a thin layer of drivers and other system software that hides the peculiarities of the COMBO6 card. Consequently, configuration, administration and monitoring of network interfaces can be accomplished by the usual operating system commands like ifconfig, tcpdump etc.

The look-up processor (LUP), which is an important part of the COMBO6 firmware, manages its own data structures that govern packet classification and the decision about the fate of each packet. These structures must nevertheless reflect analogical information that is present in the operating system kernel, especially in the routing and filtering tables. For a correct function of the hardware forwarding accelerator, the LUP data must agree with those in the kernel. This synchronisation is taken care of by the combod daemon, which is notified about the changes in the kernel tables, e.g., through the netlink socket.

A direct access to the COMBO6 and interface cards is enabled by a low-level driver and realised through two character device files /dev/combosix0 and /dev/combosix1. We have developed utilities for the initialisation of both cards and firmware download. Another interesting program is comboctl, which allows the developers to easily perform simple operations like reading and writing from/to specific registers or memory location, and even write simple scripts in the TCL language.

7.4   Formal verification

Formal verification methods, which are also known in the domain of software programming, are needed even more for proving correctness of hardware designs, since errors discovered only after a design has been realised tend to be rather expensive. However, famous flaws in products of even the biggest companies (like the Pentium processor by Intel) indicate that a complete formal verification of designs of very complex components is still just a dream.

The Liberouter project also involves students from a group of formal verification at the Faculty of Informatics MU in Brno. Our aim is to apply the formal verification approaches to smaller hardware and firmware modules, but also use the methodology for imposing some discipline on the programmers, for instance by requiring them to intersperse their VHDL code with certain logical formulas (assertions).

The method we use for formal verification is so-called model checking that attempts to prove the correctness of a specification of the given system on a certain level of abstraction that is determined by a system's model. The validity of the specification is verified by going through the entire state space of possible inputs and comparing their corresponding output against the specification. If they do not match, one immediately obtains a counterexample.

Automated formal verification is done using the program NuSMV, which uses a special SMV language for model description. Our formal verification group also developed a set of scripts for transforming VHDL programs into SMV.

Formal verification was applied, for example, to a simplified model of the look-up processor for proving that the CAM and SRAM memories are correctly shared by all four channels. This application and other experiences are described in the technical report 17/2003.

7.5   Netopeer configuration system

One of the most distinguishing features of commercial routers compared to their PC-based counterparts is the way in which these devices are configured and administered. Router vendors like Cisco Systems or Juniper Networks offer for these purposes very comfortable and consistent command line interface, which covers configuration and monitoring of all hardware and software subsystems. In contrast, PC/Unix router configuration typically boils down to editing diverse configuration files and init scripts.

The goal of the Netopeer software is to create both a configuration interface comparable to commercial routers and a platform-independent system for managing configurations of routers and entire networks. The basic idea, and a hard problem at the same time, is to define a neutral configuration format from which and into which platform-specific configurations can be translated. We have chosen XML as the language for the neutral configuration format, primarily because its tree structure is a good match for the structure of typical configuration data, and also because a number of well-established tools for XML processing are available.

Configurations expressed in XML are stored in the configuration repository, which, beside other functions, also supports version control. Software modules that interface with the user are called front-ends; their main role is to take a configuration expressed in a user-friendly way and transform it into the XML form. We are working on both batch front-ends that do only this transformation and interactive ones that also aid the user with preparing the configuration and store it into the repository. On the other side, the interface between the Netopeer system and concrete routers is a realm of so-called back-ends. They handle the reverse transformation from XML into the platform-specific configuration language, and may also handle other tasks like installing and activating the configuration in the target router.

As most of the functions are common to several (or all) front- and back-ends, we decided to implement them in the form of two specialised libraries:

Figure shows the relations of back-ends and both types of front-ends to these libraries.

[Figure]

Figure 7.6: Utilisation of Netopeer libraries by front- and back-ends

In the following subsections we will describe the current status of individual software components.

7.5.1   XML schema of the configuration data

Significant part of a typical router configuration can usually be translated from one router configuration language into another. Nevertheless, configurations of certain subsystems (e.g., packet and route filters that are not covered by any IETF standards) are often vendor- or even model-specific and thus hard to translate between configuration languages. Hence, defining an universal and neutral configuration language compatible with at least the most popular router platforms seems to be next to impossible. We thus decided to provide, in an otherwise generic XML schema, a possibility for verbatim sections of platform-specific configuration commands.

Nonetheless, a full coverage of the "convertible" subset is still far from straightforward. In order to enable the development of the Netopeer modules, we decided to define an interim XML schema covering network interface configuration (including tunnels and VLANs), static routing, RIP and RIPng routing protocols, and finally packet and route filters. This schema is described in the technical report 2/2003.

7.5.2   XML tools

We originally intended to base our XML subsystem on the Xerces parser (C++ version), which by then seemed to have the best support for W3C XML standards. However, our practical experiences were not satisfactory: Xerces is a rather bloated and slow piece of software with annoying deficiencies (for example in error handling) and incomplete documentation. Fortunately, during the year 2003 another XML library - libxml2 - reached a reasonable level of maturity. In contrast to Xerces, libxml2 is fast, modular and well-documented. For these reasons we migrated our XML library to libxml2. The current version of the Netopeer-XML library is described in the technical report 22/2003.

7.5.3   Repository

The most popular system for version control, CVS, which is otherwise used by all members of the Liberouter team for their development work, is not really appropriate as a foundation of the Netopeer repository. From our point of view, the most serious drawback of CVS is the absence of an application programming interface. This turned out to be a problem for several reasons, for instance error handling is very tricky and fragile. We thus adopted another versioning system, Subversion, which is comparable to CVS in terms of functionality but also provides a decent API. On top of Subversion we built a specific Netopeer repository library. Its installation and API is documented in the technical report 21/2003.

7.5.4   Front-ends and back-ends

At present, all front- and back-ends that are either finished or under development work with the above-mentioned interim XML schema. Completely finished is the batch front-end for Cisco IOS. A similar front-end for JUNOS is also functional but not fully conformant to the interim schema yet. Interactive front-ends are still being developed.

On the back-end side we have two functioning modules, both based on XSL transformations: one for Cisco IOS and another for Linux.

Contrary to our original plan, we decided to stop the development of a SNMP front- and back-end. As it turned out, in the configuration area SNMP is relatively useless and does not cover all necessary parts of router configuration.

7.5.5   Metaconfiguration

An interesting application, which will cooperate with Netopeer in the future, is the so-called metaconfiguration. It should allow to configure entire networks on a higher level of abstraction and assist during the network design process as some kind of an expert system. Metaconfiguration will also support templates that may be reused many times with varying parameters. The network design and parametrisation will be described again in XML, but using its own schema (i.e., not the one of Netopeer). From this description, configurations of individual routers will be generated automatically, but this time already according to the Netopeer schema.

Metaconfiguration is the topic of the PhD. thesis of Miroslav Matuška, and currently it is in the stage of architectural design.

7.6   Testing

A systematic and independent testing of all hardware and software components is considered an important part of the Liberouter project. In 2003 we set up two test laboratories (in Prague at FEL ČVUT and in Brno at ÚVT MU) and furnished them with the necessary equipment - apart from PCs we also purchased a powerful network analyser, Spirent AX4000.

The testing team elaborated a methodology for IPv6 router conformance testing based on the TAHI Conformance Suite and also evaluated available software tools for router performance testing. The results are summarised in the technical report 18/2003.

7.7   Project management, publications and presentations

The number of people directly participating on the Liberouter project is currently around 50, half of it being students. The task of coordinating such a large team, difficult by itself, is further complicated by the distributed character of the team. In 2003 we introduced a management hierarchy with delegated competences. The following workgroups have been formed:

  1. VHDL - 17 members, leader Jan Kořenek (VUT Brno)
  2. System software - 11 members, leader David Antoš (MU Brno)
  3. Formal verification - 5 members, leader David Šafránek (MU Brno)
  4. Testing - 4 members, leader David Rohleder (MU Brno)
  5. Netopeer - 10 members, leader Ladislav Lhotka (CESNET)

The main instruments for team coordination have been

Various technologies and services support team collaboration. Apart from videoconferences and mailing lists we have been successfully using the version control system CVS, where the team members are required to store all their results and documentation. The contents of the CVS repository are open to the public.

Another much-needed service is a bug and request tracking system, for example Bugzilla. The test operation is already underway and we plan to deploy it in February 2004.

The main project web server is www.liberouter.org. It also serves as a portal for accessing other information sources (CVS via a web interface, archives and administrative pages of the mailing lists etc.). The large extent of hardware and software development also means a lot of diverse documentation, that could be immediately presented on the web and discussed both within and outside the project team. Despite considerable efforts and extensive tests of systems for contents management (e.g., Plone), we have not arrived at a satisfactory solution yet.

We presented our results at three international conferences (TNC 2003 in Zagreb, FPL 2003 in Lisbon, ICETA 2003 in Košice). Five additional papers were presented at national conferences. An entire session at XIIIth EurOpen conference at Strážnice was devoted to Liberouter. We also contributed to the success of the seminar IPv6 - development and implementation organised by CESNET on October 22, 2003. Liberouter team members authored or co-authored 11 CESNET technical reports in 2003.

In the area of presentation we also cooperated with a designer on a project logo. The result is shown in Figure. Consequently, we also ordered and purchased T-shirts, glasses and cups with this logo.

[Figure]

Figure 7.7: Liberouter project logo

7.8   Conclusions

Although the Liberouter project has not been finished yet, some of its preliminary results - in particular the COMBO6 card - were already used in other projects, for example SCAMPI (see Chapter) and CzechLight (Chapter), and more applications are expected to be included in forthcoming projects of the EU 6th Framework Programme, GN2 in the first place.

The Liberouter project clearly documents the opportunity for CESNET to act as a coordinator of large-scale research and development projects involving universities and institutes of the Academy of Sciences as partners. As a matter of fact, such a platform is often hard to find otherwise.

Beside the visible results, the Liberouter project has had a number of other positive side-effects, especially in the area of human resources. The students involved benefit greatly from their participation: apart from the technological know-how they also learn how to cooperate in such a diverse team and how to present their results. So far, two Bc. and three M.A. theses stemmed from the project and all got excellent marks. Jan Kořenek's M.A. thesis was nominated for the Prize of the Minister of Education.

previous
contents 		next
metacentrum elearning liberouter live shows videoserver eduroam