domain: spi info math

text:
Benjamin Schleich

Nabil Anwer

Luc Mathieu

Sandro Wartzack

Shaping the Digital Twin for Design and Production Engineering

Keywords: Design, Tolerancing, Digital Twin

The digitalization of manufacturing fuels the application of sophisticated virtual product models, which are referred to as digital twins, throughout all stages of product realization. Particularly, more realistic virtual models of manufactured products are essential to bridge the gap between design and manufacturing and to mirror the real and virtual worlds. In this paper, we propose a comprehensive reference model based on the concept of Skin Model Shapes, which serves as a digital twin of the physical product in design and manufacturing. In this regard, model conceptualization, representation, and implementation as well as applications along the product life-cycle are addressed.

Introduction

In today's highly competitive markets, the ambitions for shortening the time to market and for increasing the product development performance fuel the application of sophisticated virtual product models, which are frequently referred to as digital twins. Enabled by the digitalization of manufacturing, cyber-physical production systems, model-based system engineering, and a growing endeavour for data gathering and processing, these models are increasingly enriched with production and operation data. Moreover, they allow the efficient prediction of the effects of product and process development as well as operating and servicing decisions on the product behaviour without the need for costly and time-expensive physical mockups [START_REF] Leu | CAD model based virtual assembly simulation, planning and training[END_REF][START_REF] Roy | Continuous maintenance and the future -Foundations and technological challenges[END_REF][START_REF] Altintas | Virtual process systems for part machining operations[END_REF]. Particularly in design, such realistic product models are essential to allow the early and efficient assessment of the consequences of design decisions on the quality and function of mechanical products. However, current approaches to the implementation of digital twins lack of a conceptual basis, which hinders the applicability of the digital twin vision to various activities in design and production engineering. Motivated by this need, this paper proposes a comprehensive reference model, which serves as a digital twin of the physical product in design and production engineering. In this regard, important model properties, such as scalability, interoperability, expansibility, and fidelity, as well as different operations on this reference model along the product life-cycle, such as composition, decomposition, conversion, and evaluation are addressed. Moreover, the application of this reference model to geometrical variations management is highlighted. The paper is structured as follows. In the next section, the vision of the digital twin and its evolution is reviewed. After that, a comprehensive reference model for the digital twin is introduced, which is then applied to geometrical variations management. Finally, a conclusion and an outlook are given.

The Vision of the Digital Twin

It has been argued, that "the vision of the digital twin itself refers to a comprehensive physical and functional description of a component, product or system, which includes more or less all information which could be useful in all -the current and subsequent -lifecycle phases" [START_REF] Boschert | Digital Twin -The Simulation Aspect[END_REF]. In the following, the evolution of this vision is briefly illustrated, recent definitions of the digital twin are discussed, and several viewpoints on it are addressed.

The Origin and Evolution of the Digital Twin

Prior to the industrial revolution, physical artefacts were predominantly manufactured by artisans resulting in unique instances of a given template. However, with the introduction of the concept of interchangeable parts in the 18 th century, the way products were designed and manufactured rapidly changed as companies began to strive for building copies of their products in mass production. Recently, the paradigm of mass customization aims at combining these two established manufacturing concepts to achieve low unit costs for customized products. However, though such manufacturing paradigms allow the fabrication of large quantities of similar, i. e. customized, parts or products, these manufactured instances are mere unrelated copies. In contrast to that, the idea of building a twin refers to producing a copy of a part or product and using it for reasoning about other instances of the same part or product -thus establishing a relation between multiple copies. This idea is said to originate from NASA's Apollo program, "where at least two identical space vehicles were built to allow mirroring the conditions of the space vehicle during the mission" [START_REF] Rosen | About The Importance of Autonomy and Digital Twins for the Future of Manufacturing[END_REF]. However, over the past decades, advancements in computer technology enabled establishing increasingly sophisticated virtual models of physical artefacts as well as the fusion of such models for systems engineering [START_REF] Lu | A Model Fusion Approach to Support Negotiations during Complex Engineering System Design[END_REF]. These models not only serve for the design verification and validation [START_REF] Maropoulos | Design verification and validation in product lifecycle[END_REF], but are also increasingly used as the master product model comprising the model-based definition of required product characteristics [START_REF] Quintana | Will Model-based Definition replace engineering drawings throughout the product lifecycle? A global perspective from aerospace industry[END_REF]. Moreover, the evolvements in "microchip, sensor and IT technologies" [START_REF] Abramovici | Semantic data management for the development and continuous reconfiguration of smart products and systems[END_REF] paved the way for the advent of smart products, which track and communicate their operating conditions and thus allow to "feed" their product models with data about their status, such as environmental conditions and loads. s Beside this, modern sensing routines, which go even beyond geometrical measurement and scanning, allow the easy, quick, and reliable collection of large sets of data from physical artefacts. Pattern recognition, data mining, deep learning, reverse engineering, and other data analysis approaches make use of these data sets and unveil dependencies between product, process, and operational characteristics that used to be hidden. The vast developments in simulation technology as well as the increasing possibilities for gathering and exchanging data from products thus allowed for building virtual twins of physical products, which finally led to the present understanding of the "digital twin" vision. Probably the first definition of it was given by NASA in their integrated technology roadmap (Technology Area 11: Modeling, Simulation, Information Technology & Processing Roadmap; 2010), which has been slightly adapted in [START_REF] Glaessgen | The Digital Twin Paradigm for Future NASA and U.S. Air Force Vehicles[END_REF]: "A Digital Twin is an integrated multiphysics, multiscale, probabilistic simulation of an as-built vehicle or system that uses the best available physical models, sensor updates, fleet history, etc., to mirror the life of its corresponding flying twin" (Fig. 1). With some similarity to this, Grieves defines the digital twin as "a set of virtual information constructs that fully describes a potential or actual physical manufactured product from the micro atomic level to the macro geometrical level" [START_REF] Grieves | Digital Twin: Mitigating Unpredictable, Undesirable Emergent Behavior in Complex Systems[END_REF].

Viewpoints on the Digital Twin

Based on these definitions, it can be found, that there exist different viewpoints on the vision of the digital twin. In this context, it has been argued, that "from a simulation point of view the digital twin approach is the next wave in modelling, simulation and optimization technology" [START_REF] Rosen | About The Importance of Autonomy and Digital Twins for the Future of Manufacturing[END_REF]. However, the digital twin is not one complete model of the physical product, but a set of linked operation data artefacts and simulation models, which are of suitable granularity for their intended purpose and evolve throughout the product lifecycle [START_REF] Boschert | Digital Twin -The Simulation Aspect[END_REF]. Thus, the digital twin not only serves representation purposes but is also applicable for making predictions about the expected product behaviour [START_REF] Boschert | Digital Twin -The Simulation Aspect[END_REF], while the granularity of the simulation models fits to their purpose and evolves from early design stages, where simple product models are used to decide about product concepts, to detail design, where sophisticated simulation models support the dimensioning and design of parts and subassemblies. As a result, from a product life-cycle management point of view, there is a strong need to integrate all lifecycle data artefacts into a comprehensive management system, which can be used by various actors for querying data, such as through-life performance information, and making predictions about the physical product from the digital twin for design optimization and manufacturing system improvement [START_REF] Rosen | About The Importance of Autonomy and Digital Twins for the Future of Manufacturing[END_REF].

Current Industrial Understanding and Applications

Different understandings of the "digital twin" can be observed in industrial practice, particularly by PLM software vendors. In this regard, it has been argued, that PTC is focusing on establishing a link between the virtual product model and the physical part to increase the manufacturing flexibility and competitiveness, while Dassault Systèmes targets the product design performance by creating a platform that enables designers to virtually build and interact with complex systems. Moreover, the digital twin understanding of General Electric focuses on forecasting the health and performance of their products over lifetime, whereas SIEMENS strives for improved efficiency and quality in manufacturing by exploiting the possibilities of today's manufacturing digitalization in the context of Industry 4.0. TESLA aims at developing a digital twin for every built car, hence enabling synchronous data transmission between the car and the factory, while other companies increasingly use complex product models to boost the immersion in virtual and augmented reality applications.

Physical Domain Virtual Domain

Design Manu-facturing Use

Synthesis and Discussion

As it has been highlighted, the vision of the digital twin evolved during the last decades and describes the vision of a bi-directional relation between a physical artefact and the set of its virtual models. In this context, the virtual "twinning", i.e. the establishment of such relations between physical parts and their virtual models, enables the efficient execution of product design, manufacturing, servicing, and various other activities throughout the product life-cycle. Particularly in design, such digital twins allow the check for conformance of the product specifications with the design intent and customer requirements. However, as it has been reported in scientific literature and in practice, current limitations to the implementation of the vision of the digital twin are insufficient possibilities for synchronization between the physical and the digital world to establish closed loops, the missing of high-fidelity models for simulation and virtual testing at multiple scales, the lacking uncertainty quantification for such models, the difficulties in the prediction of complex systems, as well as the challenges for gathering and processing large data sets. Indeed, these challenges can only be mastered based on a sound conceptual framework and a comprehensive reference model for the digital twin.

