Multiple path trees and lan segments for routing in a network of bridge-connected lan segments

Claim 3

In a network comprising of network segments interconnected by bridges, terminals connected to the the network segments and each network segment having a unique identifier a method for deriving the routing information required for frame transmissions between a source terminal and a destination terminal, with each of said terminals having a unique address comprising the steps of: transmitting from the source terminal a discovery frame including the source terminal address, the destination terminal address, and two empty fields for a source network segment identifier and a destination network segment identifier, respectively; in each bridge receiving the discovery frame with an empty source network segment identifier field, first inserting into said field an identifier of a network segment from which the discovery frame was received; in each bridge, testing for each entry of the local routing table whether the source network identifier in the frame corresponds to the destination segment identifier in the entry, and whether the next segment identifier in the entry corresponds to the input network segment from which said frame was received, and if the test is positive, inserting for each previous segment identifier contained in the entry, this previous segment identifier into the destination network segment field of said frame and forwarding a copy of the frame to the network segment corresponding to said inserted previous segment identifier, but if the test is negative, discarding the frame; receiving said discovery frame in said destination terminal, carrying the source network segment identifier for said source terminal and the destination network segment identifier for said destination terminal; and returning the source network segment identifier and the destination network segment identifier from said destination terminal to said source terminal.

Claim 4

In a network comprising of network segments interconnected by bridges, terminals connected to the the network segments and each network segment having a unique identifier a method for deriving the routing information required for frame transmissions between a source terminal and a destination terminal, with each of said terminals having a unique address comprising the steps of: transmitting from the source terminal a discovery frame including the source terminal address, the destination terminal address, and two empty fields for a source network segment identifier and a destination network segment identifier, respectively; in each bridge receiving the discovery frame with an empty source network segment identifier field, first inserting into said field an identifier of a network segment from which the discovery frame was received; in each bridge, testing for each entry of the local routing table whether the source network identifier in the frame corresponds to the destination segment identifier in the entry, and whether the next segment identifier in the entry corresponds to the input network segment from which said frame was received, and if the test is positive, inserting for each previous segment identifier contained in the entry, this previous segment identifier into the destination network segment field of said frame and forwarding a copy of the frame to the network segment corresponding to said inserted previous segment identifier, but if the test is negative, discarding the frame; receiving said discovery frame in said destination terminal, carrying the source network segment identifier for said source terminal and the destination network segment identifier for said destination terminal; and returning the source network segment identifier and the destination network segment identifier from said destination terminal to said source terminal.

Claim 5

A bridge apparatus for interconnecting LAN segments comprising: means (31) for storing a routing table (FIG. 3) including a plurality of entries, each entry comprising a destination segment identifier, a next segment identifier, and one or plural previous segment identifiers; means (29, 35) for correlating segment number information contained in at least one selected segment identifier field of a received frame with segment identifiers contained in a selected entry of the routing table and for generating control signals therefrom; and means (21, 23, 25, 27) for forwarding, in response to said control signals, the received frame from any connected network segment (11) to any other one (13, 15) of the connected network segments.

Claim 6

A bridge apparatus for interconnecting LAN segments comprising: means (31) for storing a routing table (FIG. 3) including a plurality of entries, each entry comprising a destination segment identifier, a next segment identifier, and one or plural previous segment identifiers; means (29, 35) for correlating segment number information contained in at least one selected segment identifier field of a received frame with segment identifiers contained in a selected entry of the routing table and for generating control signals therefrom; and means (21, 23, 25, 27) for forwarding, in response to said control signals, the received frame from any connected network segment (11) to any other one (13, 15) of the connected network segments.

Claim 7

Apparatus according to claim 3, further comprising: means (37, 39, 45) for comparing segment identifiers from an entry of said table with a network segment identifier received in a frame and with an identifier corresponding to the input network segment from which that frame was received, and for generating a forwarding control signal, and means (47), responsive to said forwarding control signal, for transferring a segment identifier from said table entry to said control signal generating means (35), for determining the output network segment to which said frame is to be forwarded.

Claim 8

Bridge apparatus for routing frames through a system including network segments interconnected by bridges, in which system each network segment has a unique identifier, and in which system for each of said network segments as destination, a tree of paths from all other network segments is predetermined; the apparatus comprising: means (31) for storing a routing table (FIG. 3) having an entry for each path tree of which said bridge is a part, each said entry listing for the respective path tree, identifiers for the destination network segment, and for the next network segment and all previous network segments on said path tree to which said bridge is connected; means (29, 35) for generating routing control signals as a result of correlating network segments identifiers in a received frame and network segment identifiers of said routing table; means (37, 39, 43, 45) for comparing segment identifiers from each entry of said table with a network segment identifier received in a frame and with an identifier corresponding to the input network segment from which that frame was received, and for generating a forwarding control signal; means (47), responsive to said forwarding control signal, for transferring a segment identifier from said table entry to said routing control signal generating means (29, 35), for determining the output network segment to which said frame is to be forwarded; and means (21, 23, 25, 27) for transferring, in response to said routing control signals, a frame from any network segment (11) connected to the bridge to any other one (13, 15) of the connected network segments.

Claim 9

Bridge apparatus for routing frames through a system including network segments interconnected by bridges, in which system each network segment has a unique identifier, and in which system for each of said network segments as destination, a tree of paths from all other network segments is predetermined; the apparatus comprising: means (31) for storing a routing table (FIG. 3) having an entry for each path tree of which said bridge is a part, each said entry listing for the respective path tree, identifiers for the destination network segment, and for the next network segment and all previous network segments on said path tree to which said bridge is connected; means (29, 35) for generating routing control signals as a result of correlating network segments identifiers in a received frame and network segment identifiers of said routing table; means (37, 39, 43, 45) for comparing segment identifiers from each entry of said table with a network segment identifier received in a frame and with an identifier corresponding to the input network segment from which that frame was received, and for generating a forwarding control signal; means (47), responsive to said forwarding control signal, for transferring a segment identifier from said table entry to said routing control signal generating means (29, 35), for determining the output network segment to which said frame is to be forwarded; and means (21, 23, 25, 27) for transferring, in response to said routing control signals, a frame from any network segment (11) connected to the bridge to any other one (13, 15) of the connected network segments.

Claim 10

The bridge apparatus according to claim 6, further comprising: register means (37) for holding the contents of two network segment identifier fields contained as routing information in a received frame; means (41) for detecting the presence of a discovery frame; means (39, 41) for detecting whether a discovery frame contains an empty destination network segment identifier field, and for inserting into said field the identifier of the input network segment on which the discovery frame was received; means (43, 45) for comparing, sequentially for each entry of the routing table, the destination segment identifier of the entry with the source network segment identifier contained in a discovery frame, and the next segment identifier of the entry with the identifier of the input network from which said discovery frame was received, and for generating a forwarding control signal; and means (43, 47) for sequentially inserting, in response to said forwarding control signal, each previous segment identifier of a routing table entry, into the destination network segment identifier field of said discovery frame, and for providing said identifier to the routing control signal generating means (29, 35), for transferring a copy of the discovery frame to an output network segment corresponding to the inserted previous segment identifier.

Claim 11

The bridge apparatus according to claim 7, further including terminals connected to network segments and for transmitting frames between terminals connected to different network segments.

Claim 12

The method of claim 1 further including the steps of; discarding the frame if (a) or (b) determinations is negative.