Router using multiple hop redirect messages to enable bridge like data forwarding

Description Submit all comments and votes

FIELD OF THE INVENTION

This invention relates to forwarding messages from a first link to another link, and more particularly relates to reducing the time required to forward data packets.

BACKGROUND OF THE INVENTION

Communications systems between computers are presently capable of connecting tens of thousands of computers. Typically, a computer will originate a message directed to another computer, and will transmit the message as a sequence of data packets onto the communications system. Because of the large number of computers connected to the system, and the large number of data packets transferred between the computers, congestion of packets on the system is an important problem.

Communications systems are often divided into a number of links. Typically, a link may be a local area network, where each local area network is capable of supporting a few hundred computers. A local area network will hereinafter be referred to as a LAN. The LANs are connected together by a number of different standard devices which forward packets. With the increasingly large size of modern communications systems, the time required to forward a data packet between LANs becomes an important parameter of system design.

Other types of links in a communications system may be, for example, a wide area network formed by joining other links such as LANs, a point to point connection between computers, etc. Congestion of system packet traffic is also an important problem in all link-to-link connections. Also, all types of links may be connected together by standard devices.

Before discussing standard devices used to connect links together, data packets and the headers of data packets added by different layers of the communications protocol must be discussed. A data packet is typically formed in a higher level of the communications protocol, and finally is transferred down to the Transport Layer which passes the packet into the Network layer. The Network layer attaches a header, the Network Layer Header, to the data packet, and then passes the packet into the Data Link Layer. The Data Link Layer then attaches a header, the Data Link Layer Header, to the data packet. The packet is then transmitted onto the communications system by the physical layer.

A packet, once transmitted onto the communications system, is then forwarded from link to link until it reaches its destination end station.

A first type of device connecting links of the communications system is a bridge. A bridge operates in the Data Link level of the communications protocol, which is the level immediately above the physical level. A bridge receives data packets from one link, typically a LAN, and then parses the Data Link Header. The bridge then makes a decision on what to do with the data packet, where the decision is based upon the contents found in the Data Link Header.

A second type of device linking LANs is a router. A router operates in the network layer, a layer above the data link layer. A router operates by parsing both the Data Link Header and the Network Layer Header, and making decisions based on the contents of both headers. Further, fields of the Network Layer Header are of variable length, and so the router must read the length of the variable fields from a field of the header, and then make parsing decisions based upon the indicated length. Accordingly, a router is slower than a bridge because it must parse an additional header, and must make more decisions based on the contents of the additional header, than does a bridge.

In some designs a bridge may be on the order of 200 times faster than a router in forwarding a data packet from a first link to a second link.

Even though a router is slower in forwarding packets from one link, such as a LAN, to another link, it is necessary to use routers rather than bridges at certain locations between multiple numbers of links. The router performs functions beyond those of a bridge, such as: forwarding along better routes than a bridge; incrementing a "hop count" field of a forwarded packet to show the number of passes of the packet through a router in order to prevent indefinite looping of the packet; preventing certain management traffic such as "hello" messages from end stations on one link from being forwarded to the other link; maintaining "network layer addresses" of stations on the links that it connects; fragmentation and reassembly of packets because of different protocols employed by different links; performing explicit handshaking protocols with end stations connected to links connected to the router; participating in routing algorithms, and other functions.

However, a difficulty in operation of large computer communications networks is that the time required for a router to forward messages may unduly decrease throughput on the communications system.

SUMMARY OF THE INVENTION

The invention is an apparatus for forwarding packets, and solves the difficulty of a router requiring too much time for forwarding a packet.

An apparatus for forwarding a data packet from a first link to a second link, has a first means for parsing a data link destination address field of a packet to be forwarded, and has a second means, responsive to a content of the data link destination address field as determined by the parsing, for deciding whether to forward the packet as a bridge or to forward the packet as a router. Further, the apparatus sends a redirect message to update the data link layer destination address used by the originating station to contain the data link layer address of the destination station where the destination station is on a link remote from the link of the originating station.

