Interconnection of broadcast networks

• US 4,706,080 A
• Filed: 08/26/1985
• Issued: 11/10/1987
• Est. Priority Date: 08/26/1985
• Status: Expired due to Term

• Current Assignee: Telcordia Technologies Incorporated (Telefonaktiebolaget LM Ericsson)
• Original Assignee: Bell Communications Research, Inc. (Telefonaktiebolaget LM Ericsson)
• Inventors: Sincoskie, Walter D.
• Primary Examiner(s): Weldon, Ulysses
• Assistant Examiner(s): Smith, Ralph E.
• Application Number:
  US06/769,555
• Time in Patent Office: 806 Days
• Field of Search: 340/825.02, 340/825.03, 340/825.52, 370/60, 370/94, 370/85, 370/88, 364/200, 364/900
• US Class Current: 370/401
• CPC Class Codes: H04L 12/462 LAN interconnection over a bridge based backbone
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/484 using multiple routing trees

Abstract

A process is disclosed for effecting transmission over a generally cyclic communication system comprising numerous networks interconnected by gateway pairs. Each gateway of each pair implements a store-and-forward protocol whereby each gateway forwards message packets propagated over its associated network except for any packets that are destined for a device which has previously appeared in the sending address of another packet. In order to utilize this protocol as a basis for transmission, the system is covered with a set of spanning trees that satisfy capacity and reliability requirement. Each spanning tree is assigned a unique identifier and each packet traversing the system is assigned to and conveys the specified spanning tree. Each gateway passes the packet to determine the assigned spanning tree and forwards the packet accordingly. To mitigate system flooding by a newly connected device, the protocol may also incorporate a delay to allow the gateways to learn the location of the new device.

Claims

1. A method for transmitting packets over a system comprising a plurality of networks interconnected by gateways, each of said packets having a sending address and a destination address, said method characterized by the steps of

configuring each of said gateways to implement the routing algorithm of forwarding any of said packets received by said each gateway except for said any of said packets destined for one of said networks having a sending address appearing in any previously counted ones of said packets, said sending appearances being stored in a drop list within said each gateway.

selecting a set of spanning trees for said system,

conveying by each of said packets an identifier indicative of one of said trees, and, for said each packet,

extracting said sending address and said destination address from said each packet within each of said gateways,

if said sending address is not in said drop list of said each gateway, adding said sending address to said drop list,

if said destination address is not in said drop list, storing said each packet for a predetermined time interval wherein subsequent ones of said packets are processed by said each gateway, and

routing of said each packet by said gateways through said system on one of said spanning trees in correspondence with said identifier whenever said destination address is not in said drop list after said time interval;

otherwise, no longer storing said each packet within said each gateway.

2. The method as recited by claim 1 further comprising the step of

returning an acknowledgement packet over said one of said trees.

3. A method for propagating packets by a gateway, each of said packets comprising a source address and a destination address, said method characterized by the steps of

configuring said gateway to implement the routing algorithm of forwarding any of said packets received by said gateway except for any of said packets having a destination address appearing as the source address in any previously routed ones of said packets, said source appearance being stored in a drop list;

and, for each packet,

extracting said source address and said destination address from said packet within said gateway;

if said source address is not in said drop list, adding said source address to said drop list,

if said destination address is not in said drop list, storing said packet for a predetermined time interval whereon subsequent ones of said packets are processed by said gateway; and

routing said packet if said destination address is not in said drop list after said time interval;

otherwise, no longer storing said packet within said gateway.

4. A method for processing a packet by a first gageway from a gateway pair wherein said first gateway has a first drop list readable by the second gateway and said second gateway has a second drop list readable by said first gateway, said packet comprising a source address and a destination address, each said drop list comrpising source addresses of previous packets processed by the corresponding gateway, and said method characterized by the steps of

extracting said source address and said destination address from said packet within said first gateway,

if said source address is not in said first drop list, inserting said source address in said first drop list,

reading said second drop list and, if said destination address is in said second drop list, forwarding said packet by said first gateway,

if said source address is not orignially in said first drop list and said destination address is not in said second drop list, storing said packet by said first gateway for a predetermined time interval wherein subsequent packets are processed by said gateway pair, and

forwarding said packet if said destination address is not in said first drop list after said interval;

otherwise, no longer storing said packet by said first gateway.

5. A method for transmitting a packet over a system comprising a plurality of networks interconnected by gateways, said packet originated by a source device connected to one of said networks and destined for a destination device connected to one of said networks, said packet including a source address and a destination address, and said method comprising the steps of

defining an undirected graph representative of the system wherein said networks map onto graph nodes and said gateways map onto graph paths,

defining a spanning tree on said graph such that every pair of said nodes is connected by only one of said paths and selecting a plurality of spanning trees for said graph according to predetermined system guidelines,

configuring each gateway with source address lists in correspondence to the number of trees having said each gateway comprising one of said paths,

assigning, by said source device, one of said trees to broadcast said packet and associating with said packet an identifier indicative of said one of said trees,

broadcasting said packet by said source device through the system on said one of said trees,

for each gateway receiving said packet,

(i) determining for each said packet said source address, said destination address and said packet identifier,

(ii) if said receiving gateway does not process packets having said identifier, inhibiting forwarding of said packet;

otherwise, inserting said source address in the corresponding one of said lists associated with said identifier

(iii) inhibiting forwarding of said packet if said destination address is in said corresponding one of said lists;

otherwise, storing said packet for a prescribed time interval and then submitting said packet for processing by step (iv), and,

(iv) inhibitng forwarding of said packet if said destination address is in said corrsponding list;

otherwise, forwarding said packet by said receiving gateway, and

acknowledging the reception of said packet by said destination device by broadcasting a return packet over said one of said trees.

6. A method for transmitting a packet over a system comprising a plurality of networks interconnected by gateways, said packet orginated by a source device connected to one of said networks and destined for a destination device connected to one of said networks, said packet including a source address and a destination address, and said method comprising the steps of

defining an undirected graph representative of the system wherein said networks comprise graph nodes and said gateway comprise graph paths,

defining a spanning tree on said graph such that every pair of said nodes is connected by only one of said paths and selecting a plurality of spanning trees for said graph according to predetermined system guidelines,

configuring each gateway with source address lists in correspondence to the number of trees having said each gateway comprising one of said paths, wherein said lists reduce to a common list whenever said selection of spanning trees results in identical ones of said lists for said each gateway,

assigning, by said source device, one of said trees to boradcast said packet and associating with said packet an identifier indicative of said one of said trees,

broadcasting said packet by said source device through the system on said one of said trees, and

for each gateway receiving said packet,

(i) determining for each said packet said source address, said destination address and said packet identifier,

(ii) if said receiving gateway does not process packets having said identifier, inhibiting forwarding of said packet;

otherwise, inserting said source address in the corresponding one of said lists associated with said identifier, and

(iii) inhibiting forwarding of said packet if said destination address is in said corresponding list;

otherwise, forwarding said packet by said receiving gateway.