Bridge-like internet protocol router

Claims

We claim:

1. For use in a configuration of interconnected local area networks (LANs) handling message traffic in accordance with a set of inter-network protocols that use a network addressing scheme, a bridge-like IP router (BLIP), comprising:

multiple ports for attaching the BLIP to multiple segments of an extended LAN;

means for distinguishing received message traffic that uses the inter-network protocols from other message traffic that does not use the protocols;

bridge means for processing the other message traffic exactly in the manner of a conventional bridge, using unique station addresses to determine how to forward the received message traffic; and

bridge-like means for processing the inter-network protocol traffic in a manner analogous to a bridge, wherein a message packet received from an extended LAN segment attached to the BLIP is forwarded if necessary to at least one other extended LAN segment attached to the BLIP, using network addresses and network segment addresses, instead of unique station addresses, to determine how to forward the message traffic.

2. A bridge-like IP router as defined in claim 1, and further comprising:

means for processing address resolution messages requesting destination address information.

3. A bridge-like IP router as defined in claim 2, wherein:

the means for processing address resolution messages includes means for detecting and discarding address resolution messages requesting destination address information, and means for responding to the address resolution messages by transmitting in reply a message packet containing a special address code, but only if the request destination address is on a different segment of the same extended LAN as the BLIP; and

the bridge-like means includes means for forwarding any received message packet containing the special address code, to some subset of the attached extended LAN segments except the one from which the message packet was received;

whereby a host device may transmit to destinations on other extended LAN segments as though the destinations were on the same LAN.

4. For use in a configuration of interconnected local area networks (LANs) handling message traffic in accordance with a set of protocols known as TCP/IP, a bridge-like IP router (BLIP), comprising:

multiple ports for attaching the BLIP to multiple segments of an extended LAN;

means for distinguishing received TCP/IP message traffic from non-TCP/IP message traffic;

bridge means for processing non-TCP/IP message traffic exactly in the manner of a conventional bridge; and

bridge-like means for processing TCP/IP traffic in a manner analogous to a bridge, wherein a message packet received from an extended LAN segment attached to the BLIP is forwarded if necessary to some subset of the attached extended LAN segments except the one from which the message packet was received at least one other extended LAN segment attached to the BLIP.

5. A bridge-like IP router as defined in claim 4, and further comprising:

means for processing address resolution messages requesting destination address information.

6. A bridge-like IP router as defined in claim 5, wherein:

the means for processing address resolution messages includes means for detecting and discarding address resolution messages requesting destination address information, and means for responding to the address resolution messages by transmitting in reply a message packet containing a special address code, but only if the requested destination address is on a different segment of the same extended LAN as the BLIP; and

the bridge-like means includes means for forwarding any received message packet containing the special address code, to some subset of the attached extended LAN segments except the one from which the message packet was received;

whereby a host device may transmit to destinations on other extended LAN segments as though the destinations were on the same LAN.

7. A bridge-like IP router as defined in claim 4, wherein the bridge-like means includes:

an IP database associating each segment of the extended LAN with a port of the BLIP; and

means for updating the IP database by observing each received message and correlating the segment address for each message source with a port through which the message is received.

8. A bridge-like IP router as defined in claim 4, wherein the bridge-like means includes:

an ARP database associating each network layer address in attached extended LAN segments with a corresponding data link layer address; and

means for updating the ARP database by sending ARP messages directed to specific network layer addresses and processing ARP replies that contain the corresponding data link layer addresses.

9. A bridge-like IP router as defined in claim 4, wherein the bridge-like means includes:

a router database containing data link layer addresses for all true IP routers connected to the extended LAN.

10. For use in a configuration of interconnected local area networks (LANs) handling message traffic in accordance with a set of protocols known as TCP/IP, a bridge-like IP router (BLIP), comprising:

multiple ports for attaching the BLIP to multiple segments of an extended LAN;