When a first data packet is forwarded from a first link to a second link, the apparatus behaves as a router by forwarding based upon parsing the Network Layer Header. The apparatus then passes the data link address of the receiving end station to the transmitting end station. Subsequent packets sent by the transmitting end station to the receiving end station then have the data link address of the receiving end station written into the Data Link Destination address field of the Data Link Header of the packet. For the subsequent packets the apparatus then behaves as a bridge by forwarding the subsequent packets based upon parsing of only the Data Link Header. For forwarding of subsequent packets, the apparatus is advantageously fast, in accordance with bridge operation.

An apparatus is provided for forwarding a packet from a first LAN to a second LAN. The apparatus is of the type capable of receiving a packet transmitted by a transmitting end station where the packet is sent to a receiving end station and the packet contains a data link address of the apparatus. The apparatus is capable of writing a second data link address into the packet and forwarding the packet to a second LAN.

The apparatus has a means for notifying the transmitting end station of a second data link address. The transmitting end station has a means, responsive to the notification, for the transmitting end station to transmit a subsequent packet having the second data link address in the subsequent packet. The apparatus has a means, responsive to the second data link address being included in the subsequent packet, for the apparatus to forward the subsequent packet to a station having the second data link address, where the forwarding of the subsequent packet is bridge type forwarding.

Further, when the receiving end station is on a LAN that is separated by several LANs, connected together by routers, from the LAN having the transmitting end station, the data link address of the receiving end station is sent to the transmitting end station. Subsequent packets sent by the transmitting end station are then forwarded between the intermediate LANs by the invention behaving as a bridge, and so the forwarding is advantageously fast.

Other and further aspects of the present invention will become apparent during the course of the following description and by reference to the accompanying drawings.

BRIEF DESCRIPTION OF THE DRAWINGS

Referring now to the drawings, in which like numerals represent like parts in the several views:

FIG. 1 is a logic diagram of two LANs connected by the invention.

FIG. 1A is a flow chart for operation of a brox in accordance with the invention.

FIG. 2 is a field diagram of a data packet in accordance with the invention.

FIG. 3 is a sequence of packets in accordance with the invention.

FIG. 4 is a logic diagram of multiple LANs connected in accordance with the invention.

FIG. 5 is a logic diagram of multiple LANs connected in accordance with the invention.

FIGS. 6A, 6B, 6C are a field diagram of a sequence of packets in accordance with the invention.

DETAILED DESCRIPTION

Summary Description

Capitalization will be used in this document to highlight names of fields of a packet, in order to improve readability of the document.

Referring now to FIG. 1, there is shown a communications link connection apparatus 100, a "brox", in accordance with the invention. The term "brox" is coined herein, and is defined as a box for connecting communications links in accordance with the present invention. A brox forwards as a router under certain conditions, but under other conditions forwards as a bridge. The word "brox" is an acronym constructed from the capitalized letters (Bridge Router bOX) for a box that behaves as a bridge or as a router. Also a brox may have behavior modes that are neither those of a standard bridge nor those of a standard router.

For communications between end stations on a single LAN, a router creates redirect messages for the originating station. A redirect message is defined for stations on a single LAN as a message which a router sends to an end station giving the end station an alternative data link layer address to which the end station may send future packets. In the event that the end station accepts the redirect message and uses the alternative data link layer address, which, for example, is the data link layer address of the destination station, then communications on that LAN are enhanced.

The protocol requires that an originating end station know the network layer address of a destination end station, but that the originating end station know only the data link layer address of a router connected to the link, and that the originating end station need not know the data link layer address of the intended destination station. The redirect message speeds communications on that LAN because the protocol further requires that when a router is connected to a LAN, the stations on that LAN send a first packet intended for another station on that LAN to the data link layer address of the router. And then the router both forwards the packet onto the same LAN and sends a redirect message to the originating station.

