Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1998-12-08
2002-07-02
Najjar, Saleh (Department: 2154)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S201000, C709S241000, C709S241000, C709S241000
Reexamination Certificate
active
06415333
ABSTRACT:
This application claims priority under 35 U.S.C. §§119 to Application No. 9704565-2 filed in Sweden on Dec. 8, 1997; the entire content of which is hereby incorporated by reference.
BACKGROUND
The present invention relates to a distributed communication system which comprises a number of nodes and said nodes are interconnected via an interconnection network. Each node comprises a number of resources such as for example processing resources, in/output resources, storing resources and distributed applications are executed through sending of messages between the resources in said nodes. The invention also relates to a node in a distributed network configuration, which node comprises a number of resources and communicates with other nodes via said interconnection network.
The invention still further relates to a method for sending messages in a distributed communication system comprising a number of nodes interconnected via an interconnecting network wherein each node comprises a number of resources. The invention also relates to a method of providing communication among user applications executing at resources located in different nodes in a distributed network through the sending of messages.
In a distributed system, which means a system based on a computer platform comprising a number of computer nodes interconnected through an interconnecting network a number of specific problems arise which mainly are related to the communication between resources or entities such as processes, threads, queues, residing at different nodes. Such problems among others relate to the communication between resources or entities, i.e. what operations are/should be available for communication and what are the semantics of such operations. Another issue relates to the detection of failures in a computer node and how the system reacts thereon. Still another important issue relates to the adaption of the system to changes in the available resources such as for example when nodes are added, removed etc.
Systems implementing location transparent message passing are known. Location transparent message passing means that an entity or a resource which sends a message to another resource (a process, a thread or similar) in a distributed system does not have to know anything about the actual location of the receiving entity but merely a name is used to refer to the receiving entity and underlying software layers handle the location dependent parts of the communication. Basically two different types of location transparent message passing are known. Depending on the name that is used slightly different semantics in the message passing procedures are produced.
In a first case, the name refers to a specific resource or entity which has a particular name. In that case the name is bound to the specific entity and the name is regarded invalid if the actual entity disappears even if another entity reappears under one and the same name. This means that the life time of the name and the entity it denotes is the same.
The second case relates to a name referring to any entity which has the particular name. This means in practice that an entity carrying a given name may disappear and a new entity may be created using the same name. Both these kinds of naming provides for location transparency but they differ in the way entities or resources may relocate in the system. In the first case only migration is permitted which means that an entity or a resource is actually moved and it does not allow destruction of an entity at one location and creation of a new entity at a new location which however is allowable in the second case. Most of the distributed systems are generally location transparent or even weaker which means that both the name and the location of the receiving entity has to be given. U.S. Pat. No. 5,133,053 shows an example on a system implementing location transparent message passing.
However, even if location transparent message passing actually is implemented this does not enable the provision of a truly scalable and fault tolerant distributed system. Scalability and tolerance to failures are two related properties since both of them are concerned with the behaviour of the system when changes occur in the available resources of the system. The same mechanisms are involved irrespectively of whether a resource such as for example an entire computer node is removed or whether it is added. Adaption means that an application should start employing an added node which means that it, or rather the entities residing on it, should become visible in the address space that is used when communicating in the system. Adaption means that the entities which existed on a removed node also should disappear from the communication address space.
FIG. 1A
illustrates a location transparent system in which a thread named T
1
sends a message to another thread named T
2
. Since the system applies location transparency, the sending thread T
1
does not have to know the exact location of the destination thread, e.g. it does not have to know at which computer node the receiving thread T
2
resides but it is sufficient with the name T
2
.
FIG. 1B
illustrates a case when T
2
has disappeared from the system. This could for example be the case if a failure had occurred in node
3
. However, this fact is effectively hidden to the sending thread T
1
because of the location transparency and T
1
still attempts to send the message using the name T
2
to refer to the destination. However, the name T
2
is now invalid.
Depending on which is the communication mechanism, the behaviour in such a situation may differ but at best the sending thread is notified of the failure to deliver the message. The communication, even in the best case, do thus not offer any fault tolerance in itself but it merely gives the application, here the sending thread T
1
, information about the failure.
FIG. 1C
illustrates the case when the disappeared thread T
2
reappears at another node (here node
2
). The location transparent message passing scheme will then automatically adjust to such a situation on condition that the reappearing thread has the same name, namely T
2
, as the disappeared thread.
Finally,
FIG. 1D
illustrates a situation with two instances of a thread T
2
, which means that two threads are functionally equivalent to the extent that they both are possible receivers of a message sent by T
1
. Through adding one more thread with the same functionality, the throughput of the application could potentially scale up. This scaling, however, does not mean that the application has to be rewritten, it is merely a question of creating one more copy of a thread. The main drawback is that, if location transparent communication, or any weaker form of communication, is used, the performance scaling will not take place since T
1
still explicitly addresses T
2
when sending messages.
Through the examples as illustrated in
FIGS. 1A-1D
, it becomes evident that location transparent message passing can handle situations in which the locality of a thread changes. However, it can not to a satisfactory extent handle situations with disappearing threads; in a way which makes a distributed application fault-tolerant. Furthermore scalability of an application is not supported since the application code is written to take advantage of specific, explicitly named resources (threads in the examples referred to above) and the addition of new resources requires the making of changes in the application code.
SUMMARY
What is needed is therefore a distributed communication system which is efficient and easy to implement. Particularly a system is needed which permits scalability, i.e. that at least to a desired extent enables the use of newly added nodes or resources or similiar and which can handle the situation when nodes or resources are removed, when failures occur etc., i.e. a system which is tolerent to failures. In other words a system is needed which can handle an evolving system and when changes occur in the system and which efficiently can take advantage of the chang
Burns Doane et al.
Najjar Saleh
LandOfFree
Distributed communication system with categorized resources does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Distributed communication system with categorized resources, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distributed communication system with categorized resources will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2888472