A Reference Model for the Digital Twin

The need for realistic virtual product models for design and manufacturing activities is ubiquitous. However, current approaches to the implementation of digital twins lack of a conceptual basis. This hinders the applicability of the implementations to various activities in design and production engineering and hence handicaps the efforts for building integrated digital twins of physical artefacts. Motivated by this shortcoming, we propose a reference model for the digital twin, which can be considered as a template for the implementation of digital twins for specific applications while ensuring important model properties, such as model scalability, interoperability, expansibility, and fidelity.

Background

The conceptual background of the reference model is borrowed from classical solid modelling and recent developments in ISO standards for Geometrical Product Specifications (GPS), which offer a widely acknowledged framework for the modelling, specification, and verification of product geometry. Solid modelling has introduced the abstraction-representation schema to conceptualize the idealized physical product, and to implement it on computers with a suitable representation. ISO GPS standards evolved from industrial best-practices and examples to more rigorous concepts and a language with consistent syntax and semantics with the aim of transferring them into the age of digitalization. These conceptualization efforts have led to the development of the GeoSpelling "language" [START_REF] Mathieu | GEOSPELLING: a common language for Geometrical Product Specification and Verification to express method uncertainty[END_REF] which is based on sound concepts to allow the unambiguous definition of geometrical specifications and to mirror specification and verification operations on the grounds of a duality principle. One of these basic concepts is the Skin Model, which is an abstract model of the physical interface between a workpiece and its environment [START_REF] Anwer | The skin model, a comprehensive geometric model for engineering design[END_REF]. The Skin model permits a mental model and thought experiments to develop a theoretical inspection procedure, hence connecting the specification world to the physical world. Furthermore, several mirrored operations and uncertainties (ambiguities, method uncertainty, implementation uncertainty) were defined [START_REF] Nielsen | Recent developments in International Organization for Standardization geometrical product specification standards and strategic plans for future work[END_REF].

Model Abstraction and Representation

The idea behind the comprehensive reference model is to extend and transfer the above conceptual framework and to convey the scientific fundamentals of the geometrical product specification language to the vision of the digital twin. The novelty of this reference model is the particular focus on the "twinning" between the physical and the virtual realm. In this regard, we propose to endow the digital twin with an abstract model that comprises all characteristics and fully describes the physical twin at a conceptual level throughout the whole product life-cycle. Based on this abstract model thoughts experiments can be performed, which allows to capture and understand as well as to clearly describe the physical twin, its behaviour and its environment at an abstract level.

The experiences from GPS standardization and recent research efforts on tolerancing led to the insight that only the differentiation between the real workpiece, its abstract and conceptual model (Skin Model), and the virtual representation of this abstract model allows for a clear understanding as well as a forward-looking language for geometrical variations management. Consequently, the concept of Skin Model Shapes has been developed for the virtual representation of the Skin Model based on discrete geometry representation schemes [START_REF] Schleich | Skin Model Shapes: A new paradigm shift for geometric variations modelling in mechanical engineering[END_REF]. With similarity to this, we propose a differentiation between the abstraction of the digital twin and its representation (Fig. 2). In this context, the model representation may depend on the particular application and can involve various representation and modelling paradigms. The differentiation between a conceptual model and its virtual representation for the digital twin allows achieving important model properties (Table 1), such as model scalability, interoperability, expansibility, and fidelity. In this regard, the abstract model description enables the definition of model operations at different scales, while models for different interfaced parts and subassemblies of a product can be conceptually queried and digital product models can be expanded to system models.

Physical Twin Digital Twin (Representation) (Abstraction)

Table 1 Properties of the Reference Model for the Digital Twin.

Scalability

Ability to provide an insight at different scales (from fine details to large systems).

Interoperability

Ability to convert, to combine, and to establish equivalence between different model representations.

Expansibility

Ability to integrate, to add, or to replace models.

Fidelity

Ability to describe the closeness to the physical product.

Operations on the Reference Model

Beside the Skin Model, the duality principle is anchored in the ISO GPS standards. It allows the differentiation between a specification operator, which covers a set of operations that are used to define certain geometrical specifications on the Skin Model, and the verification operator, which mirrors the specification operator and comprises the operations that are required to verify the specifications on the real part. Though the verification operator mirrors the specification operator, there will always remain uncertainties whether the verification operations fully comply with the specification operator. This duality principle as well as the concept of uncertainties is also conveyed to the reference model for the digital twin. In this regard, the application of a digital twin to different scenarios and tasks in design or production engineering dictates to apply certain operations on the digital twin. These operations depend on the specific application and are backed by physical counterparts (such e.g. manufacturing or assembly operations). The abstraction of the digital twin allows describing these operations on an abstract level, while their virtual "representation" is performed employing specific simulation models. Due to the nature of simulation models, obviously, uncertainties will remain between the abstract description of a certain operation and its representation. We propose here to classify the set of operations in four broad categories, namely conversion, composition, decomposition, and evaluation. Moreover, the "twinning" between the physical world and the virtual world can be considered as observation and prediction phases at a conceptual level (Fig. 3). While the information transfer from the physical to the digital twin is related to the observation and sensing of the physical twin, the information transfer from the digital to the physical twin originates from scientific assumptions, simulation and virtual testing models, with proper handling of uncertainty, used to predict certain characteristics and the behaviour of the physical twin.

A Digital Twin for Geometrical Variations Management

The aim of geometrical variations management is to ensure that the required geometrical characteristics of the product are met despite the presence of geometrical part deviations. The implementation of a digital twin for geometrical variations management hence requires the consideration of all different views throughout the product life-cycle that relate to the specification, generation, verification, and propagation of geometrical deviations. For each of these views and applications, specific operations on the digital twin are defined and mirrored by corresponding virtual representations. For this purpose, the set of operations defined in GPS [START_REF]Geometrical Product Specifications (GPS) -General concepts -Part 1: Model for geometrical specification and verification[END_REF] are exploited and mapped to those that operate on the reference model. The concept of Skin Model Shapes as a paradigm shift in computer-aided tolerancing and geometrical variations management [START_REF] Schleich | Status and Prospects of Skin Model Shapes for Geometric Variations Management[END_REF] serves as a first approach to connect these views and operations in a comprehensive model that incorporates manufacturing process planning and inspection process planning (Fig. 4). Thus, an important step towards the "twinning" between the physical world and a virtual model for a digital twin in geometrical variations management has been taken, which serves as a sound basis for ongoing research.

Conclusion and Outlook

The ability for assessing the consequences of product, process, and servicing decisions employing virtual models is an important competitive factor for modern manufacturing companies. The vision of the digital twin refers to an entangled relation between a physical artefact and the set of such virtual models. In this paper, the history and evolvement of the vision of the digital twin as well as its current understanding and applications have been portrayed. Beside this, current limitations to the implementation of digital twins have been discussed and a comprehensive reference model for the digital twin in design and production engineering has been highlighted. Particularly, this reference model enables the clear differentiation between a conceptual model and its virtual representation for the digital twin. The application of this reference model to geometrical variations management has also been sketched. The benefit of this paper for research as well as industrial applications is the provision of a first theoretical and conceptual framework for the digital twin, which is to be enriched by the design and production engineering community in the future and which may lead to a scientific discussion about the vision of the digital twin and its implementation throughout the product life-cycle.

Fig. 1 .

 1 Fig. 1. The Vision of the Digital Twin throughout the Product Life-Cycle following [11].

Fig. 2 .

 2 Fig. 2. Physical Twin and Reference Model for the Digital Twin (Representation and Abstraction).

Fig. 3 .

 3 Fig. 3. Different Operations on the Physical and the Digital Twin throughout the Product Life-Cycle.

Fig. 4 .

 4 Fig. 4. Digital Twin for Geometrical Variations Management


Junjie Xie
email: xiejunjiejnu@gmail.com

Yuhui Deng
email: tyhdeng@jnu.edu.cn

Ke Zhou

Totoro: A Scalable and Fault-Tolerant Data Center Network by Using Backup Port

Keywords: Data Center, Interconnection Network, Scalability, Fault Tolerance, Backup Port

