System for determining communication routes in a network

• US 5,347,272 A
• Filed: 09/11/1992
• Issued: 09/13/1994
• Est. Priority Date: 09/13/1991
• Status: Expired due to Term

• Current Assignee: Fuji Xerox Company Limited (Fujifilm Holdings Corporation)
• Original Assignee: Fuji Xerox Company Limited (Fujifilm Holdings Corporation)
• Inventors: Ota, Hiromi
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): HOM, SHICK C
• Application Number:
  US07/943,567
• Time in Patent Office: 732 Days
• Field of Search: 340/827, 340/826, 340/825.52, 370/94.1, 370/60, 370/85.13, 370/54, 370/79, 370/61
• US Class Current: 370/392
• CPC Class Codes: H04L 12/185 with management of multicast group membership
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/16 Multipoint routing

Abstract

A network system capable of speedily selecting an intermediate system which can provide a shortest route of data communication among various intermediate systems even if routing information is not stored on the end system side, and in which the wasteful routing information is not held on the end system side, thereby minimizing an amount of routing information stored. In the network system, each packet for broadcast communication sent from each intermediate system is imparted to an intermediate system-address extracting unit 6 via a reception unit 2 and a packet processing unit 4 in the end system. The management-address extracting unit 6 extracts addresses of the intermediate systems from the packets, and stores these addresses in the management-address storage unit 8. When the packet is transmitted from this end system, the packet processing unit 4 obtains addresses in the management-address storage unit 8 via a route request unit 9, and sends a request of routing information to the intermediate systems having these addresses via a transmission unit 10. When the respective routing information is sent from the intermediate systems to the end system in response to that request, a route selecting unit 5 determines a shortest route to the destination on the basis of each routing information. The packet processing unit 4 request the intermediate system providing the shortest route to relay the packet.

Claims

1. A network system comprising:

a network, a plurality of end systems connected to said network, said end systems acting only as sources and destinations of data to be transmitted and received; and

a plurality of intermediate systems for relaying said data to be transmitted and received to and from said plurality of end systems;

wherein at least one of said plurality of intermediate systems includes;

broadcast communication means for transmitting broadcast communication data, in which an address of said at least one of said plurality of intermediate systems is set as a sender, to said plurality of end systems connected to said network to which said at least one of said plurality of intermediate systems is connected as well as to at least one other of said plurality of said intermediate systems;

preparing means for preparing routing information on the basis of the broadcast communication data transmitted by said at least one other of said plurality of intermediate systems;

first routing information storage means for storing the routing information prepared by said preparing means; and

returning means for returning the routing information to at least one of said plurality of end systems upon request of said at least one of said plurality of end systems, and

wherein said at least one said plurality of said end systems includes;

extracting means which, upon receiving respective broadcast communication data transmitted from said at least one of said plurality of intermediate systems, is adapted to extract an address of said at least one of said plurality of intermediate systems respectively contained in the broadcast communication data;

storage means for storing the address extracted by said extracting means;

request means for requesting routing information from said at least one of plurality of intermediate systems on the basis of the address of said at least one of said plurality of intermediate systems in said storage means when the data is transmitted to said network; and

selecting means for selecting a selected one of said plurality of intermediate systems from which the relaying of data is requested, on the basis of the respective routing information from said plurality of intermediate systems obtained as a result of the request by said request means.

2. A network system according to claim 1, wherein said at least one of said plurality of end systems further includes:

second routing information storage means for accumulating and storing the routing information from said selected one of said plurality of intermediate systems selected by selecting means; and

retrieval means for retrieving the routing information stored in said second routing information storage means,

wherein at the time of transmission of data to said network, said retrieval means effects retrieval prior to the request from said request means so as to determine whether or not routing information indicating a shortest route has been stored in said second routing information storage means, and if the information indicating the shortest route is present, said selecting means selects said selected one of said plurality of intermediate systems to which the relaying of data is requested, on the basis of the routing information indicating the shortest route retrieved by said retrieval means.

3. A network system according to claim 2, wherein at least one of said plurality of end systems further includes first deletion means for deleting the routing information stored in said second routing information storage means, on the basis of a time when the routing information stored in said second routing information storage means was accessed.

4. A network system according to claim 2, wherein at least one of said plurality of end systems further includes second deletion means for deleting the routing information stored in said second routing information storage means, on the basis of a time when the routing information stored in said second routing information storage means was stored.

5. An intermediate system which is connected to a network system including a network and a plurality of end systems, and is adapted to relay transmission and reception of data between said plurality of end systems, said intermediate system comprising:

broadcast communication means for transmitting broadcast communication data, in which an own address is set as a sender, to said plurality of end systems;

preparing means for preparing routing information on the basis of the broadcast communication data transmitted by a second intermediate system;

first routing information storage means for storing the routing information; and

returning means for returning the routing information stored in said first routing information storage means to at least one of said plurality of end systems upon request of said at least one of said plurality of end systems.

6. An end system which is connected to a network system including a network and a plurality of intermediate systems each of said plurality of intermediate systems adapted to relay transmission and reception of data transmitted through the network and to transmit broadcast communication data which are broadcast to a plurality of addresses and in which an own address is set as a sender, so as to effect said transmission and reception of data, said end system comprising:

extracting means which, upon receiving respective broadcast communication data transmitted from said plurality of intermediate systems, is adapted to extract addresses of said plurality of intermediate systems respectively contained in the broadcast communication data;

storage means for storing the addresses extracted by said extracting means;

request means for requesting routing information from said plurality of intermediate systems on the basis of the addresses stored in said storage means when the data is transmitted to said network; and

selecting means for selecting a selected one of said plurality of intermediate systems from which the relaying of data is requested, on the basis of the respective routing information from said plurality of intermediate systems obtained as a result of the request by said request means.

7. An end system of a network system according to claim 6, further including:

second routing information storage means for accumulating and storing the routing information of said selected one of said plurality of intermediate systems selected by selecting means; and

retrieval means for retrieving the routing information stored in said second routing information storage means,

wherein at the time of transmission of data to said network, said retrieval means effects retrieval prior to the request from said request means so as to determine whether routing information indicating a shortest route has been stored in said second routing information storage means, and if the information indicating the shortest route is stored, said selecting means selects said selected one of said plurality of intermediate systems from which the relaying of data is requested, on the basis of the routing information indicating the shortest route retrieved by said retrieval means.

8. An end system of a network system according to claim 7, further including:

first deletion means for deleting the routing information on the basis of a time when the routing information stored in said second routing information storage means was accessed.

9. An end system of a network system according to claim 7, further including:

second deletion means for deleting the routing information on the basis of a time when the routing information stored in said second routing information storage means was stored.