Method and apparatus for transparently bridging traffic across wide area networks

• US 5,870,386 A
• Filed: 12/30/1991
• Issued: 02/09/1999
• Est. Priority Date: 01/09/1991
• Status: Expired due to Term

• Current Assignee: Extreme Networks, Inc.
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Harper, John A., Hawe, William R., Perlman, Radia Joy
• Primary Examiner(s): NGUYEN, CHAU T
• Application Number:
  US07/816,316
• Time in Patent Office: 2,598 Days
• Field of Search: 370/85.13, 370/85.14, 370/94.2, 370/85.15, 370/60.1, 370/94.1, 370/60, 370/85.12, 370/224, 370/225, 370/226, 370/401-405, 370/254, 370/256, 370/255 , 370/408, 370/351, 395/200.01, 395/200.02, 395/200.15, 395/200.21
• US Class Current: 370/256
• CPC Class Codes: H04L 12/4604 LAN interconnection over a backbone network, e.g. Internet, Frame Relay
• CPC Class Codes: H04L 12/462 LAN interconnection over a bridge based backbone
• CPC Class Codes: H04L 12/4633 Interconnection of networks using encapsulation techniques, e.g. tunneling
• 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/18 Loop-free operations
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/48 Routing tree calculation

Abstract

A technique for logically connecting local area networks (LANs) that may be separated by wide area networks containing routers and other network components. A logical link is formed between two bridge-like devices called tunnelers, such that, once a tunnel has been established between two LANs, other devices on the LANs can communicate as if the tunnel were a bridge. The tunneling mechanism of the invention requires that each LAN or extended LAN have only one active tunneler at any particular time, referred to as the designated tunneler, and each of the tunnelers is configured to have knowledge of the identities of the other tunnelers. A tunnel is established after a successful exchange of messages between two tunnelers, and then traffic may be forwarded through the tunnel in a transparent manner. The tunneling mechanism permits messages to be forwarded between LANs separated by a wide area network containing routers. Moreover, the mechanism permits filtering of traffic, such that only selected types of traffic, or messages for selected destinations or from selected sources, are forwarded through tunnels. The tunneling mechanism inherently precludes the formation of closed communication loops. An alternate embodiment of the invention optimizes the configuration process for particular network topologies.

Claims

1. A method for logically connecting local area networks (LANS) interconnected by network components that include bridges, the method comprising the steps of:

selecting bridges to provide a plurality of tunnels between LANs that are widely separated said LANS that are widely separated being referred to as extended LANS (XLANS) and said selected bridges being referred to as tunnelers;

electing a designated tunneler for each extended LAN (XLAN) for which tunneling is to be provided, with each XLAN having no more than one designated tunneler and a single tunneler being designated by at least one XLAN;

configuring the designated tunneler by supplying the designated tunneler with information identifying other designated tunnelers;

establishing at least one tunnel between two of said XLANs through said designated tunneler and at least one of said other designated tunnelers, by exchanging messages between the designated tunneler and said at least one her designated tunneler; and

selectively forwarding message traffic through the at least one established tunnel, from one LAN to another by appending to a message a destination address that includes an address of a receiving endpoint tunneler of the tunnel, and also includes a port identifier that defines, in part, the receiving endpoint tunneler of the tunnel.

2. A method as defined in claim 1, wherein the step of electing a designated tunneler for each XLAN provides a single tunneler designated to only one XLAN and further comprises the steps of:

electing a root bridge by executing a spanning tree algorithm among all of the bridges connected to the XLAN; and

ensuring that the root bridge has tunneling capability.

3. A method as defined in claim 1, wherein the step of configuring the tunnelers includes the step of:

supplying to each tunneler information corresponding to the identities of other tunnelers and the identities of ports of said other tunnelers through which the other tunnelers are connected to XLANs with which they are associated.

4. A method as defined in claim 3, wherein the step of establishing at least one tunnel includes the steps of:

transmitting a greeting from a designated tunneler to each other tunneler that is a potential tunnel endpoint;

receiving a message from one of the potential tunnel endpoints confirming that a tunnel is established; and

recording that said at least one tunnel has been established.

5. A method as defined in claim 1, wherein the step of configuring the tunnelers includes the step of:

supplying to each tunneler the identities of other tunnelers, the identities of ports through which the other tunnelers are connected to XLANs with which they are associated, and an indication of tunneler priorities, to facilitate establishment of tunnels between tunnel endpoints.

6. A method as defined in claim 5, wherein the step of establishing at least one tunnel includes the steps of:

transmitting a greeting from a first designated tunneler to another designated tunneler that is a potential tunnel endpoint of the first designated tunneler;

receiving a message from another designated tunneler confirming that a tunnel is established; and

recording that said tunnel has been established.

7. A method as defined in claim 5, wherein the step of establishing at least one tunnel includes the steps of:

transmitting a greeting from a first designated tunneler to another designated tunneler that is a potential tunnel endpoint of the first designated tunneler;

transmitting, after failing to receive a confirming message from another designated tunneler, a greeting to at least one backup tunneler;

receiving a message from the backup tunneler confirming that a tunnel is established; and

recording that a tunnel has been established.

8. A method as defined in claim 1, wherein the step of selectively forwarding message traffic through the at least one established tunnel includes the steps of:

receiving a message having a message destination at a tunneler;

determining whether the message destination is known to the tunneler; and

if the destination is known, performing the steps of;

determining whether the destination requires forwarding through any one of said plurality of tunnels, and

if so, forwarding the message through the tunnel, if the tunnel is one of said at least one established tunnels and the message is of a type authorized for forwarding through the one of said at least one established tunnel;

if the destination is not known, determining whether the message was received from any one of said plurality of tunnels;

if the message was received from any one of said plurality of tunnels, forwarding the message through a port defined as the tunnel endpoint;

if the message was not received from any one of said plurality of tunnels and the message destination is not known, performing the steps of;

forwarding the message over all permissible non-tunnel ports, and

forwarding the message through all established tunnels, if any, for which this tunneler is a sending endpoint, if the message is of a type authorized for tunnel transmission.

9. A method as defined in claim 8, wherein the step of forwarding a message through the one of said at least one established tunnel includes the step of:

transmitting the message through an appropriate port to reach the receiving endpoint of the one of said at least one established tunnel.

10. A method as defined in claim 9, wherein if the message was received from the one of said at least one established tunnel the method further comprises the step of:

stripping, from the received message, the address of a receiving endpoint tunneler, before forwarding the message through the tunnel receiving endpoint port.

11. A method as defined in claim 8, wherein the step of selectively forwarding messages through the at least one established tunnel includes the further step of:

updating, if necessary, a database of destinations, by means of address information obtained from each message source.

12. A method as defined in claim 1, wherein the step of configuring includes the step of:

supplying the tunnelers with a subset of information concerning other tunnelers, the subset of information being selected for optimal operation of a particular network topology; and

the step of establishing a tunnel includes the steps of;

(1) for said designated tunneler, sending a greeting to at least one of said designated tunnelers with which it has been configured, and receiving a response confirming that a tunnel has been established, or

(2) for said designated tunneler, sending a greeting to a nondesignated tunneler with which it has been configured, receiving a refusal response identifying another designated tunneler, redirecting the greeting to another designated tunneler identified in the refusal response, and receiving a response confirming that a tunnel has been established, and

(3) for said nondesignated tunneler, periodically transmitting multicast messages identifying the tunnelers with which it has been configured, and, for said designated tunneler, responding to a multicast message from another nondesignated tunneler, by sending a greeting to one of the tunnelers contained in the multicast message, and receiving a response message confirming that a tunnel has been established.

13. A method for logically connecting local area networks (LANS) interconnected by network components that include a plurality of bridges comprising the steps of:

selecting from said plurality of bridges selected bridges, to provide tunnels between LANs that are widely separated, said LANS that are widely separated being referred to as extended LANS (XLANS) with said widely separated LANS having routers, and said selected bridges being referred to as tunnelers;

electing a unique designated tunneler for each extended LAN (XLAN) for which tunneling is to be provided, with each XLAN having no more than one designated tunneler and a single tunneler being designated by one XLAN;

configuring the designated tunneler by supplying the designated tunneler with the identities of other designated tunnelers and the identities of ports through which the other tunnelers are connected to XLANs with which they are associated;

establishing at least one tunnel between at least two of said designated tunnelers, by transmitting a greeting from a first designated tunneler to each other tunneler that is a potential tunnel endpoint, receiving a message from one of the potential tunnel endpoints confirming that a tunnel is established, and recording that a tunnel has been established; and

selectively forwarding message traffic through the established tunnel, from one LAN to another by appending to a message a destination address that includes the address of a receiving endpoint tunneler of the tunnel, and also includes a port identifier that defines, in part, the receiving endpoint of the tunnel.

14. A method as defined in claim 13, wherein the step of selectively forwarding message traffic through the at least one established tunnel includes the steps of:

receiving a message having a message destination at a tunneler;

determining whether the message destination is known to the tunneler; and

if the destination is known, performing the steps of;

determining whether the destination requires forwarding through any one of said plurality of tunnels, and

if so, forwarding the message through the tunnel, if the tunnel is one of said at least one established tunnels and the message is of a type authorized for forwarding through the one of said at least one established tunnel;

if the destination is not known, determining whether the message was received from any one of said plurality of tunnels;

if the message was received from any one of said Plurality of tunnels, forwarding the message through a port defined as the tunnel endpoint;

if the message was not received from any one of said plurality of tunnels and the message destination is not known, performing the steps of;

forwarding the message over all non-tunnel ports except one through which the message was received, forwarding the message through all established tunnels, if any, for which this tunneler is a sending endpoint, if the message is of a type authorized for tunnel transmission.

15. A method as defined in claim 14, wherein the step of forwarding a message through the one of said at least one established tunnel includes the step of:

transmitting the message through an appropriate port to reach the receiving endpoint of the one of said at least one established tunnel.

16. A method as defined in claim 15, wherein if the message was received from the one of said at least one established tunnel the method further comprises the step of:

stripping, from the received message, the address of a receiving endpoint tunneler, before forwarding the message through the tunnel receiving endpoint port.

17. Apparatus for logically connecting local area networks (LANs) interconnected by network components that include bridges, the apparatus comprising:

a plurality of bridges disposed between LANs that are interconnected by routers, said LANS being widely separated, and said LANS that are widely separated being referred to as extended LANS (XLANS), said bridges being referred to as tunnelers;

means, for electing a unique designated tunneler for each extended LAN (XLAN) from a corresponding one of said plurality of bridges for which tunneling is to be provided, with each XLAN having no more than one designated tunneler and a single tunneler being designated by one XLAN;

means, responsive to information identifying other tunnelers, for configuring the tunnelers with which a tunnel is established;

means, responsive to messages exchanged between at least two tunnelers, for establishing at least one tunnel between said at least two tunnelers; and

means, contained within each tunneler, for selectively forwarding message traffic through the established tunnel, from one LAN to another by appending to a message a destination address that includes the address of a receiving endpoint tunneler of the tunnel, and also includes a sort identifier that defines, in part, the receiving endpoint of the tunnel.

18. Apparatus as defined in claim 17, wherein the means for electing a unique designated tunneler for each XLAN includes:

means for executing a spanning tree algorithm among all of the bridges connected to the XLAN and for electing a root bridge in accordance with said spanning tree algorithm; and

means for ensuring that the root bridge has tunneling capability.

19. Apparatus as defined in claim 17, wherein the means for configuring the tunnelers includes:

means for supplying to each tunneler the identities of other tunnelers and the identities of ports through which the other tunnelers are connected to XLANs with which they are associated.

20. Apparatus as defined in claim 19, wherein the means for establishing at least one tunnel includes:

means for transmitting a greeting from a designated tunneler to each other tunneler that is a potential tunnel endpoint;

means for receiving a message from one of the potential tunnel endpoints confirming that a tunnel is established; and

means for recording that said at least one established tunnel has been established.

21. Apparatus as defined in claim 17, wherein the means for configuring the tunnelers includes:

means for supplying to each tunneler the identities of other tunnelers, the identities of ports through which the other tunnelers are connected to XLANs with which they are associated, and an indication of tunnel priorities, to facilitate establishment of tunnels between tunnel endpoints.

22. Apparatus as defined in claim 20, wherein the means for establishing at least one tunnel includes:

means for transmitting a greeting from a designated tunneler to another designated tunneler that is a potential tunnel endpoint;

means for receiving a message from the other designated tunneler confirming that a tunnel is established; and

means for recording that said tunnel has been established.

23. Apparatus as defined in claim 20, wherein the means for establishing at least one tunnel includes:

means for transmitting a greeting from a designated tunneler to another designated tunneler that is a potential tunnel endpoint;

means for transmitting, after failing to receive a confirming message from the other designated tunneler, a greeting to at least one backup tunneler;

means for receiving a message from the backup tunneler confirming that a tunnel is established; and

means for recording that said tunnel has been established.

24. Apparatus as defined in claim 17, wherein the means for selectively forwarding message traffic through the at least one established tunnel includes:

means for receiving a message having a message destination at a tunneler;

means for determining whether the message destination is known to the tunneler;

means, operative if the destination is known, for determining whether the destination requires forwarding through any one of said plurality of tunnels, and if so, forwarding the message through the tunnel, if the tunnel is one of said at least one established tunnels and the message is of a type authorized for forwarding through the one of said at least one established tunnel;

means, operative if the destination is not known, for determining whether the message was received from any one of said plurality of tunnels;

means, operative if the message was received from any one of said plurality of tunnels, for forwarding the message through a port defined as the tunnel endpoint;

means, operative if the message was not received from any one of said plurality of tunnels and the message destination is not known, for forwarding the message over all permissible non-tunnel ports, and

forwarding the message through all established tunnels, if any, for which this tunneler is a sending endpoint, if the message is of a type authorized for tunnel transmission.

25. Apparatus as defined in claim 24, wherein the means for forwarding a message through the one of said at least one established tunnel includes:

means for transmitting the message through an appropriate port to reach the receiving endpoint of the one of said at least one established tunnel.

26. Apparatus as defined in claim 25, and further comprising:

means, operative if the message was received from the one of said at least one established tunnel, for stripping from the received message the address of a receiving endpoint tunneler, before forwarding the message through the tunnel receiving endpoint port.

27. Apparatus as defined in claim 17, wherein the means for configuring includes:

means for supplying the tunnelers with a subset of information concerning other tunnelers, the subset of information being selected for optimal operation of a particular network topology; and

the means for establishing a tunnel includes;

(1) for said designated tunneler, means for sending a greeting to at least one of said designated tunnelers with which it has been configured, and receiving a response confirming that a tunnel has been established, or

(2) for said designated tunneler, means for sending a greeting to a nondesignated tunneler with which it has been configured, means for receiving a refusal response identifying another designated tunneler, means for redirecting the greeting to the another designated tunneler identified in the refusal response, and receiving a response confirming that a tunnel has been established, and

(3) for said nondesignated tunneler, means for periodically transmitting multicast messages identifying the tunnelers with which it has been configured, and, for said designated tunneler, means for responding to a multicast message from a nondesignated tunneler, by sending a greeting to one of the tunnelers contained in the multicast message, and receiving a response message confirming that a tunnel has been established.