Multi-Agent Systems for Efficient Quality of Service Routing in Grids

by Eric Ayienga , Bernard Manderick, Okello-Odongo and Ann Nowe

Research carried out in cooperation between University of Nairobi and the Vrije Universiteit Brussel proposes to use multi-agent systems (MAS) for provision of QoS at the network level in a Grid environment. In the proposed architecture, self-interested agents will interact using electronic market-based techniques with the aim of establishing and maintaining a certain level of QoS in the Grid network.

The Computational Grid is a piece of infrastructure formed from a variety of computational resources interconnected by wide area network (WAN) links. The current Internet cannot adequately support Grid services, however, because it is only able to offer ‘best effort’ service with no resource reservation. This type of service is adequate for traditional applications like FTP, Telnet and email but is intolerable for emerging real-time, multimedia and Grid applications (eg Internet telephony, video-conferencing, video on-demand etc), which require high throughput (bandwidth), low latency (delay and jitter) and low packet-loss rate (reliability). This calls for the need to provision Quality-of-Service (QoS). Provisioning of QoS in a network requires its definition and deployment using various mechanisms. Network QoS can be defined as ‘a set of service requirements to be met by a network while transporting a flow’. The requirements can be qualitative or quantitative. Qualitatively, QoS is defined through user perceptions and requirements. Quantitatively QoS is defined through the specification of requirements in terms of constraints on various quantifiable metrics such as bandwidth, delay, delay jitter, reliability and cost. Its deployment is done through admission control, scheduling, routing, flow-control and policing. Attempts to satisfy the service requirements are being made by IETF, IEEE etc, through Bandwidth Overprovisioning, QoS Architectures and Traffic Engineering.

Since ‘best-effort’ will continue to be dominant however, all QoS mechanisms are layered on top of the existing Internet rather than replacing it with a new infrastructure. The reason for this dominance is that the infrastructure already exists, and the routing protocols and algorithms are reliable and stable for the applications it was designed for.

Two of the key issues in supporting these QoS campaigns in communication networks are QoS specification and routing. QoS specification specifies the requirements needed for QoS and quantifies them as accurately as possible. QoS routing on the other hand is concerned with routing traffic such that the QoS requirements of the carried traffic are met. In trying to find the ‘shortest path’ through the network, the current Internet routing protocols (OSPF, RIP, BGP) have two limitations. First, they use single objective optimization algorithms which consider a single arbitrary metric such as hop count or administrative weight during the path selection process. This may lead to congestion on this path while alternate paths with acceptable but non-optimal conditions are relatively free. Second, ‘best-effort’ algorithms tend to shift traffic from one path to a ‘better’ path whenever such a path is found. QoS-based routing should be designed to avoid these problems and in addition should take into account the applications' requirement and the availability of network resources. However, QoS routing poses several challenges that must be addressed to enable the support of advanced services in the Internet, both at intra and inter-domain levels.

Contemporary trends are moving towards the provision of QoS through intelligent resource allocation while routing traffic using machine-learning techniques. This research will approach this challenge through the use of multi-agent systems (MAS). The motivation the use of MAS is that grids are open systems. In these systems, control is distributed, characteristics are not known in advance, and are dynamic and heterogeneous. MAS can address this problem by computing solutions locally based on limited information from isolated parts of the system, and use this information in a social way. Such locality enables agents to respond rapidly to changes in the network state, while their social nature can potentially enable their actions to be coordinated to achieve some wider and socially desirable effect. MAS have been known to solve problems that have the property of inherent distribution (physically and geographically). They also solve problems requiring the interconnection and inter-operation of multiple autonomous, self-interested legacy systems.

In the proposed architecture, agents will interact in the Grid network infrastructure with the aim of establishing and maintaining a certain level of QoS. In allocating resources to implement QoS in Grids, the MAS properties to be exploited include the following:

• Agency: agents act as representatives for other entities with the express purpose of performing specific acts that are seen to be beneficial to the represented entity.
• Autonomy: agents will make autonomous decisions based on their intelligence and social ability.
• Interaction: agents will interact with users, other agents and the environment through coordination (this can be cooperation or competition), communication, and negotiation.

The proposed MAS-based solution will be decentralized and the predominant MAS structure will be the market; in this case the Grid environment in which there will be buyers and sellers of resources. Link agents will be the producers of the resources in this economy. They will wish to maximize the income they get by selling network resources to path agents. Path agents will be the buyers of link resources and sellers of path resources. Negotiations between buyer and seller agents will be based on the market economy and will be modelled using evolutionary game theory. The MAS architecture is as shown in the Figure.

The MAS Architecture.

When a request for a service is made, the Interface Agent will map the service request to the QoS parameters and come up with a quantitative value for the service. This value will be used to derive another quantitative value for the resources. which the Path Agent will use to competitively negotiate for a link with the Link Agents. Upon agreement, the Path Agent will use this link to move to the next node and repeat a similar process. In this way a route with the right QoS parameters for a service request will be formed through the network.

Initially, the system will be modelled through simulation. A simulator representing the current Internet will be built, and the MAS will be built on top of this simulator as an additional layer of control. Challenges include finding suitable paradigms for agent autonomy, multi-agent communication techniques, agent communication platform and language, and the many layers involved that will lead to a high communication and protocol overhead.

Please contact:
Bernard Manderick, Vrije Universiteit Brussel
E-mail: Bernard.Manderickvub.ac.be