Design of a Message Switching System, The : Software Reusability Applied to Discrete Event Simulation ; Teclmical Repmi 20 18-07-ECE-0 17; Technical Report 88-CSE-11
This paper proposes a framework for software system design. The framework is based on the decomposition and abstraction. The design formalism will employ an Object Descriptive Attributed Notation (ODAN) for software design representation which records three types of primary information of software system detail design: the decomposition hierarchy (of the system being designed), the taxonomic structure (recognizing the construction and function similarities), and the coupling specification (specifying the way of component integration). A message switching simulation system will be taken as an example during the discussion. An Ada program based on this design is also presented. ; Technical Report 2018-07-ECE-017 Technical Report 88-CSE-11 The Design of a Message Switching System: Software Reusability Applied to Discrete Event Simulation W. P. Yin Murat M. Tanik This technical report is a reissue of a technical report issued February 1988 Department of Electrical and Computer Engineering University of Alabama at Birmingham July 2018 Technical Report 88-CSE-11 THE DESIGN OF A MESSAGE SWITCHING SYSTEM: SOFTWARE REUSABILITY APPLIED TO DISCRETE EVENT SIMULATION W. P. Yin M. M. Tanik Department of Computer Science and Engineering Southern Methodist University Dallas, Texas 75275-0122 February 1988 The Design of a Message Switching System: Software Reusability Applied to Discrete Event Simulation W.P.Yin M. M. Tanik Department of Computer Science SMU Abstract - This paper proposes a framework for software system design. The framework is based on the decomposition and abstraction. The design formalism will employ an Object Descriptive Attributed Notation (ODAN) for software design representation which records three types of primary information of software system detail design : the decomposition hierarchy (of the system being designed), the taxonomic structure (recognizing the construction and function similarities), and the coupling specification (specifying the way of component integration) . A message switching simulation system will be taken as an example during the discussion . An Ada program based on this design is also presented. I. INTRODUCTION Recent years, software engineers gradually realize that reuse concepts play a key role in several issues [1] : productivity, maintainability, portability, quality, and standards. A carefully engineered collection of re t:·sa.ble software components can reduce the cost of software development, improve the quality of software products, and accelerate software production [2] . Many approaches have been proposed and implemented which have tried to make the reuse of software components a reality. Among them , subroutine libraries, software generators and object-oriented programming have achieved relative popularity [3, 9]. The technical foundations for making software reuse a viable alternative to program development have been identified and demonstrated by several projects [4, 11] . In this paper a software detail design methodology and a design representation system (ODAN) [10] is presented. One specific example, a message switching communication system, is developed using this methodology and representation. A message switching communication system was chosen as the application because it shows the range of ODAN's applicabilities and presents a number of interesting design problems. Ada was chosen as the implementation language because it is capable for dedicated concurrent programming, provides much needed facilities for synchronization, and appears to be good at supporting software reusability. The specific design technique used here is described in Section II. The communication system itself is then developed in Section III through V. Section III specifies the functional requirements of the system. Section IV summarizes the major features of ODAN and presents the system decomposition, abstraction, and integration in terms of ODAN. Section V refines the decomposition by giving outlines of Ada programs for some of the interesting - II - parts of the system. Finally, Section VI summaries the conclusion of our explorative work. II. DESIGN TECHNIQUE The process of design is a transformation of a designer's ideas and expertise in to a concrete implementation [ 5]. Observing the design process, we can see the following facts: • Software design is a creative act of individuals using basic problem-solving techniques, building conceptual solutions based upon a software system specification . • By providing decomposition and abstraction mechanisms, a large-scale, complex problem will become an aggregation of subproblems. The solution for original problem will be the • combination of the solutions for subproblems. The design representation is a knowledge representation that facilitates expressing the system decomposition hierarchy, the similarities of system components presented, and the coupling constraints on which system components are identified in the decomposition hierarchy. The design described here is developed in two major steps: system decomposition and component abstraction. By iterating between decomposition and abstraction , three kinds of information are derived: decomposition, taxonomy and integration. By decomposition we mean that dividing the original problem into smaller models that are themselves small problems and interact with one another in simple, well-defined ways [6]. By abstraction we mean the change in the level of detail to be considered in which certain details are ignored in an effort to convert the original problem to a simpler one. In our design technique, we use a decomposition form which gives software system designers opportunity to concentrate on the behavior of the entities of the application and the relationships among them. Therefore, a designer is to be working at the level of general construction and functionality description, but not to the degree of precision necessary for executability. The design process can be characterized as [ 5] :"The design procedure is a series of successive refinements comprising two types of design activities. The first type concerns the transitions between the so-called design levels. The second type defines a set design actions associated with a given design level. The design levels are successive refinements of the decomposition of the system under consideration." At the beginning of a software system design , designers decompose the original problem into subproblems based upon a behavioral scenario. Each subproblem corresponds to one object in the problem, in which changing the state of one object will affect the state of other objects. Decomposition continues until the subproblems are not further decomposable, i.e., any state changing on that object will not have effect on any other objects. During the decomposition, each object in the problem space will be designed as an entity in the solution space. Entities in solution space will be represented in computers. For each solution entity, three kinds of information are derived. First, the decomposition hierarchy (of the system) is declared. The decomposition hierarchy is the composition schema for the object. Composition schema contains data items which indicate the object states and operations which manipulate the data items. Second, the taxonomic - III - knowledge is specified. This knowledge can be viewed as a representation for inheritance relar tions which declare the reusability information, i.e., one entity in solution space can inherit some facilities designed in another entity. Inherited facilities include data items, operations or a whole entity. One entity can have multiple inheritance. These taxonomic knowledge will be used during further evolutionary stages in making reusable code segments. Third, the integration rules are specified. The primary goal for decomposition of the original problem is to divide-and-conquer. The partial solutions of subproblems must be coupled together to solve the original problem. The integration rules specify the data flow and control flow among the entities, input and output constraints, and an activating algorithm . ODAN [10] is used for design representation. For each entity in the solution space a set of attributes is attached. Attributes are classified into three groups corresponding to the above three kinds of information. The values for attributes are designer-defined, e.g., the value can be a single word, a sentence, a piece of code, a rule, an abstract algorithm, or a link to another entity based on the attribute meaning. We choose ODAN as our design representation because it gives software designers flexibility to add or erase attributes, or assign a specific value to the attribute. In addition , ODAN is easy to be machine representable and computable. This benefit will help software engineers to store and retrieve the previous design . III. SPECIFICATION OF A MESSAGE SWITCHING SYSTEM A typical message switching system [7] has been chosr'n as an example to show the detail of our design technique because it is a problem that is realistic in nature and implements many of concepts of embedded systems. This generalized system is typical of several communication systems used by the U.S. government and NATO. The complete system consists of a network of switching nodes connected via high-speed trunk lines. Each switching node has an auxiliary memory, an archive facility, an operator, and can support up to fifty subscriber terminals. Figure 1 shows configuration for a given node in the system . The general function of each node is to accept input messages from the trunk or local subscriber lines, and route them to one or more output destinations. Input can be received from local subscribers or from another switching node (via the trunk line). The input message is stored in the auxiliary memory and then forwarded to the output destinations, which can be either local subscribers or another node in the network. Since messages must be completely received before forwarded, this type of communication is often called store-andforward message switching. Three successive phases are required to process each message: input, switching, and output. Figure 2 presents the system components and interfaces required to perform these functions. The following summary describes the processing that must be done during each of these phases. Input Figure 1. Typical node configuration • • Oper-ator- Read the input message from a subscriber or trunk link and store the message on both auxiliary memory and archive tapes. Each input message consists of a header, a body and an end (end-of-message indicator). Switch Examine the header to determine the output destinations. For each destination , consult a directory to determine the appropriate output line to use (local subscriber or trunk to remote destination). Add a copy of the message header to the output queue on each line . Output Retrieve the message from the auxiliary memory and display it. Each message contains a priority-at all times. The message with the highest priority is transmitted first. Each node has an operator who can send and retrieve messages like a subscriber. In addition, he can monitor and control the message activity at the node; for example, he can cancel a message or check the messages in each output queue. Also the operator is notified of exceptions-for example, end of archive tape. The simulation of this system addresses the following requirements. Figure 2. Message switch system components • Maximum I/ 0 parallelism must be provided. • Two different types of I/0 devices exist (trunks and terminals) . Both process messages. • Switch must coordinate output to multiple destinations. • Messages have priorities. • The auxiliary memory and terminal devices must be controlled and synchronized because we are simulating more than one l/0 device . We now turn our attention to the design of a message switching simulation system that solves each of these problems. V. DETAIL SYS'IEM DESIGN IN 0DAN The main activity of software design is not only generating new programs but also maintaining, integrating, modifying, and explaining existing ones [8]. Based upon the problem modelling and system specification, designers know what the message switching system should look like and how it should behave. Iterating between decomposition and abstraction, designers will know how the system is divided, what are the functionalities for each component, and how those components will be integrated together. Our objective for using ODAN to represent the design idea is for keeping the reusability in mind before and during the coding not after the coding. -VIA. System Decomposition Acceding to Grady Booch [2] : " Simply stated, object-oriented development is an approach to software design and implementation in which the decomposition of a system is based upon the concept of an object. An object is an entity whose behavior is characterized by the operations that it suffers and it requires of other objects". Using object-oriented design methodology, an object existing in the model of reality will have a corresponding structureentity in the solution. As specified above, each message processed by a switching node goes through three phases: input, switch, and output. In the problem space, there are several different objects participate these three phases, I/ 0 devices for sending and reading messages, a temporary memory for storing messages, a long term memory for message backup, a reference table for destination list, and a switching node for scheduling message transmission. The decomposition is shown in Figure 2. Each I/ 0 device manages one subscriber or trunk line . The auxiliary memory provides a temporary storage. The archive tape provides a tape storage for recording all message transmission . The table provides the destination cross-reference. The switch coordinates the output to multiple destinations. Using ODAN, we can describe the system decomposition in the following way. Message_8witching_8ystem Components: (Aux.:Mem , Archive_Tape, Reference_Table, Subscribers, Trunks, Switch , Operator) Interface: ~Operator Aux_Mem Components: ( Storage_Cell, directory_Cell) Access_Constrain t: mutual exclusive Operations: (Write, Read, Write_Directory, Read_Directory) Archive_Tape Components: (Tape) Access_Constrain t: mutual exclusive Operations: (Arch ive.:Msg, Re trieve_Msg) Reference_Table Components: (Table) Operations: (Look_Up, Insert, Delete) Trunk Components: (Msg_Queue) Access_Constrain t: mutual exclusive Operations: (Broad cast_Msg) Subscriber Components: (Msg_Queue) Access_Constrain t: mutual exclusive Operations: -VII- (Add, Delete, ls_Empty, Read_Terminal, Write_Terminal) Switch Components: (Msg_Queue) Access_Constrain t: mutual exclusive Operations: (Add, Delete, ls_Empty) For abstraction reasons, we ignore some details here. Actually, for each component and operation, ODAN provides a set of attributes. For example, in Aux_Mem entity, the system designer may specify the structure for Storage_Cell and Directory_Cell, algorithm skeleton for each operation, and exceptions for the operations. The algorithm skeleton may take an existing program code as its body, or a set of rules, or a PDL like specifications. We take an Ada like specification as the algorithm body. B. Similarity Recognition As we mentioned before, our goal is to make design information not only used to develop a new program, but also provide reusable designs. During the system design stage, based upon the object-oriented decomposition and construction as well as function specification on those objects, designers have an opportunity to recognize the construction - VIII - and function similarities among those objects. In ODAN, we introduce knowledge representation into software design. More specificly, we take inheritance relations in semantic nets and modify the semantics of those relations to represent the construction or function similarities. For example, the components of two entities, Reference_Table and Archive_Tape, have a functional similarity. Reference uses a "table" to save all the destination information, Archive_Tape uses a "tape" to backup all the messages. Ignoring the structures of destination and message information, functions for a table and tape can be the same, sequential data structure and no priority. In our design, we use a non-priority queue to implement the reference table and archive tape. The design representation is as follows. Non_Friority_Qu eue Components: ( Queue_En try) Operations: (Clear, Is_Empty, Add, Position_Of, Remove, En try_Of) Archive_ Tape Components: (Tape) instance of Non_Friority_Queue • • • Reference_Table Components: (Table) insta.nce of Non_Friority_Queue • • • Here we modified the semantics of instance of relation because the component for reference table is an instance of a non-priority queue, the non-priority queue will be biding inside the reference table. The manipulations on the table will be specified by reference table operations. In the same way, message queues are designed as follows: Priority_Queue Components: ( Queue_Entry) Operations: (Clear, Is_Empty, Add, Delete) I f Trunk Components: -IX- (Msg_Queue) instance of Priority_Queue • • • Subscriber Components: (Msg_Queue) instance of Priority_Queue • • • Switch Components: (Msg_Queue) instance of Priority_Queue • • • C. Component Integration Entities of a software system are not isolated. They are related with each other to do a specific task. One important information in the software design is the coupling specification, (how those entities coordinate). In ODAN we use the "interface" attribute, to indicate the relation information and coupling specification. The operations provide static default interface if no explicit interface specified. In the message switching system, we specify the interface for auxiliary memory, switch, and subscriber in the following way. Aux_MemJnterface time_rule: concurrent con trol_ru le : iterative im port_ru le: single body: (loop select ac ce pt Read_Msg or acce pt Wri te_Msg end select end loop) SwitchJnterface time_rule: concurrent controLrule: iterative body: (loop if not Is_Empty(Msg_Queue) -- Delete(Msg_Header) -- Look_Up(Msg_Header) - X - -- Add( Su bscriber_Msg_Queue) end if end loop) Su bscriberJn terface time_rule: concurrent control_rule: iterative body: (loop while not Is_Empty(Msg_Queue) -- Delete(Msg_Header) -- Aux_Mem.Read_Msg(Msg) -- Display(Msg) end loop -- Read_Terminal(Msg) -- Aux_Mem.Write_Msg(Msg) -- Archive_Tape.Archive_Msg(Msg) -- Add(Switch_Msg_Queue) end loop) -XIXI. DESIGN IMPLEMENTATION We choose Ada as the implementation language. Ada is a general-purpose language that embodies and enforces the modern software engineering principles of abstraction , information hiding, modularity, and locality. Ada offers a number of features that facilities the expression of reusable software components and real-time systems. For example, generic program units are parameterized templates for generating software components; tasks operates in parallel with other program units and imply the mutual exclusion; systematic separation between visible syntactic interface specifications and hidden bodies allow the programmer to separate concerns of module interconnections from concerns about how the module performs its task. Ada is used here as an implementation language for message switching system also because it is available in our VAX 11 / 780 under Unix operating system. Some specific algorithm designs can be written in Ada, and taken as the value of some ODAN attributes. Those algorithms written in Ada serves as intermediate steps between system detail design and coding. Since our goal is also to show how to make a reusable software component during the design stage, we will not show the complete detail of program code . The executable code runs on VAX 11 / 780 under Unix operating system . A. Message Queue As we mentioned before in system decomposition section, we decided to design a priority queue to implement the message queue for subscribers, trunks and switches. Ada's generic package provides a powerful too!· &.t this point. Generic packages have the ability to create templates of program units with generic parameters needed at translation time . The specification of generic priority queue package is as follows. genenc type QUEUE_ENTRY is private; type PRIORITY is limited private; with function PRIORITY_OF(THE_ENTRY : in QUEUE_EN1RY) return PRIORITY; with function " SIGNAL, PRIORITY => PRIORITY_TYPE, PRIORITY _OF=> CHEOK_PRIORITY, " " PORT2, PORT_QUEUE = > QUEUE_?KG .SUBSCRIBERl_QUEUE, -XIVPORT_ QUEUE_8EMAPHOR => TABLEYKG.SUBSCRIBERLQUEUE_8EMAPHOR, GETJIEADER => DEVICE_DRIVERSYKG.GETJIEADER_VTlOO, GET_BLOCK => DEVICE_DRIVERSYKG.GET_BLOCK_VTlOO, PUTJIEADER => DEVICE_DRIVERSYKG.PUTJIEADER_VTlOO, PUT_BLOCK => DEVICE_DRIVERSYKG.PUT_BLOCK_VTlOO) ; package TRUNK is new NOD EYKG (PORT =>PORTS, PORT_QUEUE => QUEUEYKG.TRUNK_QUEUE, PORT_QUEUE_8EMAPHOR => TABLEYKG.TRUNK_QUEUE_8EMAPHOR, GETJIEADER => DEVICE_DRIVERSYKG.GETJIEADER_TRUNK, GET_BLOCK => DEVICE_DRIVERSYKG.GET_BLOCK_TRUNK, PUTJIEADER => DEVICE_DRIVERSYKG.PUTJIEADER_TRUNK, PUT_BLOCK => DEVICE_DRIVERSYKG.PUT_BLOCK_TRUNK); C. Simulation Control Message switching system is a multiple processing system, but we simulate this multiple I/0 device activities on a single 1/0 device - one terminal. Thus, it is necessary to synchronize the access to the terminal. This synchronization is implemented by an Ada task. The semantics of Ada tasks guarantee the mutual exclusion . Only one task can access the terminal at a time, and if more than one task try to access at the same time, the remaining ones except one have to wait in an implicit queue so as not to interfere with each other. If those tasks arrive at different times, the first task will be permitted accessing first, the remaining ones are put in the queue based upon a time stamp. The task for synchronizing the terminal access is as follows: task I0_8YNC is entry REQUESTJO_DEVICE; entry RELEASEJOJ)EVICE; end I0_8YNC; task body 10_8YNC is BUSY: BOOLEAN:= false; begin loop select when not BUSY=> accept REQUESTJOJ)EVICE do BUSY :=true; end REQUESTJOJ)EVICE; or accept RELEASE_IO_DEVICE do BUSY :=false; end RELEASE_IO_DEVICE; end select; end loop; end IO_SYNC; -XVXV. CONCLUSION Current approaches for software reusability are primarily based on code sharing and subroutine libraries . Ada's generic units provide additional reusability techniques. We believe that if we can find ways to express reusable software components at a higher level than at the programming code level, software reusability will significantly improve the software productivity. The message switching system design is our explorative work on software reusability. 'Ne feel that it is necessary to develop a software design representation . Such a representation must not bind the implementation too early and must capture the logic of system functions. The programming environment support is also important for applying software reusability more effectively. REFERENCES [1] P . G. Bassett, " Framed-Based Software Engineering," IEEE Software, July, 1987. [2] G. Booch, Software Components With Ada, The Benjamin/ Cummings, Publishing Company Inc., 1987. [3] G. E. Kaiser and D. Garlan, " Melding Software Systems from Reusable Building Blocks," IEEE Software, July, 1987 . [ 4] W. Tracz , " Reusability Comes of Age," IEEE Software ", July, 1987. [5] J. W. Rozenblit and B. P. Zeigler, "Concept For Knowledge-Based System Design Environment," Proc. of the 1985 Winter Simulation Conference, San Francisco, Dec.1985. [ 6] B. Liskov and J. Guttag, Abstraction and Specification in Program development, The MIT Press, McGraw-Hill Book Company, 1986. [7] G. R. Andrew, "The design of a Message Switching System : An Application and Evaluar tion of Modula," IEEE Trans. Software Eng., Vol.SE-5, No.2, Mar.1979. [8] G. Fischer, "Cognitive View of Reuse and Redesign," IEEE Software, July, 1987. [9] W. P. Yin, M. M. Tanik, D. Y. Y. Yun, T. J. Lee and A. G. Dale, "Software Reusability: A Survey and A Reusability Experiment", Proc. of FJCC, Dallas, Oct. 1987. [10] W. P. Yin , M . M. Tanik, and D . Y. Y. Yun "Software Design Representation : Object Descriptive Attributed Notation (ODAN), " (Available from authors). [11] R. T. Yeh and T. A. Welch , "Software Evolution: Forging a Paradigm," Proc. of FJCC, Dallas, Oct. 1987.