Scalability and fault tolerance become a fundamental challenge of data center network structure due to the explosive growth of data. Both structures proposed in the area of parallel computing and structures based on tree hierarchy are not able to satisfy these two demands. In this paper, we propose Totoro, a scalable and fault-tolerant network to handle the challenges by using backup built-in Ethernet ports. We connect a bunch of servers to an intra-switch to form a basic partition. Then we utilize half of backup ports to connect those basic partitions with inter-switches to build a larger partition. Totoro is hierarchically and recursively defined and the high-level Totoro is constructed by many low-level Totoros. Totoro can scale to millions of nodes. We also design a fault-tolerant routing protocol. Its capability is very close to the performance bound. Our experiments show that Totoro is a viable interconnection structure for data centers.

Introduction

With the development of information digitization, large amounts of data is being created exponentially every day in various fields, such as industrial manufacturing, ecommerce, and social network, etc. For example, 72 hours of video are uploaded to YouTube every minute [START_REF]Statistics-YouTube[END_REF]. 1 billion active Facebook users upload 250 million photos every day. If these photos are printed and piled, the height would be as tall as 80 Eiffel Towers [START_REF]A Typical Day In the Internet[END_REF]. A report from IDC even shows that 1,800EB data has been created in 2011 with a 40-60% annual increase [START_REF] Gantz | The diverse and exploding digital universe: An updated forecast of worldwide information growth through[END_REF]. As data increases exponentially, the scale of data centers has been increased sharply.

In recent years, governments and multinational corporations are racing to invest amounts of money to build many large data centers. For instance, Google has already had 19 data centers where there are more than 1 million servers. Some corporations, such as Facebook, Microsoft, Amazon, eBay and so on, have hundreds of thousands of servers in their own data centers. In this case, scalability becomes a necessary condition for data centers.

With the increasing scale of data centers, failures become quite common in the cloud environment. Failures from software, hardware, outage or even overheat will have a significant impact upon the running applications. For example, Amazon EC2 and RDS failed for several days, leading to the stoppage of some famous corporations [START_REF]Ten worst cloud crashes in 2011[END_REF]. Google also reports that 5 nodes will fail during a MapReduce job and 1 disk will fail every 6 hours in a 4,000-node cluster running MapReduce [START_REF] Dean | Experiences with MapReduce, an abstraction for large-scale computation[END_REF]. Hence, failures and their damages make fault tolerance a big challenge in the cloud environment.

In current practice, most of data centers are tree-based. At the top of its hierarchy, a tree-based data center provides the Internet services by core-routers or core-switches. However, there are three weaknesses about the top-level switches. Firstly, they can easily become the bandwidth bottleneck. Secondly, if one port fails, it will make its subtrees all isolated. In other words, they are the single points of failure. Thirdly, toplevel switches are so expansive that updating will cause the steep rise in cost. In summary, tree-based structure lacks enough scalability and fault tolerance.

Fat-Tree [START_REF] Al-Fares | A scalable, commodity data center network architecture[END_REF] is an improved tree-based structure. It scales out with a large number of links and mini-switches. By using more redundant switches, Fat-Tree provides higher network capacity than traditional tree-based structures. But the scalability of Fat-Tree is still limited by the ports of switches fundamentally. DCell [START_REF] Guo | Dell: a scalable and fault-tolerant network structure for data centers[END_REF] is a levelbased, recursively defined interconnection structure. It typically requires multiport (e.g., 3, 4 or 5) servers. DCell scales doubly exponentially with the server node degree. It is also fault tolerant and supports high network capacity. But the downside of DCell is that it trades-off the expensive core switches/routers with multiport NICs and higher wiring cost. FiConn [START_REF] Li | FiConn: Using backup port for server interconnection in data centers[END_REF] is also a new server-interconnection structure. It utilizes servers with two built-in ports and low-end commodity switches to form the structure. FiConn has a lower wiring cost than DCell. Routing in FiConn also makes a balanced use of links at different levels and is traffic-aware to better utilize the link capacities. However, the downside of FiConn is that it has lower aggregate network capacity.

Besides the structures mentioned above, there are various interconnection solutions presented in recent years, such as Portland [START_REF] Niranjan Mysore | PortLand: a scalable fault-tolerant layer 2 data center network fabric[END_REF], VL2 [START_REF] Greenberg | VL2: a scalable and flexible data center network[END_REF], CamCube [START_REF] Costa | CamCube: a key-based data center[END_REF] and so forth. These structures have their advantages in some aspects, yet they still have some deficiencies. In contrast to the existing work, we propose a new interconnection structure called Totoro. It utilizes commodity server machines with two ports as FiConn does. When constructing a high-level Totoro, the low-level Totoros use half of their available backup ports for interconnections as well. Totoro and FiConn share the similar principle to place the interconnection intelligence onto servers. In FiConn, all communication between two partitions flows through a unique link. This brings severe forwarding load to the servers at each end of this link. Unlike FiConn, there is no direct link between any two servers in Totoro. All servers communicate with each other through switches. There are multiple links connecting two partitions directly. All the data that flows from one partition to another partition can be distributed to these links. This lowers the forwarding load and makes the transmission more efficient. Totoro scales exponentially with the hierarchical level. A 3-level Totoro can hold more than 1-billion servers by using 32-port switches. Totoro is also fault tolerant, benefiting from multi-redundant links, which provides high network capacity. We also design a fault-tolerant routing mechanism, whose capacity is very close to that of shortest path algorithm (SP) with lower traffic and computation overhead.

2

Totoro Interconnection Network

Totoro Architecture

Totoro is recursively defined. It consists of a series of commodity servers with two ports and low-end switches. We connect N servers to an N-port switch to form the basic partition of Totoro, denoted by Totoro 0 . We call this N-port switch intra-switch. Each server in Totoro 0 is connected to an intra-switch by using one port and the rest of ports are called available ports. If consider a Totoro 0 as a virtual server, we denote the number of available ports in a Totoro 0 as c. Obviously, there is c = N. Next, we connect each Totoro 0 to n-port switches by using c/2 ports. Each Totoro 0 is connected to c/2 switches and each switch is connected to n Totoro 0 s. Now we get a larger partition, which is denoted by Totoro 1 (e.g., in Figure 1). By analogy, we connect n Totoro i-1 s to n-port switches to build a Totoro i in the similar way. Note that, we will never connect switches with switches. We call a switch connecting different partitions an inter-switch. In a Totoro i , switches and links connecting different Totoro i-1 s are called level-i switches and level-i links respectively. Peculiarly, the level of intra-switch is 0.

If the inter-switch has n ports, we note that the number of child partitions in a parent partition is also n. If we denote the number of available ports in a Totoro i as c i , there is c i = c i-1 * n/2. This is because a Totoro i has n Totoro i-1 s and we connect each Table 1. Useful denotations and their meanings in the following text.

Denotation

Meaning

N

The number of ports on an intra-switch. n

The number of ports on an inter-switch. K

The top level in a Totoro.

Totoro i

An ith level Totoro. c i

The number of available ports in a Totoro i .

[a K , a K-1 , …, a i , …, a 1 , a 0 ] A (K+1)-tuple to denote a server, a i < n (0 < i ≤ K) indicates which Totoro i-1 this server is located at and a 0 < N indicates the index of this server in that Totoro 0 .

(u -b K-u , b K-u+1 , …, b i ,…, b 1 , b 0 )
A combination of an integer and a (K-u+1)-tuple to denote a switch, u ≤ K indicates that it is a level-u switch, b i < n (0 < i ≤ K-u) indicates which Totoro u+i-1 this switch is located at and b 0 indicates the index of this switch among level-u switches in that Totoro u .

Totoro i-1 to c i /2 inter-switches (level-i) by using half of its available ports (c i-1 /2). It implies that the number of paths among Totoro i s is n/2 times of the number of paths among Totoro i-1 s. Multiple paths make the routing protocol robust and fault tolerant. Totoro can communicate in the presence of failures with redundant links. Furthermore, the number of high-level links is n/2 times of the number of low-level links means that high-level links will not be the bottleneck of the system and Totoro has high network capacity.

At the structure of Totoro, there are several inter-switches between two partitions. Servers in a Totoro i (0 ≤ i < K) can access servers in another Totoro i directly by multiple paths without any other Totoro i . For instance, in Figure 1, server [0, 1] wants to access [START_REF]Statistics-YouTube[END_REF][START_REF]Statistics-YouTube[END_REF]. Under normal circumstances, we can choose the path [0, 1], (0-0, 0), [0, 0], (1-0), [1, 0], (0-1, 0), [START_REF]Statistics-YouTube[END_REF][START_REF]Statistics-YouTube[END_REF]. Assume that the link between [0, 0] and (1-0) fails, this path is unavailable now. In this case, we can choose another path [0, 1], (0-0, 0), [0, 2], (1-1), [START_REF]Statistics-YouTube[END_REF][START_REF]A Typical Day In the Internet[END_REF], (0-1, 0), [START_REF]Statistics-YouTube[END_REF][START_REF]Statistics-YouTube[END_REF]. It is still the communication between two Totoro 0 s without any other ones. Therefore, the structure of Totoro reduces the accessing distance between servers.