For a multiple hop data packet transmission, operation of the invention can be described in simple terms as follows: a data packet from a sending end station to a receiving end station generates a corresponding redirect message from a first brox to the sending end station. The redirect message tells the sending end station to use the data link address of the next brox. The second data packet generates a redirect message from the second brox, where the redirect message tells the sending end station to use the data link address of the next brox. And finally the last brox sends a redirect message telling the sending end station to use the data link address of the receiving end station. The broxs function as routers when a data packet is addressed to the data link address of the brox. However, the broxs function as bridges when the Data Link Destination Address field of the data packet does not contain a data link address of the brox.

A significant benefit of the invention is that, once the sending end station learns the data link address of the receiving end station, forwarding of later sent data packets is at bridge speed, rather than router speed. The forwarding delay at each brox my be as much as 200 times less when the brox functions as a bridge rather than as a router.

The invention greatly speeds forwarding of data packets.

FIRST EXEMPLARY EMBODIMENT

Referring again to FIG. 1, there is shown generally a communications system 101. Local Area Network (hereinafter referred to as LAN) 110 is coupled to LAN 112 by brox 100. LAN 110 has end station A 111A and end station B 111B. LAN 112 has end station C 113C. Both Local Area Networks, 110 and 112, may have additional end stations that are not shown in FIG. 1, and each LAN may, for example, each support as many as several hundred end stations.

Brox 100 forwards traffic generated on LAN 110 to LAN 112, and also forwards traffic generated on LAN 112 to LAN 110.

The internal connections of brox 100 are logically represented in FIG. 1.

A packet arriving at brox 100 may produce any one of a plurality of results, for example: the packet may be forwarded onto a link different from the originating link; or the packet may be forwarded onto the originating link; or the packet may be processed internally by the router and not forwarded, or for further examples, packets may be discarded and not forwarded.

By way of example, a packet arriving from LAN 110 enters brox 100 on line 115A where it is first processed by logic 115. In the event that the packet is to be forwarded by the brox behaving as a bridge, then logic 115 and control 119 close switch 116A by control line 119A and close switch 116B by control line 119B. Also logic 115 and control 119 open switch 114A by control line 119C and open switch 114B by control line 119D. The packet then progresses through brox 100 by being forwarded by bridge 116, and passes through logic 117 and line 117A onto LAN 112.

In the event that a packet arrives from LAN 100 on line 115A, and logic 115 determines that the packet is to be forwarded by brox 100 functioning as a router, then logic 115 and control 119 close switch 114A by control line 119C and close switch 114B by control line 119D. Also logic 115 and control 119 open switch 116A by control line 119A and open switch 116B by control line 119B. The packet is then forwarded by router 114 and leaves brox 100 by passing through logic 117 and line 117A.

In the further case that a packet enters brox 100 from LAN 112 on line 117A, and logic 117 determines that brox 100 is to forward the packet with brox 100 functioning as a bridge, then logic 117 and control 119 close switch 116B by control line 119B and close switch 116A by control line 119A. Also logic 117 and control 119 open switch 114B by control line 119D and open switch 114A by control line 119C. The packet then is forwarded by bridge 116 and leaves brox 100 through logic 115 and line 115A.

In the still further case that a packet enters brox 100 from LAN 112 on line 117A, and logic 117 determines that brox 100 is to forward the packet by functioning as a router, then logic 117 and control 119 close switch 114B by control line 119D and close switch 114A by control line 119C. Also logic 117 and control 119 open switch 116B by control line 119B and open switch 116A by control line 119A. The packet is then forwarded by router 114, and passes through logic 115 and leaves brox 100 on line 115A.

Switches 114A 114B 116A and 116B are operated by control 119, in cooperation with logic 115 and logic 117, on a packet by packet basis. Accordingly, brox 100 processes packets arriving from either LAN 112 or LAN 110 by forwarding them as either a bridge or as a router, as required.