means for distinguishing received TCP/IP message traffic from non-TCP/IP message traffic;

bridge means for processing non-TCP/IP message traffic exactly in the manner of a conventional bridge; and

bridge-like means for processing TCP/IP traffic in a manner analogous to a bridge, wherein a message packet received from an extended LAN segment attached to the BLIP is forwarded if necessary to at least one other extended LAN segment attached to the BLIP;

wherein the bridge-like means includes

means for detecting and discarding ARP messages requesting destination address information,

means for responding to ARP messages by transmitting in reply a message packet containing a special address code, but only if the requested destination address is on a different segment of the same extended LAN as the BLIP,

means for forwarding any received message packet containing the special address code, to at least one other attached extended LAN segment, whereby a host device may transmit to destinations on other extended LAN segments as though the destinations were on the same LAN,

an IP database associating each segment of the extended LAN with a port of the BLIP,

means for updating the IP database by observing each received message and correlating the segment address for each message source with a port through which the message is received,

an ARP database associating each network layer address in attached extended LAN segments with a corresponding data link layer address, and

means for updating the ARP database by sending ARP messages directed to specific network layer addresses and processing ARP replies that contain the corresponding data link layer addresses.

11. A bridge-like IP router as defined in claim 10, wherein the bridge-like means further includes:

a router database containing data link layer addresses for all true IP routers connected to the extended LAN.

12. A bridge-like IP router as defined in claim 11, wherein the bridge-like means further includes:

means for determining whether a received message packet is destined for an attached segment of the extended LAN;

means for forwarding a packet destined for an attached segment other than the one from which the packet was transmitted, by obtaining a data link layer destination address from the ARP database;

means for forwarding a packet destined for a segment unattached to the BLIP, by transmitting the packet to at least one other segment through a port selected to reach the destination segment.

13. A bridge-like IP router as defined in claim 12, wherein the bridge-like means further includes:

address checking means effective for processing a packet destined for the same extended LAN segment as the one from which the packet was received by the BLIP, for taking corrective action depending on the data link layer destination address contained in the packet.

14. A bridge-like IP router as defined in claim 13, wherein the address checking means includes:

means for discarding the packet if the data link layer destination address matches an entry in the ARP database corresponding to an IP destination address contained in the packet;

means for substituting the ARP database entry for a data link layer destination address in the packet if there is no match; and

means for sending a redirect message to a source host from which the packet was transmitted, if there is no match, and sending an ARP message to verify the correctness of database entry.

15. A method of operation of a configuration of interconnected local area networks (LANs) handling message traffic in accordance with a set of protocols known as TCP/IP, the method comprising the steps of:

configuring an extended local area network (LAN) to include a plurality of extended LAN segments connected by bridge-like IP routers (BLIPs);

receiving a packet of data at a BLIP;

determining whether the packet has been transmitted under TCP/IP protocols;

processing non-TCP/IP packets in the manner of a conventional bridge; and

processing TCP/IP traffic in a manner analogous to a bridge, wherein a message packet received from an extended LAN segment attached to the BLIP is forwarded if necessary to at least one other extended LAN segment attached to the BLIP.

16. A method as defined in claim 15, and further comprising:

detecting and discarding ARP messages requesting destination address information;

responding to ARP messages by transmitting a message packet containing a special address code, but only if the requested destination address is on a different segment of the same extended LAN as the BLIP; and

forwarding any received message packet containing the special address code, to at least one other attached LAN segment;

whereby a host device may transmit to destinations on other extended LAN segments as though the destinations were on the same LAN.

17. A method as defined in claim 15, and further comprising:

maintaining an IP database that associates each segment of the extended LAN with a port of the BLIP;

wherein the maintaining step is performed by observing each received message and correlating the segment address for each message source with a port through which the message is received.

18. A method as defined in claim 15, and further comprising:

maintaining an ARP database that associates each network layer address in attached extended LAN segments with a corresponding data link layer address;

