Datacab: a geographical‐information‐system‐based expert system for the design of cable networks

Datacab: a geographical-information-system- based expert system for the design of cable networks In ˜ igo Monedero, 1 Carlos Leo ´ n, 1 Robert Denda 2 and Joaquı´n Luque 1 (1) Escuela Te ´cnica Superior de Ingenierı ´a Informa ´tica, Departamento de Tecnologı ´a Electro ´nica, Avda Reina Mercedes s=n, 41012 Sevilla, Spain E-mail: [email protected] (2) Manager of Technology Services, Endesa Ingenierı´a, Edificio Expo, Isla de la Cartuja s=n, 41092 Sevilla, Spain E-mail: [email protected] Abstract: Telecommunication networks have evolved over time as a result of technological advances, and network topologies and equipment have become increasingly complex. Expert systems are being successfully applied to the management of telecommunication networks. However, applying expert systems to network design is another especially beneficial yet still not very common approach. In this paper we propose a rule-based expert system called Datacab. Datacab was developed at Enditel Endesa in collaboration with the Electronic Technology Department of the University of Seville, for the automatic design of hybrid fibre coax (HFC) cable networks. Using data from a geographical information system as input, it automatically generates viable HFC network designs. Keywords: telecommunication networks, expert system, HFC network, GIS 1. Introduction As a result of the great technological evolution that has taken place in telecommunications, it is possible to communicate and access information rapidly, via telephony and communication networks such as the Internet. Telecommunication networks have evolved over time to satisfy the demands of different communication services, continuously requiring greater bandwidth and a better quality of service. Network technology has increased in complexity, generating the need for a better administration of the resources of these systems, which has fostered the evolution of network management systems. On the other hand, research carried out in the field of artificial intelligence has led to important advances in the treatment, storage and exploiting of knowledge. These advances include the field of knowledge-based expert systems (Buchanan & Duda, 1982; Liebowitz, 1998; Ignizio, 1991; Awad, 1996; McGraw & Harbison-Briggs, 2002). Expert systems are being successfully applied to the realization of diverse tasks (interpretation, prediction, diagnosis, design, planning, instruction, control etc.) in multiple fields such as medicine, geology, chemistry and engineering (Liebowitz, 1998). Expert systems may also be applied to the field of telecommunication networks, because many of the previously enumerated tasks require specialized knowledge and are needed for the management and operation of these networks, which can be automated by an expert system. Among these tasks is the one of network design, which in particular requires the knowledge of experts. This paper describes an expert system called Datacab for the automatic design of cable networks. The aim of Datacab is to save time and work during the task of designing a cable network. The paper first gives an introduction to the state of the art of expert systems applied to telecommunication networks; second, the hybrid fibre coax (HFC) network structure to which Datacab has been applied is presented, and lastly, the structure and design of Datacab as well as a base case and experimental results are described. 2. Applications of expert systems to telecommunication networks Figure 1 schematically shows the different application domains of expert systems related to telecommunication networks (Liebowitz, 1988; ITU-T, 1991). The efficiency of the tasks of operation and maintenance of current telecommunication networks largely depends on the degree of cooperation between the management system and the human operators. The management system plays a very important part, informing on possible anomalies and executing the commands of control. The different tasks involved in this management and for which commercial expert systems currently exist are as follows. Failure management. This task refers to the group of functions related to network management necessary for the detection, diagnosis, recovery and correction of shortcomings of the elements that form a telecommunication network. Examples include Max and Opti-Max (an expert administrator of telephony line maintenance developed by NYNEX) (Rabinowitz et al., 1991), Trouble Locator (an intelligent system developed by Pacific Bell for locating failures at the physical level of a local telephony network) (Chen et al., 1996), ANSWER (an expert system developed by AT&T and in charge of supervising their 4ESS switches) and Scout (developed by AT&T for identifying persistent failures in the network) (Raman, 1999). Configuration management. This function helps the administrator to exercise control on the configuration of the components of the network. Changes in the configuration are carried out to eliminate congestion, to isolate shortcomings or to make changes required by users. Examples of expert systems supporting configuration management include ECXpert (detection and reparation of failures, developed by Lucent Technologies) (Raman, 1999), ACE (an expert system developed by AT&T for help in the detection and diagnosis of failures in cables) (Liebowitz, 1988) and NEMESYS (also developed by AT&T for avoiding network congestion) (Raman, 1999). Accounting management. This function allows positions and costs for the use of the resources of the network to be determined and located, e.g. APRI (developed by AT&T for forecasting the probability of falling into new debt) (Ezawa & Norton, 1996). Presentation management. This task helps the network administrators to monitor and evaluate the benefits of the system. Example Failure management Configuration management Network management Accounting management Presentation management Security management Expert systems applied to User interfaces Final user application Communication satellites Network design Protocol verification Routing Figure 1: Expert systems in telecommunication networks. expert systems for presentation management are Net=Advisor and NetCommand (for monitoring the state of the network in real time) (Raman, 1999). Security management. This function helps the network administrators manage the services that provide protection in the access to the communication resources. Examples of expert systems related to security management include EXSYS (a set of expert systems developed by Pacific Bell which executes on an AT&T 3B2=600 computer for supervising the loop maintenance operating system from a server) (Raman, 1999). In addition, there exist other expert systems such as NetHELP (which provides assistance for user troubleshooting) and ExSim (assistance in the process of routing a network) applied to other fields (Raman, 1999), enumerated in Figure 1. There is an especially interesting yet less investigated field for the application of expert systems to the world of telecommunication networks: systems applied to assist during the tasks of network design. Within the design process, the use of knowledge-based systems is of particular interest for the topological design of the network. Among these tasks are the following: the choice of the type of transmission: transmission by physical support (cable, microstrip, wave-guided) and=or transmission by radio (electromagnetic waves). the layout of the network: in radio networks it would be necessary to establish the layout depending on the type of communication (bidirectional or omni-directional) and signal propagation and interference characteristics. In cable networks, this task comprises the process of cable layout. placement of the network elements: establishment and localization of the different nodes and necessary elements in order to obtain a suitable signal level (splitters, amplifiers etc.). The last two tasks in particular require the work of experts who apply various design rules and their empirical knowledge. Because of the great number of limitations of the physical media, these tasks are particularly complex in cable networks. On the other hand, due to the very specific characteristics of the design rules for each network, as well as the high complexity of the application of the knowledge, the development and commercial use of expert systems for cable network design is still not very widely extended. Thus, the currently existing approaches mainly focus on research (Lo & Ghauri, 1991; Wu & Lee, 1993; El-Fishawy & Khamis, 2000). In some cases, the design is only partial (Lo & Ghauri, 1991); other approaches (Wu & Lee, 1993; El-Fishawy & Khamis, 2000) are limited to the design of local networks. In this paper we propose an expert system for the complete design of a cable network. 3. The HFC cable network A typical cable network, which covers a medium-sized city, consists of an HFC network that is made up of an optical fibre network and its continuation into a coax network. Potentially, a parallel telephony network is deployed (Tunmann, 1995; Ovadia, 2001). The cable network structure supports cable television, Internet access and telephony services; it is represented in Figure 2. The structure Main nodes 30.000 to 90.000 Fibre Primary Network Secondary nodes 2000 homes Secondary Network ONT ONT ONT Fibre Optical Network Termination 500 homes Distribution Network Remote Telephony centre Figure 2: The HFC network to be designed. of the network depends on each country and operator, but typically a fibre optic network is made up of a head-end connected to a primary network, which contains a number of primary nodes, e.g. servicing between 30,000 and 90,000 homes each. These main nodes are connected to a network of several secondary nodes (secondary networks), each of which typically serves around 10,000 homes. In general, the secondary nodes also contain a remote telephony centre (RTC). The tertiary networks (distribution networks) connect to the secondary node and end in optical network terminations (ONTs), which are connected to a coax network. This coax network finally distributes the signal to the subscribers. The telephony network typically starts at each RTC and has three levels. The first level connects each RTC to an ONT, the second level reaches a group of homes and, finally, the third level connects with the subscribers’ homes. In Figure 3, a representation of a typical coax area of a cable network extracted from a geographical information system (GIS) (Heywood et al., 1999; Korte, 2001) is shown. In this figure, the buildings are represented as shaded polygons, the cables as lines, the connections as small circles and boxes, and signal amplifiers as triangles. In the design of an HFC network the layout of the first, secondary and distribution fibre networks are normally easy to carry out because the location of their elements depends on the availability of adequate premises. Thus, the part of the network that particularly requires deep expert knowledge during design is the coax network. When a human designer carries out a coax network design he in many cases is only guided by his expert knowledge and intuition, and very basic support tools. The designer works this way: with the help of specific software which reads and represents the geographical information from a GIS he begins the layout at the ONT progressively placing the cables and elements and carrying out the calculation of the signal level. If at some point it is not possible to reach the desired signal level on a particular Figure 3: Design of a zone of the cable network. connection with the layout in process, the designer has to redesign all or a part of the layout. Following this commonly used approach, the average time of producing a finished design for an ONT zone of around 500 connections is around 8 hours. 4. Datacab: an expert system for designing a cable network 4.1. Introduction Datacab is an expert system we designed and implemented based on rules for the automatic design of an HFC telecommunication network and which works in an integrated manner with a GIS. The major advantage of the proposed expert system approach is the great reduction of the human workforce needed for the design of the HFC network. With Datacab, instead of doing the designs himself, the human expert only has to verify the different designs generated by Datacab. Another important advantage is its adaptability, being possible to easily modify the knowledge base if the design criteria change, and its high integration, working as add-on software to the existing GIS. Finally, similar to other expert systems, the developed system can be used to train new staff. The GIS into which Datacab is integrated is GE SmallWorld (Rigaux et al., 2002), a powerful commercial GIS with special deployment in the areas of distribution networks like water, electricity, gas and telecommunication networks. 4.2. Interaction with GIS Datacab performs the design of the HFC network through the phases represented in Figure 4. Phase 1: Datacab processes the geographical information corresponding to the zone to be designed, adding it to its knowledge base. The input data of the different elements of the zone with their location and all redesign information (i.e. possible access to accommodations, previous channel locations, nonpermitted fac¸ ades etc.) is obtained from the GIS. Phase 2: By means of a graph representation of the GIS elements of the zone and the mechanisms of application of the knowledge, Datacab carries out the necessary calculations to achieve an optimal solution for the cable network design. Previously, a database access is realized in order to obtain the different parameters, such as the degree of attenuation of the cables or the gain of the available amplifiers for the different commercial network elements typically installed by the HFC operator. Phase 3: Datacab processes the obtained information, generates the network design based on the rule database and provides the GIS with the geographical information of the elements belonging to the cable network. 4.3. Design Datacab’s architecture consists, like most expert systems, of a knowledge base and an inference engine. The knowledge base consists of a class structure and a rule-based system which are described further below. The inference engine, which takes care of the firing of the rules, is Database of elements GIS data City information Redesign data Datacab input Datacab database queries GIS data Network elements Datacab output Figure 4: Datacab’s interaction with GIS. carried out by an expert system environment called ART*Enterprise which is described in the coding section. In addition, a salience mechanism was developed and added for rule inferencing. This mechanism makes it possible to fire the rules in the order that corresponds to the priority defined for each rule. We selected a knowledge representation, taking into account that the problem was formed by different network elements, and a set of rules and conditions necessary to place these elements in the layout. These rules, which are defined in internal design guides and procedures of the company, were studied and defined during the knowledge acquisition phase. The geographic elements are represented by objects according to the class diagram of the application. The necessary knowledge data to carry out the design is contained in the rulebased system. The methods which execute the firing of the rules are enclosed in a class called dc:algorithm (kernel package). 4.3.1. Class diagram The class diagram of Datacab was designed with the help of the Rational Rose tool using UML (Eriksson & Penker, 1997; Booch et al., 1999) and is formed of seven packages, which are linked as shown in Figure 5. The class diagram includes geographical elements (streets, buildings etc.), redesign information (i.e. access points to buildings), coax elements (wires, amplifiers etc.), civil elements (caskets, channels etc.) as well as the elements corresponding to the telephony and fibre networks, in addition to superclasses, which were created to generalize some common properties of our objects such as distances in linear elements and signal losses in elements of the coax network. There is an important package called Base- Type. This package represents the group of geometric elements which are inherited by the different elements from the map, civil, radio frequency and kernel packages. In Figure 6 the classes that form this package and that are needed to deal with the geographic properties of the elements are illustrated. The class dc: segment represents a segment of geometric elements. An object of this class is composed of two objects of the class dc:point, which represents a geometric point and which is constituted by a pair of coordinates. The class dc:area which represents the element geometric area is Civil Coax Fibre BaseType Kernel Map global Telephony Figure 5: Package diagram. dc:gis id : Enum{...} state:Enum{...} 2..*0..* dc:segment points : Set(Point) 0..* dc:area 3..* dc:point x : Float y : Float 2..*0..* Is formed by 0..* 3..* Is formed by <<ordered>> pointList : Sequence(Point) Figure 6: BaseType package. composed of a sorted list of objects of the dc:point class. Finally, there is a class called dc:gis from which all the mentioned classes derive. The coax package has a superclass called Coax, which contains three classes corresponding to the type of coax element: passive component (i.e. wires), active component (amplifiers) and power source (to feed active components). Thus, the advantages of inheritance are important, for example, in classes inherited from passive elements which obtain characteristics on the one hand from coax elements and on the other hand from their geometric data. Serving as an illustrative example, the class diagram of the passive elements is shown in Figure 7. Datacab includes a database of elements. This database contains all the characteristic data from the network elements for the corresponding city or zone. Thus, for instance, if the company changes a model of amplifier it is not necessary to reprogram Datacab but simply to update the database. In this way, Datacab will instantiate one copy of each different child class of the coax diagram and the attributes with technical characteristics are filled in according to their constructor via database accesses. 4.3.2. Algorithm When the geographic information is read from the GIS, each element of the zone, like a street or a building, is converted into an object of the class diagram and a connected graph is generated. Initially we investigated two alternatives for the design of the algorithm, based on the notion of algorithms for design of an expansion tree related to a non-directed graph (Sedgewick, 1992; Castillo et al., 1997; Bratko, 2001). The alternatives were as follows. The first alternative was based on the idea of Kruskal’s algorithm, which selects the edges sorted by cost avoiding cycles in the layout. Kruskal’s algorithm selects the lowest cost edge in each of the iterations, as long as it does not generate any cycles. The second alternative was based on the running of Prim’s algorithm, which starts from a point and selects serial edges of minor cost, building an expansion tree in this way. After studying and applying these two alternatives to our particular problem, and designing prototypes based on both of them, we decided to implement the first alternative which begins by determining the layout and then establishes the situation of the elements of radio frequency. If it is not possible to locate the elements in the selected route, a search for a different route is dc:point (from BaseType) dc:passive CurrentBlocker dc:coaxcable dc:segment (from BaseType) TerminalChargeEqualiser Tapdc:splitter Figure 7: Coax passive elements. carried out and an attempt is made to relocate the elements. Note that when a human expert carries out the design of a network, the radio frequency elements are placed at the same time as the layout is determined, which resembles more the second algorithm. However, this approach was discarded because of its higher system requirements and because the first algorithm proved to result in similarly good design results. The difference between Kruskal’s algorithm and our algorithm lies in the dynamic characteristics of the latter. While the edge cost in Kruskal’s algorithm does not depend on the previously selected edges, in our algorithm the cost is allowed to vary. We distinguished two kinds of edge cost in the algorithm. The static cost of a certain edge is defined as the cost that does not depend on the previously selected edges for the layout by the algorithm, i.e. the cost that is independent of the state of the layout such as the longitude of a certain street and the necessary cable to cover it. The dynamic cost is defined as the cost which at same point depends on the previously selected edges for the layout; i.e. the cost which is related to the state of the layout as, for example, the cost of a crossing between a placed cable and another cable (the company tries to avoid such cases). These rules use methods belonging to the different radio frequency objects which are derived from the class radio-frequency. There are two especially useful methods of signal-level calculation. Regressive signal-level calculation calculates regressively the level of signal at a certain object. Therefore, it calculates the signal level belonging to an element and all the elements connected from it until the ONT. Progressive signal-level calculation calculates progressively the level of signal at an object. Thus, it calculates the signal level belonging to an element and all the elements connected from it until the different points of connection in which it is involved. 4.3.3. Rule-based system The knowledge data are represented in the form of if–then rules or, to put it another way, of rules made up of premises and conclusions to which a salience mechanism was added in order to provide them with a priority order. This system of reasoning has been chosen instead of other kinds of reasoning, such as reasoning based on cases, because the design of an HFC network is based on rules defined by the experience of the experts. There are five main groups of rules in our system. Rules of initialization (R1) are a group of rules which carry out the preprocessing of the information of the streets from the GIS, converting these data into Datacab information. In addition, they carry out a series of previously necessary calculations for the execution of the algorithms. Rules of edge sorting by static cost (R2) are a group of rules which carry out a sorting by static cost of the different streets of the zone. This group of rules comprises the rules for the division of zones, e.g. from 500 homes into four zones of about 125 homes. Rules of sorting by dynamic cost and selection of edges (R3) sort by dynamic cost the different streets of the zone. In addition, this group contains the necessary rules to select On the other hand, the previous costs are determined by a priority number which was defined for the firing of each of the rules. Thus, if the firing of two rules at the same point was possible, the one with the higher priority would be fired and therefore it would get assigned a lower cost. Once the layout is achieved, the network elements are placed by means of a group of rules which calculate the signal levels corresponding to each of the nodes of the layout. These rules thus determine the positioning of the amplification elements based on the calculated attenuation, in order to provide the subscriber with the right signal level. from the previous order the edges necessary for the layout. Rules of location of elements (R4) is a group of rules belonging to the placement of the different necessary radio frequency elements for the correct wiring of the zone. By applying these rules, which calculate the signal level at each node, the different radio frequency elements (i.e. amplifiers, closets etc.) are located. If it is not possible to locate the elements, it is necessary to go back and fire a new group of rules. Rules of generation of the output data toward the GIS (R5) generate the files with the necessary GIS information for the specification of the different elements belonging to the resulting layout, as well as their corresponding parameters. The order of firing of the above-mentioned groups of rules is shown in Figure 8. First, Datacab is initialized and the GIS data are read by means of firing group R1. Later, the ordering of the several edges is carried out by means of groups R2 and R3. The ordering from dynamic sorting generates a layout. The elements are placed and the signal calculations are carried out by means of the group R4. If it is possible to reach the desired signal level with the generated layout from the previous phase, the design is considered good and the GIS data are generated (R5). Otherwise, another static order is forced and therefore another layout is designed. Currently, the total number of rules is 147. Table 1 shows some examples of rules for each group. The table contains four columns with information for each of the rules. The first column indicates the phase in which the rule is fired, the second contains the name of the rule, the third shows its priority, with a lower number meaning a lower priority, and finally in the last column a brief description of the rule is given. 4.3.4. Coding For coding these rules, we have used a tool for expert systems called ART*En- terprise. From the programming paradigm perspective, ART*Enterprise provides objectoriented programming, rule-based programming, case-based reasoning and procedural programming. Its programming language is very similar to CLIPS (Giarratano & Riley, 1994), maintaining the same structure. In Figure 9 we can see an example of the coding of a rule in our system, which prefers the edges that represent fac¸ ade cables over edges representing cables requiring tubes. The rule has a priority of 700 which is defined in the code after ‘salience’, in the premises zone (before ¼>). The rule chooses between two possible objects (street1 and street2), which represent two different kinds of edges (fac¸ ade or tubes), and preferably selects the one which is over fac¸ ade. An ART*Enterprise application generally consists of three layers: a graphical user interface layer, an application model layer and a database mapping layer. We did not implement the graphical user interface for Datacab since this function was carried out by the GIS application. ART*Enterprise has file management capabilities that make it possible to easily carry out the exchange of data between the GIS and Rules of initialization Rules of sorting of edges by static cost Rules of sorting by dynamic cost and selection of edges Rules of location of elements Rules of generation of the output data toward the GIS Figure 8: Order of firing the group of rules.