Referring now to FIG. 2, there is shown a typical field structure for a data packet used by an end station of a LAN 110, 112 shown in FIG. 1. Data packet 120 is shown having a Data Link Header 122 and a Network Layer Header 124. When data packet 120 is created and transmitted onto a LAN, the network layer attaches Network Header 124 to the packet, and then the packet is handed down to the data link layer. The data link layer then attaches the Data Link Header 122 to the packet. Upon transmission, data packet 120 may have additional fields preceding the Data Link Header 122 such as, for example, preamble fields, and the precise structure of such preamble fields will depend upon the standard to which LAN 110 is designed. Such preamble fields are not shown in FIG. 2, as FIG. 2 focuses on those fields used by the invention.

Data Link Header 122 is shown in FIG. 2. Data Link Header 122 contains Data Link Destination Address field 126, and Data Link Source Address field 128, as also shown in FIG. 2. Other Data Link Header fields 130 are also shown in FIG. 2, but are not further described herein in that the invention focuses on the Data Link Destination Address field 126 and the Data Link Source Address field 128 of the Data Link Header 122. Data Link Destination Address field 126 is abbreviated DL D. Data Link Source Address field 128 is abbreviated DL S. Many LANs are constructed in accordance with a standard LAN specification. Examples of standard LAN specifications are: the IEEE 802 family of specifications, the IEEE 802.3 Ethernet bus using CSMA/CD, the IEEE 802.4 token bus, the IEEE 802.5 token ring, and the IEEE 802.2 data link layer; the ANSI Fiber Distributed Data Interface, FDDI; the ARPA Net TCP/IP; and many others. In many standard specifications for a LAN, the Data Link Destination Address field 126 is defined as 6 octets, and also the Data Link Source Address field 128 is defined as 6 octets. In a system that uses 8 bits for a byte, an octet and a byte are the same. Some systems may use other than 8 bits for a byte, and in that event the definition used for many LAN specifications is that the Data Link Destination Address field 126 and Data Link Source Address field 128 are defined as 6 octets each, where an octet is 8 bits. Also, the precise definition of Data Link Header "other" fields 130 will depend upon the standard to which the LAN 110 is designed.

Normal operation of a bridge and normal operation of a router will now be described.

Bridges

The Data Link Header 122 contains a number of fields, and the fields principally used by the bridge are: the Data Link Destination Address field 126; and, the Data Link Source Address field 128 (FIG. 2).

The bridge compares the address found in the Data Link Destination Address field with a forwarding table maintained in a database contained in the bridge, and also compares the contents of the Data Link Source Address field of the packet with a list of source addresses maintained for each link connected to the bridge. The bridge then, typically makes forwarding decisions based upon the contents of these fields.

Typical design rules for operation of a bridge are as follows, and include both rules for receipt of a packet and rules for forwarding a packet.

For receipt of a packet, a bridge tests the contents of the Data Link Destination Address field of the packet against internally maintained forwarding tables.

For forwarding, the bridge decides what to do with the packet, for example, as follows. Typically, for a bridge that uses the flooding and backward learning algorithm, the bridge makes the following decisions, based upon the contents of the Data Link Destination Address field of the packet: if the packet Data Link Destination Address is in the forwarding table of a link attached to the bridge, then forward the packet to the proper link, except, if the packet destination is on the link from which the packet originated, then disregard the packet; and, if the destination address is not in the forwarding table, then flood the packet to all of the links connected to the bridge, but not the link from which the packet originated. Also, typically, a bridge forwards packets having certain multicast or broadcast addresses in their Data Link Destination Address field, such as end station hello messages. A bridge attempts to make the links that it joins together operate as an extended LAN.

Also, if the content of the Data Link Source Address field of the packet is absent from the bridge forwarding tables, then the bridge adds to its appropriate forwarding table a correlation between the address contained in the Data Link Source Address field of the packet and the link from which the packet arrived. Any subsequent packets addressed to that address are then forwarded onto the correlated link. By updating its forwarding table using the arrival link of unknown packets, a bridge learns the correlation between arrival links and the source address of end stations either on those links or connected to those links from other links, and thereby builds up entries into its forwarding tables. Further, for example, there are many other ways that entries in in a bridge forwarding table may be compiled.