wherein the maintaining step is performed by sending ARP messages directed to specific network layer addresses and processing ARP replies that contain the corresponding data link layer addresses.

19. A method as defined in claim 15, and further comprising:

maintaining a router database containing the data link layer addresses of all true IP routers connected to the extended LAN.

20. A method of operation of a configuration of interconnected local area networks (LANs) handling message traffic in accordance with a set of protocols known as TCP/IP, the method comprising the steps of:

configuring an extended local area network (LAN) to include a plurality of extended LAN segments connected by bridge-like IP routers (BLIPs);

receiving a packet of data at a BLIP;

determining whether the packet has been transmitted under TCP/IP protocols;

processing non-TCP/IP packets in the manner of a conventional bridge;

processing TCP/IP traffic in a manner analogous to a bridge, wherein a message packet received from an extended LAN segment attached to the BLIP is forwarded if necessary to at least one other extended LAN segment attached to the BLIP;

detecting and discarding ARP messages requesting destination address information;

responding to ARP messages with a special address code when the requested destination address is on a different segment of the same extended LAN as the BLIP;

forwarding a message packet having the special address code, to at least one other attached LAN segment, whereby a host device may transmit to destinations on other extended LAN segments as though the destinations were on the same LAN;

maintaining an IP database that associates each segment of the extended LAN with a port of the BLIP, wherein the maintaining step is performed by observing each received message and correlating the segment address for each message source with a port through which the message is received;

maintaining an ARP database that associates each network layer address in attached extended LAN segments with a corresponding data link layer address, wherein the maintaining step is performed by sending ARP messages directed to specific network layer addresses and processing ARP replies that contain the corresponding data link layer addresses; and

maintaining a router database containing the data link layer addresses of all true IP routers connected to the extended LAN.

21. A method as defined in claim 20, and further comprising:

determining whether a received message packet is destined for an attached segment of the extended LAN;

forwarding a packet destined for an attached segment other than the one from which the packet was transmitted, by obtaining a data link layer destination address from the ARP database; and

forwarding a packet destined for a segment unattached to the BLIP, by transmitting the packet to at least one other segment through a port selected to reach the destination segment.

22. A method as defined in claim 21, and further comprising:

checking the destination address of every packet destined for the same extended LAN segment as the one from which the packet was transmitted; and

taking corrective action depending on the data link layer destination address contained in the packet.

23. A method as defined in claim 22, wherein the step of taking corrective action includes:

discarding the packet if the data link layer destination address matches an entry in the ARP database corresponding to an IP destination address contained in the packet.

24. A method as defined in claim 22, wherein the step of taking corrective action includes, if there is no match between the data link layer destination address in the packet and an entry in the ARP database corresponding to an IP destination address contained in the packet:

substituting the ARP database entry for the data link layer destination address in the packet; and

sending a redirect message to a source host from which the packet was transmitted.

25. A method of operation of a configuration of interconnected local area networks (LANs) handling message traffic in accordance with a set of inter-network protocols that use a network addressing scheme, the method comprising the steps of:

configuring an extended local area network (LAN) to include a plurality of extended LAN segments connected by bridge-like IP routers (BLIPs);

receiving a packet of data at a BLIP;

determining whether the packet has been transmitted under the inter-network protocols;

processing packets that were not transmitted under the inter-network protocols in the manner of a conventional ridge, using unique station addresses to determine how to forward the received packets; and

processing inter-network protocol traffic in a manner analogous to a bridge, wherein a message packet received from an extended LAN segment attached to the BLIP is forwarded if necessary to at least one other extended LAN segment attached to the BLIP, using network addresses and network segment addresses, instead of unique station addresses, to determine how to forward the packets.

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

detecting and discarding address resolution messages requesting destination address information;

responding to the address resolution messages by transmitting a message packet having a special address code, but only if the requested destination address is on a different segment of the same extended LAN as the BLIP; and

forwarding any received message packet containing the special address code, to at least one other attached LAN segment;