Observing the structure of Totoro, we find that not all servers are connected to inter-switches. In our design philosophy, we retain a large number of available ports for expanding. Thus, our Totoro is open and convenient to be expanded. We propose expanding Totoro by increasing the hierarchical level rather than updating the switches. This helps reduce the costs of devices and management in data centers. Without high-end devices, our Totoro also scales exponentially and we will discuss about this in Section 2.2. In Totoro, we can indicate a server in two ways: Totoro tuple or Totoro ID. Totoro tuple is a (K+1)-tuple [a K , a K-1 , …, a i , …, a 1 , a 0 ]. It indicates where this server is located clearly and it will help calculate the common partition of two servers. For example, servers [0, 0] and [0, 1] in Figure 1, we know that these two servers are in the same Totoro 0 [0] due to their common prefix (i.e., [0]). Totoro ID is an unsigned integer, taking a value from t K (t K is the total number of servers in a Totoro K ). Totoro ID will be used to identify a server uniquely. Note that, the mapping between Totoro tuple and Totoro ID is a bijection. In addition, we denote a switch as a combination of an integer and a (K-u+1

Totoro Building Algorithm

)-tuple, (u -b K-u , b K-u+1 , …, b i ,…, b 1 , b 0 )
. Algorithm 1 gives the Totoro building algorithm, which follows the principle in Section 2.1. The key in Algorithm 1 is to work out the level of the outgoing link of this server (Line 10). Theorem 1 describes the total number of servers in Totoro u : Theorem 1:

Algorithm. 1. Totoro Building Algorithm. 0 TotoroBuild(N, n, K) { 1 Define t K = N * n K 2 Define server = [a K , a K-1 , …, a i , …, a 1 , a 0 ] 3
For tid = 0 to (t K -1) 4

For i = 0 to (K -1) 5 a i+1 = (tid / (N * n i )) mod n 6 a 0 = tid mod N 7

Define intra-switch = (0 -a K , a K-1 , …, a 1 , a 0 ) 8

Connect(server, intra-switch) 9

For i = 1 to K 10

If ((tid -

2 i-1 + 1) mod 2 i == 0) 11 Define inter-switch (u -b K-u , …, b i , …, b 0 ) 12 u = i 13
For j = i to (K -1) 14 b j = (tid / (N * n j-1 )) mod n 15 b 0 = (tid / 2 u ) mod (N / n * (n/2) u ) 16

Connect(server, inter-switch) 17 } Proof: A Totoro 0 has t 0 = N servers. n Totoro 0 s are connected to n-port interswitches to form a Totoro 1 . Hence, there are t 1 = n * t 0 servers in a Totoro 1 . By analogy, a Totoro i (i ≤ u) consists of n Totoro i-1 s and has t i = n * t i-1 servers. Finally, the total number of servers in a Totoro u is t u =N * n u .

3

Totoro Routing

Totoro Routing Algorithm (TRA)

Totoro routing algorithm (TRA) is simple but efficient by using Divide and Conquer algorithm. Assume that we want to work out the path from src to dst: Suppose src and dst are in the same Totoro i but two different Totoro i-1 s. Firstly, there must be a level-i path between these two Totoro i-1 s. We denote this path as P(m, n), which implies that m and src are in the same Totoro i-1 , while n and dst are in the same Totoro i-1 . Then, we work out P(src, m) and P(n, dst) respectively with the same technique. In this pro- cess, if we find src and dst are both in the same Totoro 0, we just return the directed path between them. Finally, we join the P(src, m), P(m, n) and P(n, dst) for a full path. Algorithm 2 follows the whole process mentioned above. The function getNear-estPath just returns a nearest level-k path to the source host.

The SP that we use is Floyd-Warshall [START_REF] Floyd | Algorithm 97: shortest path[END_REF] algorithm. From Table 3, we observe that the performance of TRA is close to the SP under the conditions of different sizes. Although the SP is globally optimal, its computation complexity is as high as O(n 3 ). It is not suitable for routing in data center. Our TRA is efficient enough and much simpler than the SP. Thus, we will build Totoro Fault-tolerant Algorithm based on TRA.

Totoro Broadcast Domain (TBD)

In order to send the packets with correct paths, servers need to detect and share the link states. Although global link states can help servers work out the optimal path, it impossible to share the global link states in data center due to its large scale of nodes. Therefore, we introduce the definition of Totoro Broadcast Domain (TBD) to break up the network. We define a variable called bcLevel for broadcast domain, which means that a Totoro bcLevel is a TBD. The server in a TBD is called inner-server, while the server connected to a TBD with an outgoing link whose level is larger than bcLevel is called outer-server. Take Figure 1 for example, assume that bcLevel = 0. [START_REF] Gantz | The diverse and exploding digital universe: An updated forecast of worldwide information growth through[END_REF][START_REF]A Typical Day In the Internet[END_REF] are the outerservers of Totoro 0 [0]. Servers detect the states of links connected to them and broadcast the states to its intra-switch and inter-switch (if it has) periodically. If a server receives a link state packet, it handles the packet based on the following steps: If this packet has ever been received, then just drop it. Otherwise, save the link states and determine whether the packet comes from inter-switch. If so, broadcast it to the intra-switch. If not, broadcast it to the inter-switch if this server is connected to an inter-switch with a link whose level is smaller than bcLevel.

Then Totoro 0 [0] is a TBD. [1, 0], [2, 0], [3, 0], [1, 2], [2, 2],

Totoro Fault-tolerant Routing (TFR)

In combination of TRA and TBD, we propose a distributed, fault-tolerant routing protocol for Totoro without global link states. Firstly, we give the constraint to bcLevel: bcLevel ≥ log n (2 K /N). It makes sure that every inner-server can find an arbitrary level link in its TBD as well as its link state. We divide the Totoro network into several TBDs and they are connected by links with level ≥ bcLevel + 1. We use Dijkstra [START_REF] Dijkstra | A note on two problems in connexion with graphs[END_REF] algorithm for routing within TBD and TRA for routing between TBDs. Take Figure 1 for instance, assume that bcLevel is 0 and we want to find out the path from src[0, 2] to dst [START_REF]Statistics-YouTube[END_REF][START_REF]Statistics-YouTube[END_REF]. Src and dst are in two different Totoro 0 . By using TRA, we find that a level-1 link between these two Totoro 0 is required. We just get the nearest path P([0, 2], [START_REF]Statistics-YouTube[END_REF][START_REF]A Typical Day In the Internet[END_REF]). In the real routing calculation, we just need to work out the next hop. Note that [START_REF]Statistics-YouTube[END_REF][START_REF]A Typical Day In the Internet[END_REF] is an outer-server of this TBD. Hence, it can be simplified to work out the path from [0, 2] to [START_REF]Statistics-YouTube[END_REF][START_REF]A Typical Day In the Internet[END_REF]. Then by using Dijkstra algorithm, we find that the next hop is [START_REF]Statistics-YouTube[END_REF][START_REF]A Typical Day In the Internet[END_REF]. Furthermore, we add a proxy field to the packet header, which means a temporary destination. If this field is not empty, servers just need to find out the next hop to the proxy by using Dijkstra without TRA. After the packet arrives at the proxy, TRA will be used again to find out the next proxy.

If the proxy is unreachable (e.g., P([0, 2], [START_REF]Statistics-YouTube[END_REF][START_REF]A Typical Day In the Internet[END_REF]) fails), we can set the proxy as [START_REF]Statistics-YouTube[END_REF]0]. Then the failure will be bypassed successfully. In conclusion, TRA will be used to find out the proxy on the nearest path firstly. If it fails, TFR will reroute the packet to another by using local redundant links. Moreover, if there exist several available links, TFR can choose one according to a random algorithm or the link load. Algorithm 3 shows the detailed procedure of TFR.

EXPERIMENT EVALUATION

Evaluating Path Failure

We use simulation to evaluate the performance of Totoro under four types of failures, including link, node, switch and rack failures. In the simulation, we also use SP to compare with our TFR. The SP that we used is based on Floyd-Warshall algorithm and it offers a performance upper bound under the structure of Totoro. The networks where we run TFR and SP are a Totoro 1 (N=48, n=48, K=1, t K =2,304) and a Totoro 2 (N=16, n=16, K=2, t K =4,096). Each Totoro 0 is a rack. Failures are generated randomly and their ratios vary from 2% to 20%. In our simulation, each node routes packets to all the other nodes 20 times. Therefore, each simulation result is an average of 20 running results. Figure 2 plots the path failure ratio versus the node failure ratio. It shows that the performance of TFR is almost identical to that of SP, regardless of the number of servers. The server failure is quite common as mention in Section 1 according to [START_REF] Dean | Experiences with MapReduce, an abstraction for large-scale computation[END_REF]. The remarkable capacity of TFR benefits from the technique of rerouting, which maximizes the usage of redundant links when a node failure occurs.

