Hungarian and Norwegian researchers developed an internet-based packet forwarding system in order to improve the efficiency and reliability of the operation of the web.

Several projects of the European Union’s 7th Framework Programme for Research and Technological Development (FP7) focus on the present issues and future prospects of the internet. One of them is the Allegra project concluded recently, in which the research team of the Department of Telecommunications and Media Informatics of the Budapest University of Technology and Economics together with their Norwegian partners analysed the challenges related to the continually expanding internet traffic and the available solutions for the upcoming issues.

“Not only sustainability of the environment but sustainability of the world wide web is a problem, which needs urgent attention,” emphasized Mr. András Gulyás, senior lecturer of the Department of Telecommunications and Media Informatics of the Budapest University of Technology and Economics, leader of the research team. “Possibilities of the present internet architecture are limited: the continually growing number of users will sooner or later outgrow the available technology. The developing internet traffic causes more and more problems for the packet forwarding subsystem of the internet, which is becoming increasingly difficult to handle.”

The packet forwarding subsystem manages the packets that are created when for instance e-mails are sent. First the data file of the e-mail is divided into smaller units (packets) and then it enters the network. When these packets are received by our computer it compiles the e-mail again. Each packet contains the addresses of the sender and the receiver and information about the units that are linked together. Loads of packets from different sources use the same channel to get to the receivers; they are managed and directed by computers. All the devices have to know the final destination of the packet received and when there are different routes available the optimal one has to be chosen.

Such decisions are made by special equipment called router, which forwards the packets on the network. “The routers that our research was dealing with were the high-performance devices of professional service providers, which cost over 10 million Forints and are operated in separated, air-conditioned server rooms, so we were not focusing on ordinary wifi routers for home use,” András Gulyás explained.

The route of the packet to be forwarded is selected according to the routing table in the memory of the router, which specifies the route to the different destination servers. The structure and size of the routing table is an important element of the efficiency of the routing process. “The problem is that the number of entries in such devices is growing very quickly,” as the researcher outlines. “Three-four hundred thousand entries can be handled by the present devices but the continuous expansion, special memory units and new hardware solutions make such equipment more and more expensive.”

The new packet forwarding concept of the research team was based on the social networks, where members of the network similarly give information to one another. The original idea was based on the “small world” or “six degrees of separation” experiment of the American social psychologist, Stanley Milgram in 1967, which proved that people can forward a letter to any unknown recipient through five other people on average. “This experiment is impressive and was very useful for us to create our model because people, without knowing the exact map of the social network, were able to guess who they should hand the letter over so that it should get to the recipient,” explained András Gulyás. They way it works can be modelled if we imagine the processes of the mind in an abstract, multidimensional space, in which people are able to categorize their contacts.

These categories are obviously fewer than existing personal contacts therefore when the sender gives some information about the recipient, the intermediary person can guess who of their acquaintances may be closer to the recipient. If for example I am asked to forward a letter to a Chinese fisherman, I may remember that I have a friend who learns Chinese at the university and may have contacts in China, and so on.

Technical terminology describes this phenomenon as greedy decision or greedy routing, which means that within the network we tend to make the locally optimal choice at each stage with the hope of finding a global optimum. It is very similar to geographic routing, which allows finding a solution close to the global optimum. “Its advantage is that the route does not need to be specified in advance but it is determined flexibly during packet forwarding. The disadvantage is that the sender cannot be sure that the routers will select the optimal solution for them,” the researcher added.

The described model of social networks was applied and adapted to the packet forwarding systems by the researchers. The software developed in the frame of the project was tested through the PlanetLab system. “PlanetLab is a worldwide computer network with about 1000 nodes, which is available to researchers for organized research projects; and therefore it is an ideal platform to examine the internet of the future. There we have got the opportunity to test something new, which can be more efficient and reliable in the future,” the researcher summarized.

FP7 Allegra was a small-budget project with two partners involved: the Norwegian University of Science and Technology (NTNU) and the Budapest University of Technology and Economics (BME). Slightly more than half of the 149 thousand Euro grant was received by the Budapest University of Technology and Economics. Own funding was provided partly by the University and partly by the Research and Technology Innovation Fund of the National development Agency. The Grant covered the staff costs of the research team, involving 12 members from the BME.

Allegra project was a part of a larger FP7 programme aiming to create European and world-wide testing systems. “It was a very difficult task because we had to elaborate our idea in a structure that was not determined by ourselves therefore we had to adapt to the environment along with its possibilities and constraints. We needed to share the tasks among the participants very efficiently and at the same time do excellent teamwork,” said András Gulyás.

The department has got several research programmes running that focus on the sustainability of the internet. “Allegra project aims to develop architecture, which can solve problems in the long-term, but we have middle-term, more direct plans as well,” explained András Gulyás. The idea of another project was not to change the existing architecture but make an attempt to “squeeze” the sizes of these routing table entries. This research project has also been very successful: we proved that the size of the table entries can be reduced to a fraction without any significant decrease in the searching speed.”

Closing Allegra project successfully does not mean that no further research is needed. “In a cooperation programme we have the opportunity to make contacts with other researchers and we get insight in one another’s activities. As a result we have started two other programmes that build on our experiences about the routing architectures,” summarized András Gulyás, senior lecturer of the Department of Telecommunications and Media Informatics.

- HA -

Photo: Erik Pintér