whereby a host device may transmit to destinations on other extended LAN segments as though the destinations were on the same LAN.

BACKGROUND OF THE INVENTION

This invention relates generally to local area networks (LANs) of computers and, more particularly, to multiple LANs that are interconnected by bridges and routers. More specifically, the invention is concerned with a problem that arises in interconnected networks using a set of protocols generally known as TCP/IP. TCP stands for Transmission Control Protocol, and IP is Internet Protocol. The following background material introduces various computer network concepts and definitions. Those familiar with computer networks and TCP/IP may wish to skip to the subsection headed "The Problem."

Computer Network Background

A computer network is simply a collection of autonomous computers connected together to permit sharing of hardware and software resources, and to increase overall reliability. The qualifying term "local area" is usually applied to computer networks in which the computers are located in a single building or in nearby buildings, such as on a college campus or at a single corporate site. When the computers are further apart, the terms "wide area network" or "long haul network" are used, but the distinction is one of degree and the definitions sometimes overlap.

A bridge is a device that is connected to at least two LANs and serves to pass message frames or packets between LANs, such that a source station on one LAN can transmit data to a destination station on another LAN, without concern for the location of the destination. Bridges are useful and necessary network components, principally because the total number of stations on a single LAN is limited. Bridges can be implemented to operate at a selected layer of protocol of the network. A detailed knowledge of network architecture is not needed for an understanding of this invention, but a brief description follows by way of further background.

As computer networks have developed, various approaches have been used in the choice of communication medium, network topology, message format, protocols for channel access, and so forth. Some of these approaches have emerged as de facto standards, but there is still no single standard for network communication. However, a model for network architectures has been proposed and widely accepted. It is known as the International Standards Organization (ISO) Open Systems Interconnection (OSI) reference model. The OSI reference model is not itself a network architecture. Rather it specifies a hierarchy of protocol layers and defines the function of each layer in the network. Each layer in one computer of the network carries on a conversation with the corresponding layer in another computer with which communication is taking place, in accordance with a protocol defining the rules of this communication. In reality, information is transferred down from layer to layer in one computer, then through the channel medium and back up the successive layers of the other computer. However, for purposes of design of the various layers and understanding their functions, it is easier to consider each of the layers as communicating with its counterpart at the same level, in a "horizontal" direction.

The lowest layer defined by the OSI model is called the physical layer, and is concerned with transmitting raw data bits over the communication channel. Design of the physical layer involves issues of electrical, mechanical or optical engineering, depending on the medium used for the communication channel. The layer next to the physical layer is called the data link layer. The main task of the data link layer is to transform the physical layer, which interfaces directly with the channel medium, into a communication link that appears error-free to the next layer above, known as the network layer. The data link layer performs such functions as structuring data into packets or frames, and attaching control information to the packets or frames, such as checksums for error detection, and packet numbers.

Although the data link layer is primarily independent of the nature of the physical transmission medium, certain aspects of the data link layer function are more dependent on the transmission medium. For this reason, the data link layer in some network architectures is divided into two sublayers: a logical link control sublayer, which performs all medium-independent functions of the data link layer, and a media access control (MAC) sublayer. This sublayer determines which station should get access to the communication channel when there are conflicting requests for access. The functions of the MAC layer are more likely to be dependent on the nature of the transmission medium.

Bridges may be designed to operate in the MAC sublayer. Further details may be found in "MAC Bridges," P802.1D/D6, September 1988, a draft publication of IEEE Project 802 on Local and Metropolitan Area Network Standards, or in later drafts of this document.

The basic function of a bridge is to listen "promiscuously," i.e. to all message traffic on all LANs to which it is connected, and to forward each message it hears onto LANs other than the one from which the message was heard. Bridges also maintain a database of station locations, derived from the content of the messages being forwarded. Bridges are connected to LANs by paths known as "links." After a bridge has been in operation for some time, it can associate practically every station with a particular link connecting the bridge to a LAN, and can then forward messages in a more efficient manner, transmitting only over the appropriate link. The bridge can also recognize a message that does not need to be forwarded, because the source and destination stations are both reached through the same link. Except for its function of "learning" station locations, or at least station directions, the bridge operates basically as a message repeater.