Figure 3 plots the path failure ratio versus the link failure ratio. We observe that the path failure ratio of TFR increases with the link failure ratio. Our TFR performs well when the link failure ratio is small (i.e., lower than 4%). But it can not perform as well as SP when the link failure ratio increases and the performance gap between them becomes larger and larger. For instance, in the same Totoro 2 (N=16, n=16, K=2), the gap is about 16% (0.21 -0.05) when the link failure ratio is 8%. It rises to 32% (0.43 -0.11) when the link failure ratio increases to 16%. This is because link failure just result in a very few nodes' being disconnected. The SP is global optimal and it always finds out a path from the source to the destination, if it exists. Thus, SP can achieve a good performance even when the link failure ratio is high. But our TFR is not global optimal and not guaranteed to find out an existing path. We also observe that Totoro which holds more servers has a lower path failure ratio. It implies that the integrated capacity of fault tolerance will be more obvious under the condition of a large scale. This enlightens us to improve our TFR because of its huge performance improvement potential on handling link failure. Figure 4 plots the path failure ratio versus the switch failure ratio. It shows that TFR performs almost as well as SP in Totoro 1 (N=48, n=48, K=1). But the performance gap between TFR and SP becomes larger and larger with the increase of switch failure ratio in the same Totoro 2 (N=16, n=16, K=2). We also observe that path failure ratio of SP is lower in a larger-level Totoro. It means that more redundant high-level switches help bypass the failure rather than become the single points of failure. Given this, our future work will be devoted to improving the performance of TFR under switch failure.

In our simulation, we also study the relationship between the rack failure and the path failure. We select a rack randomly and make all the nodes and links in this rack fail. Figure 5 plots the path failure ratio versus the rack failure ratio. It shows that in a low-level Totoro (e.g., Totoro 1 ), TFR achieves results very close to SP. But the capacity of TFR in a relative high-level Totoro (e.g., Totoro 2 ) could be improved. However, TFR performs still well enough when the rack failure ratio is lower than 10%.

Evaluating Network Structure

In this section, we compare Totoro with traditional Tree structure and several recent structures of Fat-Tree, DCell and FiConn to evaluate our network structure. Table 4 summarizes the topological property comparison result of different network structures. We denote the total number of servers as T.

The node degree of Totoro or FiConn approaches to 2 as k grows, but will never reach 2. They all achieve a smaller node degree than DCell, which means a lower deployment and maintenance overhead. Furthermore, Totoro and FiConn are always incomplete and highly scalable by using available backup ports.

As we all know, the smaller the diameter is, the more efficient the routing mechanism will be. The diameter of Tree is 2log d-1 T, where d is the number of switch ports. Fat-Tree has a diameter of 2log 2 T. The upper bound of diameter of DCell is 2log n T-1. And the diameter of FiConn is O(logT). They all achieve a relative small diameter. It seems that Totoro has a large diameter. But it is not accurate in practice. A low-level Totoro can hold hundreds of thousands or even millions of servers, e.g., a Totoro 2 with N = n = 48 has 110,592 servers and a Totoro 3 with N = n = 32 has 1,048,576 servers. However, the diameters of Totoro 2 and Totoro 3 are only 10 and 18, respectively. In addition, even though the diameters of Tree and Fat-Tree are both small,

-- 2log d-1 T 1 Fat-Tree -- 2log 2 T T/2 DCell k + 1 <2log n T-1 T/4long n T FiConn 2 -1/2 k O(logT) O(T/logT) Totoro 2 -1/2 k O(T) T/2 k+1
they can not be comparable with Totoro since their scalability is limited by the number of switch ports. Tree structure has a bisection width of 1 because each server or switch has only one path to the upper node. The failure of one path will make their subtrees all isolated. What's more, high-level links will become the bandwidth bottleneck. Fat-Tree overcomes these problems by using more redundant switches near the root in its hierarchy. It has a large bisection width of T/2. DCell has a large bisection width of T/4long n T since it has more ports on a server. And the bisection width of FiConn is O(T/log(T)). Totoro also has a relative large bisection width of T/2 k+1 . As we have mentioned above, a low-level Totoro can hold a large number of servers. When we take a small number of k, the bisection width is large, e.g., BiW=T/4, T/8, T/16 when k = 1, 2, 3, respectively. A large bisection width means a fault-tolerant and resilient structure. Thus, we can draw a conclusion that Totoro is fault-tolerant both in the topological analysis and from the path failure evaluating above. In addition, a relative large bisection width also leads to a higher network capacity.

In a word, Totoro gains the good scalability, fault tolerance and relative high network capacity. These attractive properties all meet the current requirement of data centers. Hence, our Totoro is a viable interconnection solution for data centers.

Conclusion

Structures neither proposed in the area of parallel computing nor based on tree hierarchy in current practice meet the requirements of scalability and fault tolerance. This drives us to present a new structure called Totoro. Then we detail the physical structure of Totoro. It is hierarchically and recursively defined. Through topological property analysis we know that Totoro scales exponentially and it is convenient to expand Totoro by using backup built-in Ethernet ports. In addition, we elaborate a distributed and fault-tolerant routing protocol called TFR, which is designed to handle various failures. The experiments show that its capability of handling fault tolerance is very close to that of the SP, especially in the presence of server failure. Furthermore, TFR significantly reduces the network traffic of sharing link states and the computation overhead. Lastly, we compare Totoro with other interconnection structures in some aspects, including node degree, diameter, and bisection width. It shows that Totoro is able to satisfy the demands of scalability and fault tolerance. In a word, topological analysis, experiments and comparison prove that Totoro is a viable interconnection solution for data centers. One problem faced by Totoro is the failure handling under some kinds of failures. Failure handling depends largely on fault-tolerant algorithm.

We have seen the huge performance improvement potential from TFR. In the future work, we will be devoted to solving this problem by using more techniques, such as multiplexing and retouring based on remote proxy.

Fig. 1 .

 1 Fig. 1. A Totoro 1 structure with N = 4, n = 4. It is composed of 4 Totoro 0 . Each Totoro 0 has 4 servers and an intra-switch with 4 ports. 4 Totoro 0 connect through 2 inter-switches.

Fig. 2 . 3 .

 23 Fig. 2. Path failure ratio vs. node failure ratio. Fig. 3. Path failure ratio vs. link failure ratio.

Fig. 4 . 5 .

 45 Fig. 4. Path failure ratio vs. switch failure ratio. Fig. 5. Path failure ratio vs. rack failure ratio.

Table 2 .

 2 Total number of servers in Totoro u with different N, n, u.

	N	n	u	t u
	16	16	2	4096
	24	24	2	13824
	32	32	2	32768
	16	16	3	65536
	24	24	3	331776
	32	32	3	1048576

Table 3 .

 3 The mean value and standard deviation of path length in TRA and Shortest Path Algorithm in Totoro u of different sizes. M u is the maximum distance between any two servers in Totoro u .

				Algorithm. 2. Totoro Building Algorithm.
	0 TotoroRoute(src, dst) {
	1	If (src == dst)
	2	Return NULL
	3	Define k = lowestCommonLevel(src, dst)
	4	If (k == 0)		// in the same Totoro 0
	5	Return P(src, dst)
	6	Else
	7	Define P(m, n) = getNearestPath(src, k)
	8	Return TotoroRoute(src,m)+P(m,n)+TotoroRoute (n,dst)
	9 }
								Shortest Path
	N	n	u	t u	M u	TRA		Algorithm
						Mean	StdDev	Mean	StdDev
	24	24	1	576	6	4.36	1.03	4.36	1.03
	32	32	1	1024	6	4.40	1.00	4.39	1.00
	48	48	1	2304	6	4.43	0.96	4.43	0.96
	24	24	2	13824	10	7.61	1.56	7.39	1.32
	32	32	2	32768	10	7.68	1.50	7.45	1.26

Table 4 .

 4 Topological property comparison of different network structures.

	Structure	Degree	Diameter	Bisection Width
	Tree

Acknowledgments

We would like to thank the anonymous reviewers for helping us refine this paper. Their constructive comments and suggestions are very helpful. This work is supported by the National Natural Science Foundation (NSF) of China under grant (No.61272073, No. 61073064), the Scientific Research Foundation for the Returned Overseas Chinese Scholars (State Education Ministry), the Educational Commission of Guangdong Province (No. 2012KJCX0013), the Science and Technology Planning Project of Guangdong Province (No.2012A080102002), the Science and Technology Planning Project of Guangzhou (No. 2012J4100109), Open Research Fund of Key Laboratory of Computer System and Architecture, Institute of Computing Technology, Chinese Academy of Sciences (CARCH201107). The corresponding author of this paper is Yuhui Deng.