In addition to receiving and forwarding packets, bridges perform additional functions. For example, a bridge may have a plurality of ports in excess of two ports, where each port may, for example, be connected to a different link. And the bridge may turn off selected links in order to prevent looping of packets in a topologically complex communications network.

Routers

A router makes forwarding decisions based upon the content of the Network Layer Header 124 fields, and uses principally the Network Layer Destination Address field 140 and the Network Layer Source Address field 142 (FIG. 2). Also, a router must parse and read a field giving the lengths of the address fields, and then interpret the address fields based upon the contents of the length indicator fields. The length indicator fields are in the other fields 144. Other Network Layer Header fields are used by a router, however, at present we discuss only the decisions made by the router based upon these two address fields 140, 142.

Typically, an end station informs a local router what both the data link address and the network layer address of the end station is.

For receipt of a packet, typically a router receives a packet if: the Data Link Destination Address field contains the data link address of the router; or if the Data Link Destination Address field contains certain broadcast destination addresses, which are not presently of concern.

Also, typically, a router forwards a packet that it has received: to an end station if the end station is on a link, such as a LAN, connected to the router; or, to another router, and that router is chosen from a list by comparing the Network Layer Destination Address field of the packet with an entry in a forwarding table maintained by the receiving router, and sending the packet to the appropriate router.

For example, routers use the routing protocol in order to exchange explicit routing information amongst routers, and that information is used by each router to construct a forwarding database. The forwarding database consists of an association between network layer destination addresses, and forwarding information. The forwarding information consists of a link to forward the packet on, combined with a data link address to forward the packet to.

As a second example, the router forwarding table is typically built up by messages sent between routers, where a message from a router carries a list of network layer addresses of end stations on a LAN connected to the router. Typically, messages between routers may be link state packets, as are familiar to those skilled in the art.

Data packet traffic between end stations and a router, such as end station "hello" traffic, informs the router of the data link addresses of the end stations, and also the network layer address of the end station. The router then builds up a table for each link to which the router is directly attached showing the data link addresses of all end stations attached to that link. The router does not forward the hello traffic, and so is able to build up a table for each link showing the end stations attached to that link.

Routers exchange router "hello" messages. From the router hello traffic, routers learn the identity, including the data link source address of other routers in the communications network. Routers then exchange messages by which they inform other routers of the end stations that they service. From the messages received from other routers, a particular router learns which router to send a message to, where the message has a particular network layer destination address in the packet Network Layer Destination Address field.

From the router to router traffic, a router constructs a forwarding table correlating end station network layer addresses with a data link address of an appropriate router, and forwards a packet accordingly.

Another typical function of a router connected to a link such as a LAN is to operate a redirect protocol, such as the redirect protocol set out in the International Standards Organization standard ISO 9542. In standard ISO 9542, when a LAN that has a router connected into the LAN is first powered up, then the end stations and the router learn each others data link addresses through hello packets. When one end station on the LAN sends a first packet to another end station on the LAN, the packet is sent with the router data link address in the Data Link Address Field of the packet. The router then forwards the packet to the receiving end station, where the forwarding is based on the contents of the Network Layer Destination Address field of the packet. The sending end station learned the Network Layer Destination Address of the desired receiving end station from management traffic generated by the router.

After forwarding the packet with the Data Link Layer field containing the data link destination address of the desired receiving end station, the router then sends a redirect message to the sending end station. The redirect message causes the sending end station to write into an internal database of the sending end station a correlation between the network layer address of the receiving end station and the data link address of that station. The next data packet that the sending end station sends to the same receiving station is then sent with the data link address of the receiving station in the Data Link Destination Address field of the packet, rather than sending the packet to the router. A result of this redirect protocol is that traffic on the local LAN is improved, because after the first packet goes to the router, all subsequent pa