As network topologies become more complex, with large numbers of LANs, and multiple bridges interconnecting them, operational difficulties can ensue if all possible LAN bridging connections are permitted. In particular, if several LANs are connected by bridges to form a closed loop, a message may be circulated back to the LAN from which it was originally transmitted, and multiple copies of the same message will be generated. In the worst case, messages will be duplicated to such a degree that the networks will be effectively clogged with these messages and unable to operate at all.

To prevent the formation of closed loops in bridged networks, IEEE draft publication P802.1D, referred to above, proposes a standard for a spanning tree algorithm that will connect the bridged network into a tree configuration, containing no closed loops, and spanning the entire network configuration. The spanning tree algorithm is executed periodically by the bridges on the interconnected network, to ensure that the tree structure is maintained, even if the physical configuration of the network changes. Basically, the bridges execute the spanning tree algorithm by sending special messages to each other to establish the identity of a "root" bridge. The root bridge is selected, for convenience, as the one with the smallest numerical identification. The algorithm determines which links of the bridges are to be active and which are to be inactive, i.e. disabled, in configuring the tree structure. One more piece of terminology is needed to understand how the algorithm operates. Each LAN has a "designated" link, which means that one of the links connectable to the LAN is designated to carry traffic toward and away from the root bridge. The basis for this decision is similar to the basis for selecting the root bridge. The designated link is the one providing the least costly (shortest) path to the root bridge, with numerical bridge identification being used as a tie-breaker. Once the designated links are identified, the algorithm chooses two types of links to be activated or closed: first, for each LAN its designated link is chosen, and second, for each bridge a link that forms the "best path" to the root bridge is chosen, i.e. a link through which the bridge received a message giving the identity of the root bridge. All other links are inactivated. Execution of the algorithm results in interconnection of the LANs and bridges in a tree structure, i.e. one having no closed loops.

Internet is a collection of networks, including Arpanet, NSFnet, regional networks such as NYsernet, local networks at a number of university and research institutions, and a number of military networks. The protocols generally referred to as TCP/IP were originally developed for use only through Arpanet and have subsequently become widely used in the industry. The protocols provide a set of services that permit users to communicate with each other across the entire Internet. The specific services that these protocols provide are not important to the present invention, but include file transfer, remote log-in, remote execution, remote printing, computer mail, and access to network file systems.

The basic function of the Transmission Control Protocol (TCP) is to make sure that commands and messages from an application protocol, such as computer mail, are sent to their desired destinations. TCP keeps track of what is sent, and retransmits anything that does not get to its destination correctly. If any message is too long to be sent as one "datagram," TCP will split it into multiple datagrams and makes sure that they all arrive correctly and are reassembled for the application program at the receiving end. Since these functions are needed for many applications, they are collected into a separate protocol (TCP) rather than being part of each application. TCP is implemented in the transport layer of the OSI reference model.

The Internet Protocol (IP) is implemented in the network layer of the OSI reference model, and provides a basic service to TCP: delivering datagrams to their destinations. TCP simply hands IP a datagram with an intended destination; IP is unaware of any relationship between successive datagrams, and merely handles routing of each datagram to its destination. If the destination is a station connected to a different LAN, the IP makes use of routers to forward the message.

A router, like a bridge, is a device connected to two or more LANs. Unlike a bridge, however, a router operates at the network layer level, instead of the data link layer level. Addressing at the network layer level makes use of a 32-bit address field for each host, and the address field includes a unique network identifier and a host identifier within the network. Routers make use of the destination network identifier in a message to determine an optimum path from the source network to the destination network. Various routing algorithms may be used by routers to determine the optimum paths. Typically, routers exchange information about the identities of the networks to which they are connected.