Dr Constantine E Kyritsis
email: kyritsis@softlab.ntua.gr

Alternative algebraic definitions of the Hessenberg natural operations in the ordinal numbers

§0. Introduction This is a series of five papers that have as goal the definition of topological complete linearly ordered fields (continuous numbers) that include the real numbers and are obtained from the ordinal numbers in a method analogous to the way that Cauchy derived the real numbers from the natural numbers.We may call them linearly ordered Newton-Leibniz numbers. The author started and completed this research in the island of Samos during 1990-1992. Seven years later (1999) he discovered how such numbers can be interpreted as fields of random variables (stochastic real numbers) that links them to applications of Bayesian statistics, stochastic processes and computer procedures.

From this point of view it turns out that the ontology of infinite is the phenomenology of changes of the finite. In particular the phenomenology of stochastic changes of the finite can be formulated as ontology of the infinite .He hopes that in future papers he shall be able to present this perspective in detail.

It is a wonderful perspective to try to define the Dirac's deltas as natural entities of such stochastic real numbers. If in the completion of rational numbers to real numbers we ramify the equivalence relation of convergent sequences to others that include not only where the sequences converge (if they converge at the same point) but also how fast (if they converge in the same way ,an attribute related also to computer algorithms complexity) ,then we get non-linearly ordered topological fields that contain ordinal numbers (certainly up to ω a , a= ω ω ) and are closer to practical applications. This approach does not involve the random variables at all, but involves directly sequences of rational numbers as "Newtonian fluxions".

This creation can be considered as a model of such linearly ordered fields (up-tocharacteristic ω a , a= ω ω ) ,when these linearly ordered fields are defined axiomatically. This gives also a construction of the real numbers with a set which is countable. This does not contradict that all models of the real numbers are isomorphic as the field-isomorphism is not in this case also an -isomorphism so the Cauchy-real numbers and such a model still have different cardinality. If we want to define in this way all the Ordinal real numbers , then it is still possible but then this would give also a device for a model of all the ZFC-set theory! And such a model is indeed possible: By taking again sequences of non-decreasing (in the inclusion) finite sets of ZFC , and requiring that any property ,relation or operation if it is to hold for this set-sequence it must hold finally for each term of the sequence and finite set. In other words we take a minimality relative to the axiom of infinite for every set of it. It is easy to prove that the (absolute) cardinality of such a model is at most 2 ω , that is at most the cardinality of the continuum. We could conceive such a model as the way a computer with its algorithms , data bases tables etc would represents sets of ZFC in a logically consistent way. There is no contradiction with the 2nd-incompletness theorem of Gödel as the argument to prove that it is a model of ZFC-set theory is already outside ZFC-set theory (as are also the arguments of Gödel ,or of Lowenheim-Skolem that gives a countable model of ZFC-set theory). In particular it is proved that the Hessenberg natural operations are free finitary operations ; We make use of rudimentary techniques relevant to K-theory and Universal Algebra .

The main application of the present results is in the definition of the ordinal real numbers.(see [ Kyritsis C.E.1991] .By making use of the present results and techniques it is proved in [Kyritsis C.E.1991] that all the three techniques and Hierarchies of transfinite real numbers ,see [ Glayzal A 1937],of surreal numbers, see [START_REF] Conway | On numbers and games Academic press[END_REF]], of ordinal real numbers see [ Kyritsis C.E.1991], give by inductive limit or union, the same class of numbers ,already known as the class No. We refer to the class No as "the totally ordered Newton-Leibniz realm of numbers").

Two algebraic characterisations of the Hessenberg operations in the ordinal numbers.

Let us denote by F a linearly ordered field of characteristic ω (also said of characteristic 0).Let us denote by h a mapping of an initial segment of ordinal numbers, denoted by W(a),in F such that it is 1-1, order preserving and h(0)=0, h(1)=1, h(s(b))=b+1,where s(b) is the sequent of the b , b<a, the b+1 is in the field operations the set h(W(a)) is closed in the field addition and multiplication . We shall call field-inherited operations in the ordinal numbers of W(a), the operations induced by the field, in the initial segment W(a).

(For a reference to standard symbolisms and definitions for ordinal numbers, see [START_REF] Cohn | Universal Algebva Harper -Row[END_REF] p.1-36 also [ Kutatowski K.-Mostowski A. 1968]).

The following properties hold for these field-inherited abelian operations for the ordinals of w(a) ( in that case, it is needless to say that a is a limit ordinal).

Lemma 1. For the field-inherited abelian operations in the initial segment w(a) of ordinal numbers, the followings hold (x,y,z,c,x',y', w(a)).

y x c c y c x a w c y x c y c x                0 ) (
The proof of the previous lemma is direct from the properties of a linearly ordered field.

We mention two more properties that they will be of significance in the followings paragraphs. 8) The W(x.y) is cofinal set with the

h -1 ({h(y)h(w(x))+h(x)h(w(y))-h(w(x)).h(w(y))})
and we write

cf(w(x.y)) = cf h -1 ({h(y)h(w(x))+h(x)h(w(y))-h(w(x)).h(w(y))})
To continue our argument we need a many-variables form of transfinite induction.

Lemma 2. (many-variables transfinite induction)

Let A w(a 1 )x...xw(a n ) such that

1. (0,...,0) A 2. For every (b 1 ,...b n ) w(a 1 )x...xw(a n ) it holds that w((b 1 ,...,b n )) A  (b 1 ,...,b n ) A.        i I n   1,...,      i I n   1,...,      
By 1.2. we infer that A = w(a 1 )x...xw(a n ).

Lemma 3. (many-variables definition by transfinite induction)

Let a set A and ordinal numberss a 1 ,...,a n . Let a set denoted by B, such that it is sufficient for inductive rules h BA :

This means that :

a)

The set B is a set of functions, denoted by and defined on simulteneous initial segments with values in A. In order to save space and because the proofs are not directly relevant to our subject we will not give the proofs of lemma 2 and 3 but we will mention that they are analogous, without serious difficulties, to the ones with one-variable only (see e.g. [ Kutayowski K. -Mostowski A 1968], [ Lang S.1984]).

 A             n n b b w b b xw x a w b b A B n n  ... ,..., , 1 1 ,..., ,..., 1 1      f b b n 1 ,...,   f b b n 1 ,...,   f b b n 1 ,...,         n n c c w b b f ,... ,..., 1 1       n n xw x w c c   ... ,..., 1 1    n c c f ,..., 1   n c c f ,..., 1      f B w n    1 ,...,   f b b n 1 ,...,              n c c w n n n b b c c b b f w f ,..., 1 1 1 1 ,..., ,... ,...,                g b b f b b b b w n b b n n n n 1 1 1 1 1 ,..

Proposition 4. (Uniqueness)

Any two pairs of field-inherited operations in the initial segment w(a) of ordinals, satisfying properties 7,8 of lemma 1 (a is a limit ordinal ) are isomorphic .

Proof: Let a monomorphic embedding denoted by h of w(a), as is described in the beggining of the paragraph in two linearly ordred fields denoted by F 1 , F 2 .

Let the two pairs of field inherited operations in w(a) be denoted by ((+,.) ( ) respectively. They satisfy the properties 0.1.2.3.4.5.6.7.8.of lemma 1 . Suppose that the operations +, coincide for the set where .

Then by property 7 (by the hypothesis of transfinite induction)

=               n n b b w f h b b f ,..., ,..., 1 1 ,      2 1 ,b b w    w  2                       b b w w b b w b xw b b xw b w b x b 1 2 1 2 1 2 1 2 1 2 , ,            b b s b w b w b b 1 2 1 2 1 2             s b w b w b b b b 1 2 1 2 1 2      ;
Where by S(A) we denote the sequent of the set A .Thus by lemma 2 the operations +, coincide on w(a)xw(a).

Then the set w(a) is an ordered abelian monoid relative to addition, with cancelation law.

The Grothendieck groups of w(a) for both +, and coincide, and we denote it by k(w(a)) (see for the definition of Grothendieck group [START_REF] Lang | Laugwitz Detler 1983] Ω Calculus as a Generalization of Field Extension. An alternative approach to non-Standard analysis "Recent developments in non-standard analysis[END_REF] exercises 1. 2. 3.) and [ Frankel A.A.1953] pp. 591-594 also [START_REF] Conway | On numbers and games Academic press[END_REF]] ch2 p. 27-28).

The way in which the Hessenberg operations are defined, traditionally , depends on the standard non-commutative operation on ordinals.

In order to define the Hessenberg-Conway operations in the traditional way ,we remind that :

    ,                         b b s h h b h w b h w b h b h w b h w b 1 2 1 1 2 1 2 1 2                                          2 1 2 1 2 1 2 1 1 ) , b b b w h b w h b h b w h b w h b h h s            ,

Lemma 6 (Cantor normal form).

For every ordinal a there exists a natural number n and finite sequences : b 1 ,. The natural product, denoted by α(.)b is defined to be the ordinal arising by multiplication (using distributive and associative laws) from the Cantor normal forms of a and b and by using the rule: ω x (.)ω y =ω x(+)y to multiply powers of ω. As a result we get for instance that Remark 7

1) The normal form of a can also be written in the standard Hessenberg-Conway operations that is

2) The sum a(+)b is an increasing function of a and b.

3) If and then for ordinals ζ, η, α and conversely if an ordinal j satisfies the condition: "if ξ<j and η<j then ξ.η<j" then there exists an ordinal number α such that ;we call ordinal numbers of the type principal ordinals of the Hessenberg operations.(see [ Kutatowski K.-Mostowski A. 1968] ch vii paragraph 7,p 253) This has also as a consequence that we define the Hessenberg-Conway

      a a n b b n 1 1 ...               1 1 1 1 p p b q q n n n n ... ... ;                  b p q p q n n n 1 1 1 ... .                 1 1 . ... . . p p n n                .         
natural operations only for initial segments of the type W for some ordinal number α (we will call them principal initial segments ).

4) The Hessenberg-Conway natural operation restricted on the set of Natural numbers coincide with the ordinary sum and product of natural numbers.

5) The operation "powers of ω" , through the Hessendberg-Conway natural operation, can be defined as follows: a) ω (0) = 1 ω (1) = ω if ξ is a limit ordinal ω (ξ) = sup ω (η) η<ξ b) If ξ is not a limit ordinal then there exists an ordinal η with η(+)1= s(η)=ξ and we define ω (ξ) = ω η (.)ω.

It holds, (this happens especially for the base ω), that these "natural powers" of ω coincide with the standard powers of ω defined through the standard non-commutative multiplication of ordinal numbers (this can be proved with transtinite induction since ω η .ω=ω (η) ω. This gives us the right to express any ordinal number α in Cantor normal form, exclusively with natural operations: 6) Also we notice that, the natural difference denoted by a (-) b, of two ordinals a, b in Cantor normal forms , is defined only if p 1 q 1 ... p n q n . 7) We notice that if ξ i <ξ j for two ordinals then but also for every pair of non-zero natural numbers a,b. (in the standard non-commutative operations on ordinals). But this has as consequence that the ordering of a finite set of ordinal numbers in Cantor normal form (normalizing the Cantor normal forms by adding terms with zero coefficients so that all of them have the same set of exponents) is

                          1 1 . ... . p p n n             a p p n n        1 1 . ... .             b q q n n        1 1 . ... .     i j      i j a b .
.  isomorphic (similar) to the lexicographical ordering of the coefficients of the normal forms.

Proposition 8. For every principal initial segment of ordinal numbers, the Hessenberg natural operations satisfy the properties 0.1.2.3.4.5.6.7.8. of lemma 1.

Remark.

From the moment we have proved the properties 0.1.2.3.4.5.6. for the natural operations in the principal initial segment w(a), there is the Grothendieck group k(w(a)) of the monoid relative to sum, w(a) such that the w(a) is monomorphicaly embedded in k(w(a) (because of cancelation law) and also there is an ordering in k(w(a)) that restricted on w(a) coincides with the standard ordering in w(a).

Then the difference that occurs in property 8 has meaning and also the statement of property 8 itself has meaning (see [START_REF] Lang | Laugwitz Detler 1983] Ω Calculus as a Generalization of Field Extension. An alternative approach to non-Standard analysis "Recent developments in non-standard analysis[END_REF]] Ch I §9 p. 44).We denote by h the monomorphism of the W(a) in the K(W(a)) .

Proof. The properties 0.1.2.3.4. are directly proved from the definition of the natural operations. Let us check the property 5. Namely , the cancelation laws. Let us suppose that y,x,c, are ordinal numbers with y,x,c for some ordinal a and their Cantor normal form , in natural operations , are

p i , c i , y 1 No then hence   w                x p p n n        1 1 . ... .             c c c n n        1 1 . ... .             y q q n n        1 1 . ... .                    x c p c p c n n n           1 1 1 . ... .                   y c q c q c n n n           1 1 1 . ... .
x(+)c=y(+)c  p i +c i = q i +c i i = 1,...,n and by cancelation law for addition in natural numbers we deduce that p i =q i i=1,...,n hence x = y. Also and and if c  0 and x(.)c = y(.)c then p i .c j = q i .c j with not all of c j equal to zero. Say , then

for every i = 1,...,n hence p i = q i and x=y.

Let us check the property 6. The first part of property 6 is immediate from Remark 7, 2.

Let, furthermore, x',y' with Cantor normal form (changing the ξ i , in order to have the same exponents for all x, y, x', y') with p i ',q i ' No and with summation interpreted as natural sum. By hypothesis x'>y', x>y.

Then and and the coefficient of the monomial of greatest exporent of x(.)x'(+)y(.)y' is p 1 p 1 '+ q 1 q 1 ' and of x(.)y'(+)y(.)x' is p 1 q 1 '+q 1 p 1 '. But p 1 p 1 ' + q 1 q 1 ' -p 1 q 1 ' -q 1 p 1 ' = p 1 (p 1 '-q 1 ') -q 1 (p 1 '-q

1 ') =         x c p c i j i j i j n . . .         1         y c q c i j i j i j n . . .         1 c j 0 0  p c q c i j i j . . 0 0       w          x p n i i   1 .         y q n i i   1 .          x x p p i j ij i j . . .                 y y q q i j ij i j . . .        
(p 1 -q 1 ). (p 1 '-q 1 ') > 0 which is a product of the positive factors p 1 -q 1 , (p 1 '-q 1 ') hence it is positive. By Remark 7,7 because p 1 q 1 ' + q 1 q 1 ' > p 1 q 1 ' + q 1 p 1 we deduce that x(.)x'(+)y(.)y'>x(.)y'(+)x'(.)y. Next we prove the property 7. Let x' as before but also satisfying x' w(x) that is x'<x. Then by property 5 we deduce that w(x)+y w(x+y).

Conversely let z<x+y z w(x+y). Let the Cantor normal form of z be (we rearrange appropriately the normal forms of x, x', y, y', Z) with r i No. From the last inequality we get that in the lexiographical ordering it holds that (r i ,...,r n )<(p 1 +q 1 ,...,p n +q n )(*)

Let and Let and Then the following ordinals are defined: z 1 '(-)z, z 1 '(-)y, z 2 '(-)z, z 2 '(-)y, and also by Remark 7,7. It holds that zz 1 ' zz 2 ', yz 1 ' xz 2 '. From the inequality (*) and the inequality (**) q i  p i + q i i = 1,...,n and the definition of k i we infer that it holds in the lexicographical ordering, the inequality (k 1 ,...,k n )  (p 1 +q 1 ,...,p n + q n ) similarly (λ i ,…,λ n )  (p 1 + q 1 ,...,p n + q n ). Hence by Remark 7.7. it holds that z 1 'x(+)y and z 2 'x(+)y If for both z 1 ', z 2 ' holds that z 1 '=x(+)y=z 2 '. Then {r i , q i }= {r i , p i }=p i + q i , hence r i = p i + q i i=1,...,n.

But then z=x(+)y ,contradiction.

Let us suppose then, that z 1 '<x(+)y.

Then if z" = z 1 '(-)y by the last inequality we get that z"(+)y = z 1 '(-)y(+)y = z 1 ' < x(+)y or z"(+)y < x(+)y.

That is we proved that for every z w(x+y) there is z" an other ordinal with zz"(+)y<x+y. If z"x then z"(+)yx(+)y contradiction, hence z"<x that is z" w(x) and z"(+)y w(x)+y. From this and also that w(x)+yw(x+y) ,that we have already proved ,we deduce that w(x+y) and {w(x)+yx+w(y)} are cofinal sets; we write cf(w(x+y))=cf({w(x)+yx+w(y)}) . In other words we haved proved the property 7.

     z r n i     1 1 .    k r q i i n i i    max , 1    i i n i i r p    max , 1 z k i n i i 1      z i n i i 2       max i max i   
Let us prove the property 8. As we have already remarked the difference is to be understood in the extension of the additive monoid w(a) into the linearly ordered Grothendick group k(w(a)). The ordering in k(w(a)) is defined by: (x,y)(x',y')x+y'x'+y.

Where by (x,y) we denote the equivalence class of the free abelian group generated by We make clear that h -1 ({h(x)(.)h(w(y))(+)h(w(x))(.)h(y) -h(w(x))(.)h(w(y))}={v|v w(α) and v =h -1 (h(x)(.)h(y)'(+)h(x')(.)h(y) -h(x')(.)h(y')) with x' w(x) y' w(y) and x,y w(a)}.

By the property 6 we get that h(x)(.)h(y')

(+)h(x')(.)h(y) <h(x)(.)h(y)(+)h(x')(.)h(y') hence h(x)(.)h(y')(+)h(x')(.)h(y) -h(x')(.)h(y') < h(x)(.)h(y)
hence h -1 ({h(x)(.)h(w(y))(+)h(w(x))(.)h(y) -h(w(x))(.)h(w(y))}}  w(x(.)y).

Conversely, let, z w(x(.)y), that is z<x(.)y.

If x(.)y = then we also write for the normal form of z: z = and r ij No. By Remark 7,7. We deduce that in the lexicographical ordering it holds that (r 11 ,...,r ij ,...,r n,n ) < (p 1 p 1 ,...,p i p j ,...,p n .p n ). It is sufficient to prove that for every (r 11 ,...,r ij ,...,r n,n )< (p 1 p 1 ,...,p i p j ,...,p n .p n ) there are (p 1 ',...,p n ') and

(q 1 ',...,q n '), p i , q j No with (p 1 ',...,p n ')< (p 1 ,...,p n ) and (q 1 ',...,q n ')< (q 1 ,...,q n ) such that (r 11 ,...,r ij ,...,r n,n )  (p 1 q 1 '+p 1 'q 1 -p 1 '.q 1 ',...,p n .q n '+p n '.q n -p n '.q n ') < p 1 .q 1 ,..., p n .q n ).

But the property 8 holds for a=ω, that is for the natural numbers. Hence there are p 1 ', q 1 ' with p 1 ' < p 1 q 1 ' < q 1 and r 11  p 1 q 1 '+p 1 'q 1 -p 1 '.q 1 ' < p 1 ' q 1 and completing with arbitrary p i ', q i ' i = 2,...,n) that give positive the terms p i q j ' + p i 'q j -p i 'q j ' (by elementary arithmetic of natural numbers this is always possible) we define

               1    i j n i i i j p q , . .        1    i j n ij i j r , .   x' =
and y' = .

By the lexicographical ordering it holds that x' w(x), y' w(y) and h(z)  h(x)(.)h(y')(+)h(x')(.)h(y) -h(x')(.)h(y') <h(x)(.)h(y). Hence the sets W(x(.)y) and h - 1 ({h(x)(.)h(w(y)) (+) h(w(x))(.)h(y) -h(w(x))(.)h(w(y))}) are cofinal and we write cf(w(x(.)y)) = cfh -1 ({h(x)(.)h(w(y)) (+) h(w(x))(.)h(y) -h(w(x))(.)h(w(y))}). This is the end of the proof of the property 8. Q.E.D.

Corollary 9 (first characterisation )

Every pair of operations in a principal initial segment of ordinal that satisfy the properties 0.1.2.3.4.5.6.7.8 of lemma 1 ,.is unique up-to-isomorphism and coincides with the Hessenberg natural operations .

Remark:

The difference that appears in the property 8 is defined as in the remark after the proposition 8 .

Proof:Direct after the proposition 4 and 8 Q.E.D.

.

Corollary 10.(Second characterisation )

Every pair of field -inherited operations in a principal initial segment of ordinals, w(a) that satisfy the properties 7. 8. coincides with the natural sum and product of Hessenberg .

  In this paper are studied the Hessenberg operations in the ordinal numbers, from an algebraic point of view. The main results are the characterisation theorems 9,10 . They are characterisations of the Hessenberg operations as a) field-inherited operations in the ordinal numbers,that satisfy two inductive properties .(see proposition 10) b) operations that satisfy a number of purely algebraic properties, that could be called in short operations of a well-ordered commutative semiring with unit ;(see Lemma 0, proposition 9). In a next paper I shall give two more algebraic characterisations of the Hessenberg operations as c) operations defined by transfinite induction in the ordinal numbers and by two recursive rules , d) operations of the free semirings in the category of abelian semirings; or as the operations of the formal polynomial algebras of the category of abelian semirings. These characterisations of the Hessenberg operations are independed of the standard noncommutative operations of the ordinal numbers and can be considered as alternative and simpler definitions of them (especially the c),d)).

  x>y, x'>y' then x+x'>y+y', and xx'+yy'>xy'+yx'