When a message reaches its destination network, a data link layer address is needed to complete forwarding to the destination host. Data link layer addresses are 48 bits long and are globally unique, i.e. no two hosts, wherever located, have the same data link layer address. There is a protocol called ARP (address resolution protocol), which obtains a data link layer address from the corresponding network layer address (the address that IP uses). Typically, each router maintains a database table from which it can look up the data link layer address, but if a destination host is not in this ARP database, the router can transmit an ARP request. This message basically means: "will the host with the following network layer address please supply its data link layer address." Only the addressed destination host responds, and the router is then able to insert the correct data link layer address into the message being forwarded, and to transmit the message to its final destination.

The Problem

As discussed above, bridges operate at the data link layer level and are effectively "transparent" to user stations or "hosts" connected to the LANs. That is to say, a message directed to a destination on a different LAN from the one to which the source of the message is connected, will reach the destination through a bridge without the source's knowing that tee destination is on a different LAN. Bridges work well for message traffic that is not using the TCP/IP protocols. However, for TCP/IP traffic a significant problem is sometimes caused by ARP messages, especially when bridges are used within an extended network of LANs. For some network implementations, ARP packets can be duplicated by bridges and this can result in "flurries" or even "storms" of ARP packets, which disrupt normal traffic flow. Ideally, ARP packets should be confined to the LAN in which they originate, but bridges are designed to be transparent to all traffic. One possible solution is to use a combination of a bridge and a router in every situation in which a bridge might be used, but providing full router functionality is more complex and more expensive than using conventional bridges.

The need for an alternative to bridges and routers is particularly critical in an "extended network" administered by a single institution. For example, a corporation or a university may have the need to configure a number of "subnets" or "network segments" that are interconnected into one extended network. From outside the extended network, there appears to be just a single network, i.e. there is one network identifier in the network layer address, and messages destined for a host computer within the extended network are addressed as if this were the case. Within the extended network, however, part of the host identifier field of the network layer address is used as a subnet address or network segment address. The network segments might be connected by bridges, but these would be subject to the ARP storm problem outlined above. Another problem with using bridges for TCP/IP traffic is that some IP data packets may be too large for a bridge to forward, and will then be discarded by the bridge.

It will be apparent from the foregoing that there is a need for an alternative to conventional bridges in interconnected networks handling TCP/IP traffic. Ideally, what is needed is a network interconnection device that can handle TCP/IP traffic without the added complexity of a router, and without the problems inherent in the use of bridges. The present invention satisfies this need, as will become apparent from the following summary.

SUMMARY OF THE INVENTION

The present invention resides in a bridge-like IP router (BLIP) that functions exactly like a bridge for non-TCP/IP traffic, and functions in a bridge-like manner for TCP/IP traffic, forwarding messages through a spanning tree and learning source and destination addresses, at a network layer level, by correlating the direction from which messages arrive with the source subnet addresses they contain. Thus the bridge-like IP router functions very much like a bridge, but at the network layer level of addressing.

Although the invention addresses a problem that arises in the specific context of the TCP/IP protocols, in a more general sense the invention applies to any inter-network protocols that operate at the network layer level, using an addressing scheme of network addresses and host addresses within each network. Basically, the invention is embodied in a bridge-like device that functions at this network layer level, as well as at a lower level at which globally unique host addresses are used.

As it relates more specifically to the TCP/IP protocols, the device of the invention comprises multiple ports for attaching the BLIP to multiple segments of an extended LAN, means for distinguishing received TCP/IP message traffic from non-TCP/IP message traffic, bridge means for processing non-TCP/IP message traffic exactly in the manner of a conventional bridge, and bridge-like means for processing TCP/IP traffic in a manner analogous to a bridge. A message packet received from an extended LAN segment attached to the BLIP is forwarded, if necessary, to