7)

  The w(x+y) is a cofinal set with the {w(x)+x x+w(y)}and we write cf(w(x+y)) = cf{w(x)+y x+w(y)}.

  Let a i i = 1,...,n n N ordinal numbers and (b 1 ,...b n ) w(α i )x...xw(α n ). We define as simultenous initial segment of n-variables defined by (b 1 ,...b n ), the set w((b 1 ,...b n )) = w(b 1 )x...x{b 1 }x...xw(b n ) for every I {1,...n},or w((b 1 ,...,b n ))= w{b 1 }x...xw{b i )x...x{b n } for every I {1,...n} with I  .

  and let us denote the value of f at (b 1 ,...,b n ) with . Let us suppose that it holds that whenever c 1  b 1 ,b' 1 ,...,c n  b n ,b' n , (b 1 ,...,b n ),(b' 1 ,...,b' n ) w(α 1 )x...xw(α n ) then Then let us suppose that we get as a consequence that the function defined by , belongs to B It holds that for every function h:B

  ] Ch1 §4 p. 44 or[START_REF] Cohn | Universal Algebva Harper -Row[END_REF] ch vii §3 pp 263 ). Thus also the opposite -x of an element x of w(a) is the same in the Grothendieck group k(w(a)) of w(a) for both the two operations + and . Suppose also that the operations coincide for the set w ((b 1 , b 2 )). Then by property 8 (because +, and are isomorphic and the hypothesis of transfinite induction for . Hence by lemma 2 the two operations coincide on the whole set w(a)xw(a) Q.E.D. The next step is to find the relation of field-inherited operations in an initial segment of ordinals with the Hessenberg operations . It will turn out that, if they satisfy the properties 7.8.of lemma 1 ,then they are nothing else than the Hessenberg-Conway natural sum and product (see [Kutatoski K.Mostowski A. 1968 ] ch VII §7 p. 252-253

  w(a), which is denoted by F a,b (w(a)) (k(w(a)) = F a,b (w(a))/ ([x+y]-[x]-[y])), in the process of taking the quotient by the normal subgroup generated by the elements of the form [x+y]-[x]-[y] in F a,b (w(a)) (the corresponding generator of x w(a), in F a,b (w(a) we denote by [x]), that is defined by the representative x+(-y). Needless to mention that the natural difference in w(a), isn't but an instance of difference in k(w(a)).

(

  For the existence of field-inherited operations in the ordinal numbers see[C Conway J.H.1976 ] ch note pp 28 .)Proof:The proof is immediate from proposition 4 and 8.Q.E.D.Remark.11It seems that N.L.Alling in his publications: the existence of real closed Fields that are η α -sets of power ω α Transactions Amer.Math.Soc. 103 (1962) pp 341of Analysis over Surreal number Fields .Math. studies 141 North-Holland 1987. he is unaweare that if an initial segment of ordinals is contained in a set-field and it is cofinal with the field ,(and it induces the Hessenbeg operations in it) then it has to be an initial segment of a principal ordinal that is of type (see [Kutatowski K-Mostowski A.1968] ch VII §7 p. 252-253 exercises 1. 2. 3.) Thus properties 0.1.2.3.4.5.6.7.8. can be taken as an axiomatic definition of the Hessenberg operations without having to mention the non-commutative ordinal operations. In a forthcoming paper, I will be able to prove the non-contradictory of properties 0.1.2.3.4.5.6.7.8. (actually the existence in Zermelo-Frankel set theory, of the operations +,.) without using the non-commutative ordinal operations,neither field-inherited operations. but through transfinite induction and other methods of universal algebra . Bibliography [ Bourbaki N. 1952] Elemente de Mathematique algebre, chapitre III Hermann Paris 1948, chapitre VI Hermann Paris 1952.   

List of special symbols

ω

: Small Greek letter omega, the first infinit number.

α, b : Small Greek letter alfa, an ordinal.

Ω 1 : Capital Greek letter omega with the subscript one.

(x)

: Aleph of x, the cardinality of the set X.

N: the fisrt capital letter of the Hebrew alfabet.

: Natural sum and product of G. Hessenberg plus and point in parenthesis.

Abstract

This paper proves prerequsite results for the theory of Ordinal Real Numbers. In this paper, is proved that any field-inherited abelian operations and the Hessenberg operations ,in the ordinal numbers coincide.It is given an algebraic characterisation of the Hessenberg , operations ,that can be described as an abelian, well-ordered,double monoid with cancelation laws.

Key words

Hessenberg natural operations (in the ordinal numbers) ordinal numbers semirings inductive rules transfinite induction