IN COMPUTER NETWORKS

FIELD OF INVENTION The present invention relates generally to computer networks and, more particularly, to apparatus and methods for selecting improved routing paths in computer networks.

BACKGROUND OF THE INVENTION In an autonomous system comprising at least two computer networks, it is necessary for certain network elements, typically hosts and routers, to know of other computer networks so as to be able to communicate with other network elements attached to those other computer networks. The methods by which certain network elements of a computer network learn about other computer networks, and hence other network elements within a system of computer networks, are commonly referred to as interior routing protocols. One widely used interior routing protocol is known as Routing Information Protocol (RIP) , which relies upon physical network broadcasts to disseminate routing and reachability information throughout the computer network system.

The underlying methodology of RIP is a straightforward implementation of distance-vector routing for local area networks. Network elements are classified as being either active (vocal) or passive (silent) . Active elements advertise, or broadcast, their routes to others, while passive elements listen and update their routes based upon the advertisements, or broadcasts, of others, but do not advertise, or broadcast, themselves. Typically, routers operate in an active RIP mode, while hosts operate in a passive RIP mode.

A network element operating in an active RIP mode typically broadcasts a message every 30 seconds. Each such message contains information taken from a routing database, or table, and comprises a message pair that contains a destination network address and an integer distance between

that network element and the destination network address. RIP uses a hop count metric to measure such an integer distance, wherein a router is defined to be one hop from directly connected networks, two hops from networks that are reachable through one other router, and so on. Thus, the number of hops, or the hop count, along a routing path from a given source to a given destination refers to the number of routers that a data packet would encounter along that routing path. Both active and passive RIP participants listen to all broadcast messages and update their routing tables according to the distance-vector routing algorithm described above. Eventually all routers and hosts will have a routing path to any given network stored in their routing tables. It should be noted, however, that RIP specifies that once a network element learns a route from another network element, it must keep that route until it learns of a better one. In other words, to prevent a router or host from oscillating between two or more equally efficient (equal cost) routing paths, RIP specifies that existing routing paths should be retained until a new routing path having a lower hop count is available.

To illustrate the above-described operation of RIP, refer to Figure 1, where there is shown a prior art computer network system 10 having two interconnected computer networks 12 and 14. Network 12 has several hosts 16, 18, 20, and 22, and several bridges 24, 26, 28, 30, 32, and 34. Network 14 also has several hosts 36, 38, 40, and 42, and several bridges 44, 46, 48, 50, 52, and 54. Located between and interconnecting the networks 12 and 14 are several routers 56, 58, 60, 62, 64, and 66, each having an associated routing table 68, 70, 72, 74, 76, and 78, respectively. Referring to Figure 2, there is shown a prior art integrated bridge/router device 80 comprising two bridges 82 and 84, a router 86, and an associated routing table 88, which provide interconnection means for two networks 90 and 92. Such a

device 80 is commonly used in computer network systems, such as the one described above. One such device is manufactured by the assignee of the present invention and is sold under the tradename LANplex. Referring again to Figure 1, router 60, for example, will broadcast an RIP update message that contains the pair (12,1) on network 14, meaning that router 60 can reach network 12 from network 14 in one hop (at cost 1) . Router 60 will also broadcast an RIP update message that contains the pair (14,1) on network 12, meaning that it can reach network 14 from network 12 in one hop (at cost 1) . Routers 56, 58, 62, 64, and 66 will also broadcast similar RIP update messages, but at some later time. Thus, since router 60 was the first router to broadcast and no lower cost routing paths were later broadcast, hosts 16, 18, 20, and 22 and hosts 36, 38, 40, and 42 will all have stored in associated internal routing tables routing paths between networks 12 and 14 through router 60. In other words, hosts 16, 18, 20, and 22 would send and receive data to and from hosts 36, 38, 40, and 42 only through routing paths utilizing router 60.

From the above-described illustration, it should be apparent that the particular aspect of RIP wherein hop counts are used to calculate the shortest path distance between a given source and a given destination does not always produce optimal, or even near optimal, results since bridges, and their associated delays, are not taken into account when determining the hop counts. Thus, it would be desirable to provide an apparatus and method for selecting improved routing paths in a computer network system having at least two computer networks by taking bridges into account when selecting such routing paths. Similarly, as illustrated below, it would also be desirable to provide an apparatus and method for selecting improved routing paths in an emulated Local Area Network (LAN) over an Asynchronous Transfer Mode (ATM) network.

LAN emulation enables the implementation of an emulated

LAN over an ATM network. An emulated LAN provides for the communication of data frames among all of the users in the emulated LAN, similar to a physical LAN. One or more emulated LAN's may run on the same ATM network. However, each emulated LAN is independent, and users cannot communicate directly across emulated LAN boundaries . Communication between emulated LAN's is possible only through routers or bridges, which may be implemented in a common ATM end station. An emulated LAN may be one of two types: Ethernet/IEEE

802.3 or IEEE 802.5 (Token Ring) . Each emulated LAN typically comprises a single LAN Emulation Service (LE Service) and a plurality of LAN Emulation Clients (LEC's) . An LE Service comprises a LAN Emulation Configuration Server (LECS) , a LAN Emulation Server (LES) , and a Broadcast and Unknown Server (BUS) . An LE Service may be implemented in an ATM end station (e.g., a bridge, router, or dedicated workstation) , or in a specific ATM network device (e.g., a switch) . An LE Service may be centralized or distributed throughout an ATM network.

Each LEC is part of an ATM end station and represents one or more users, each of which is identified by a Medium Access Control (MAC) address . Each LEC performs data forwarding, address resolution, and other functions for associated ATM end station users. Each LEC must be assigned to an LE Service of an emulated LAN before it can communicate with other LEC's within the emulated LAN. Communication between LEC's and between an LEC and its assigned LE Service is performed over ATM virtual channel connections (VCC's) . An LECS implements the assignment of individual LEC's to various emulated LAN's. Based upon its own policies, configuration databases, and information provided by LEC's, an LECS assigns any LEC which requests configuration information to a particular LE Service. The LECS assigns an LEC to a particular LE Service by giving the LEC the ATM address of an LES associated with that particular LE Service,

along with other necessary operating parameters. The LECS provides the ATM address of the LES to the LEC over a configuration VCC which is established between the LECS and the LEC. An LES implements the control coordination function for an emulated LAN. That is, an LES provides a facility for registering MAC addresses and/or route descriptors, and for resolving MAC addresses and/or route descriptors to ATM addresses. An LEC will register the users that it represents with the LES to which it is assigned. An LEC will also query its assigned LES when the LEC wishes to resolve an MAC address and/or route descriptor to an ATM address. The LES will either respond directly to the LEC which initiated the query or forward the query to other LEC's so that they may respond. An LEC communicates with its assigned LES over control VCC's which are established between the LEC and the LES.

An LES always exists with a BUS in an emulated LAN. A BUS handles all broadcast, multicast, and unknown data traffic to and from an LEC. That is, all broadcast, multicast, and unknown data traffic to and from an LEC passes through a BUS. A BUS receives and delivers this data traffic through multicast VCC's which are established between the BUS and each associated LEC. Multicast VCC's are established between a BUS and an associated LEC after the ATM address of the BUS is provided to the LEC by its assigned LES in an address resolution procedure.

Since an LES and a BUS always coexist in an emulated LAN, they may be coupled together into a combined LES/BUS server. In order to minimize the utilization of ATM network resources in an emulated LAN, a plurality of LES/BUS servers, or LES/BUS subservers, may be distributed throughout an ATM network. In such a case, each LEC is assigned to a "local" LES/BUS subserver, and the appropriate VCC's are established between each LEC and its local LES/BUS subserver. It should be noted that VCC's are also established between the LES/BUS

subservers.

An LEC which represents a router will periodically send an RIP update message to its local LES/BUS subserver over an established VCC so that the RIP update message may be distributed to other components within the emulated LAN. An RIP update message, which is always initiated by a router, contains network routing information regarding the router that initiated the RIP update message. It should be noted that RIP update messages are broadcast messages and, as such, must be handled by the BUS component of a local LES/BUS subserver. It should also be noted that RIP update messages are actually part of multicast data frames which are sent over established VCC's in an emulated LAN.

As described above, each RIP update message contains information taken from a routing table of the router that initiated the RIP update message, and comprises a message pair that contains a destination network address and an integer distance between the router that initiated the RIP update message and the destination network address. A hop count metric is used to measure the integer distance, wherein a router is defined to be one hop from directly connected networks, two hops from networks that are reachable through one other router, and so on. Thus, the number of hops, or the hop count, along a routing path from a given source to a given destination refers to the number of routers that a data packet will encounter while traveling along that routing path.

Certain network elements, such as hosts and routers, receive RIP update messages and update their routing tables accordingly so that eventually all hosts and routers will have stored in their routing tables a routing path to any given network. However, some of these routing paths may not be the most efficient routing path in terms of the utilization of network resources. For example, RIP specifies that once a network element learns a route from another network element, it must keep that route until it learns of

a better one. In other words, to prevent a router or host from oscillating between two or more equally efficient (equal cost) routing paths, RIP specifies that existing routing paths should be retained until a new routing path having a lower hop count is available. However, since RIP only takes into account routers when determining the hop count of a routing path, other network elements, such as bridges and switches, are not considered. Thus, it is possible that the advertised routing paths of two or more routers, although having the same hop count, are not equally efficient in terms of the utilization of network resources.

In view of the foregoing, it should be apparent that the particular aspect of RIP wherein hop counts are used to calculate the shortest path distance between a given source and a given destination does not always produce optimal, or even near optimal, results in an emulated LAN since some network elements, such as bridges and switches, and their associated delays, are not taken into account when determining the hop counts. Thus, it would be desirable to provide an apparatus and method for selecting improved routing paths in an emulated LAN over an ATM network.

SUMMARY OF THE INVENTION

In accordance with the present invention, an apparatus and method for selecting improved routing paths in a computer network system having at least two computer networks is disclosed. Such an apparatus and method are realized by having network bridges in the computer network system identify and, in certain circumstances, modify RIP update messages according to information retrieved from a routing table, of an associated network router. More particularly, the network bridges modify RIP update messages so that they will more accurately reflect the position of the network router that broadcast the RIP update message, relative to the position of the associated network router, with respect to

any given destination network. Thus, the presently disclosed apparatus and method essentially take network bridges into account when determining the best possible routing paths within the computer network system. As a consequence, more direct routing paths are typically utilized and unnecessary delays through bridges are avoided.

In further accordance with the present invention, an apparatus and method for selecting improved routing paths in an emulated LAN over an ATM network is disclosed. The apparatus and method are realized by having an editor associated with a distributed LAN emulation server selectively modify RIP update messages according to information retrieved from an associated routing table. More particularly, the editor modifies RIP update messages so that they will more accurately reflect the position of the network router that broadcast the RIP update message, relative to the position of a network router associated with the distributed LAN emulation server, with respect to any given destination network. Thus, the presently disclosed apparatus and method essentially take other network elements, such as bridges and switches, into account when determining the best possible routing paths within an ATM network. As a consequence, more direct routing paths are typically utilized and unnecessary delays through some network elements, such as bridges and switches, are avoided.

BRIEF DESCRIPTION OF THE DRAWINGS

The present invention will be more fully understood by reference to the following detailed description and the appended drawings of which:

Figure 1 is a schematic block diagram of a prior art computer network system having two computer networks interconnected by several routers; Figure 2 is a schematic block diagram of a prior art integrated bridge/router device for use in a computer network

system having at least two computer networks;

Figure 3 is a schematic block diagram of a system of computer networks according to the present invention;

Figure 4 is a schematic block diagram of an integrated bridge/router device according to the present invention;

Figure 5 is a schematic block diagram of an alternate embodiment of a system of computer networks in accordance with the present invention;

Figure 6 is a flowchart illustrating an RIP update message modification method in accordance with the present invention;

Figure 7 is a block diagram illustrating a prior art topology of a typical emulated LAN over an ATM network;

Figure 8 is a block diagram illustrating a prior art topology of an emulated LAN having a plurality of LES/BUS subservers distributed throughout an ATM network;

Figure 9 is a block diagram illustrating the topology of an emulated LAN having a plurality of LES/BUS subservers distributed throughout an ATM network along with a corresponding plurality of associated RIP update message editors and associated routing tables in accordance with the present invention;

Figure 10 is a block diagram illustrating the various VCC's which are established between each LEC and its local LES/BUS subserver in an emulated LAN; and

Figure 11 is a flowchart illustrating an RIP update message modification method in accordance with the present invention.

DETAILED DESCRIPTION OF THE INVENTION

Referring to Figure 3, there is shown a schematic block diagram of a computer network system 100. Many of the components of this system 100 are common with those shown in Figure 1, and so they share common numerical designations.

For instance, the computer networks 12 and 14, the hosts 16,

18, 20, 22, 36, 38, 40, and 42, and the routers 56, 58, 60, 62, 64, and 66 are all common between the system 10 of Figure 1 and the system 100 of Figure 3.

The system 100 comprises bridges 102, 104, 106, 108, 110, 112, 114, 116, 118, 120, 122, and 124. The system 100 also comprises routing tables 126, 128, 130, 132, 134, and 136. The bridges 102, 104, 106, 108, 110, 112, 114, 116, 118, 120, 122, and 124 are capable of accessing information that is contained in associated routing tables 126, 128, 130, 132, 134, and 136. The bridges 102, 104, 106, 108, 110, 112, 114, 116, 118, 120, 122, and 124 are also capable of identifying and, in certain circumstances, modifying RIP update messages based upon information retrieved from the associated routing tables, 126, 128, 130, 132, 134, and 136, as will be described in more detail below.

To better illustrate the presently disclosed method and apparatus, the system 100 is also shown comprising a third computer network 140 having a host 142 and a bridge 144, which has access to routing table 134, and a fourth computer network 150 having a host 152 and a bridge 154, which has access to routing table 130.

As described above, router 60, for example, will broadcast an RIP update message containing the pair (12,1) on network 14 and an RIP update message containing the pair (14,1) on network 12. It should be noted that the RIP update messages broadcast by router 60 on networks 12 and 14 will also contain the pair (150,1) , meaning that router 60 can reach network 150 at cost 1. It should also be noted that, according to the commonly known "split horizon" concept, either the RIP update message broadcast by router 60 on network 12 or the RIP update message broadcast by router 60 on network 14 will also contain the pair (140,2) , meaning that router 60 can reach network 140 at cost 2. It should further be noted that, according to the commonly known "split horizon with poison reverse" concept, the RIP update message broadcast by router 60 on network 12 or the RIP update

message broadcast by router 60 on network 14 will also contain the pair (140,16), meaning that network 140 cannot be reached through router 60, as will be described in detail below. It should additionally be noted that router 60 will also broadcast an RIP update message containing the pairs (12,1) , (14,1) and (140,2) on network 150.

Upon receiving the RIP update message containing the pairs (12,1), (150,1), and possibly either (140,2) or

(140,16) on network 14 from router 60, bridge 120, for example, will access the associated routing table 132. An illustration of the contents of this routing table 132 is shown below.

destination # of router hops thru network (metric) router

12 1 XX

14 1 XX

140 2 64

150 2 60

It should be noted that in accordance with the most widely accepted version of RIP, a routing table typically counts an associated router when listing the number of router hops between the associated router and any given destination network. Thus, in the above illustration of routing table 132, the number of router hops between router 62 and networks 12 and 14 is one since router 62 is directly connected to networks 12 and 14. Also, the number of router hops between router 62 and networks 140 and 150 is two since any routing path from router 62 to either of networks 140 and 150 must go through at least one additional router, namely routers 64 and 60, respectively. It should also be noted that the symbol XX in the above illustration represents the fact that any routing paths from router 62 to either of networks 12 and 14 do not go through any other routers. It should further

be noted that the present invention is applicable for use in accordance with the lesser accepted versions of RIP, wherein a routing table does not count an associated router when listing the number of router hops between the associated router and any given destination network.

After receiving the RIP update message containing the pairs (12,1), (150,1) , and possibly either (140,2) or

(140,16) on network 14 from router 60, bridge 120 will compare the hop count metrics that are contained in the associated routing table 132 with the hop count metrics that are contained in the RIP update message broadcast from router 60 for each destination network. If the value of a hop count metric in a pair in the received RIP update message for any given destination network is not equal to the value of a hop count metric in the routing table 132 for a corresponding destination network, then the bridge 120 will forward the RIP update message without modification of that pair to any connected network elements, namely router 62 and bridge 122. If, on the other hand, the value of a hop count metric in a pair in the received RIP update message for any given destination network is equal to the value of a hop count metric in the routing table 132 for a corresponding destination network, then the bridge 120 will modify the RIP update message by increasing the value of the hop count metric in that particular pair and then forward the RIP update message to any connected network elements; i.e. router 62 and bridge 122. In other words, bridge 120 will modify the RIP update message of router 60 so that it will more accurately reflect the position of router 60, relative to the position of router 62, with respect any given destination network.

In the specific example set forth above, bridge 120 will modify the RIP update message broadcast on network 14 from router 60 so that it will contain the pairs (12,16) , (150,1) , and possibly (140,16) . Thus, the first pair will be modified by increasing the value of its hop count metric to 16 since

the original value of its hop count metric was equal to the value of the corresponding hop count metric in the routing table 132. It should be noted that if a third pair of (140,2) was received in the RIP update message broadcast on network 14 from router 60, it will also be modified by increasing the value of its hop count metric to 16 since the original value of its hop count metric was equal to the value of the corresponding hop count metric in the routing table 132. The actual value to which the hop count metrics are increased need only be greater than the corresponding hop count metrics in the routing table 132. The modified hop count metric value of 16 was chosen in the above-described example since that is the value used in RIP operation to indicate that a destination network is not reachable using the router that initially broadcast the RIP update message.

As with respect to router 60, routers 56, 58, 62, 64, and 66 will also broadcast RIP update messages containing message pairs which reflect their proximity with respect to any given destination network as measured by hop count metrics. These RIP update messages will then be processed by the bridges which receive them according to the above- described RIP update message modification scheme. The result of this ongoing process is that the network elements which receive the modified RIP update messages will select a near optimum routing path to any given destination network.

The above-described RIP update message modification technique thus essentially takes bridges into account when determining the best possible routing path within a computer network system. Such was heretofore absent in the operation of RIP, resulting in efficiency degradation within the system.

Before proceeding with any further explanation of the present invention, it should be noted that there is no need for the bridges 102, 104, 106, 108, 110, 112, 114, 116, 118,

120, 122, 124, 144, and 154 to process the RIP update

messages broadcast by their associated routers 56, 58, 60, 62, 64, and 66, respectively, since routers 56, 58, 60, 62, 64, and 66 have access to the information contained in their associated routing tables 126, 128, 130, 132, 134, and 136, and the routers 56, 58, 60, 62, 64, and 66 take this information into account when formatting the RIP update messages.

Figure 4 illustrates a block diagram of an integrated bridge/router device 160 according to the present invention. Many of the components of this integrated bridge/router device 160 are common with those shown in Figure 2, and so they share common numerical designations. For instance, the computer networks 90 and 92 and the router 86 are all common between the integrated bridge/router device 80 of Figure 2 and the integrated bridge/router device 160 of Figure 4.

The integrated bridge/router device 160 comprises bridges 162 and 164, and a routing table 166. As with respect to bridges 102, 104, 106, 108, 110, 112, 114, 116, 118, 120, 122, 124, 144, and 154 of Figure 3, bridges 162 and 164 are capable of identifying and, in certain circumstances, modifying RIP update messages based upon information retrieved from the associated routing table 166. As with respect to the routing tables 126, 128, 130, 132, 134, and 136 of Figure 3, routing table 166 allows the associated bridges 162 and 164 to access information contained therein. Thus, the presently disclosed integrated bridge/router device 160 may be employed in the computer network system 100 of Figure 3, or any other network system containing a plurality of interconnected networks which are interconnected by routers and bridges.

Figure 5 illustrates a block diagram of a computer network system 170 comprising a plurality of computer networks which are operable in accordance with the presently disclosed method. Many of the components of the system 170 are common with those shown in Figures 1 and 3, and so they share common numerical designations.

The system 170 comprises bridges 172, 174, 176, 178, 180, 182, 184, 186, 188, 190, 192, 194, 220, and 230, and routing information tables 196, 198, 200, 202, 204, 206, 208, 210, 212, 214, 216, 218, 222, and 232. As with respect to bridges 102, 104, 106, 108, 110, 112, 114, 116, 118, 120,

122, 124, 144, and 154 of Figure 3, bridges 172, 174, 176, 178, 180, 182, 184, 186, 188, 190, 192, 194, 220, and 230 are capable of identifying and, in certain circumstances, modifying RIP update messages according to information provided by the associated routing information tables 196, 198, 200, 202, 204, 206, 208, 210, 212, 214, 216, 218, 222, and 232. Routing information tables 196, 198, 200, 202, 204, 206, 208, 210, 212, 214, 216, 218, 222, and 232 are unique in that they contain routing information for any routers which are directly connected to associated bridges 172, 174, 176, 178, 180, 182, 184, 186, 188, 190, 192, 194, 220, and 230. These routing information tables 196, 198, 200, 202, 204, 206, 208, 210, 212, 214, 216, 218, 222, and 232 allow associated bridges 172, 174, 176, 178, 180, 182, 184, 186, 188, 190, 192, 194, 220, and 230 to access the routing information contained therein. Thus, these routing information tables 196, 198, 200, 202, 204, 206, 208, 210, 212, 214, 216, 218, 222, and 232 are separate from the routing tables 68, 70, 72, 74, 76, and 78, although both contain similar information. Such routing information tables 196, 198, 200, 202, 204, 206, 208, 210, 212, 214, 216, 218, 222, and 232 are beneficial when the bridges 172, 174, 176, 178, 180, 182, 184, 186, 188, 190, 192, 194, 220, and 230 and the associated routers 56, 58, 60, 62, 64, and 66 are located remote from each other.

In operation, bridges 172, 174, 176, 178, 180, 182, 184, 186, 188, 190, 192, 194, 220, and 230 of system 170 will modify RIP update messages broadcast by unassociated routers if it is determined upon comparing the hop count metrics that are contained in these RIP update messages with the hop count metrics that are contained in the associated routing

information tables 196, 198, 200, 202, 204, 206, 208, 210, 212, 214, 216, 218, 222, and 232 that preferable, more direct, routing paths are available. In other words, bridges 172, 174, 176, 178, 180, 182, 184, 186, 188, 190, 192, 194, 220, and 230 will modify RIP update messages broadcast by unassociated routers so that they will more accurately reflect the positions of associated routers 56, 58, 60, 62, 64, and 66, relative to the positions of the unassociated routers, with respect any given destination network. Figure 6 illustrates a flowchart depicting the typical steps of an RIP update message modification method 240 according to the present invention. In a first step 242, an RIP message is received and a determination is made whether such an RIP message is an RIP update message. At this point it should be noted that this first step 242, as well as all of the subsequent steps, are essentially performed by a single bridge based upon information contained in an associated routing table.

If the RIP message is not an RIP update message, the RIP message is processed and forwarded in a manner consistent with typical RIP operation. If, on the other hand, the RIP message is an RIP update message, then, in a second step 244, a first message pair in the RIP update message is examined. In a third step 246, a determination is made as to whether or not a routing path is listed in the associated routing table for the destination network address contained in the first message pair. If there is no routing path listed in the associated routing table for the destination network address contained in the first message pair, then the method 240 directs skipping to a subsequent sixth step 252, which is described in detail below. If, on the other hand, there is a routing path listed in the associated routing table for the destination network address contained in the first message pair, then, in a fourth step 248, a comparison is made between the hop count metric that is contained in the associated routing table and the hop count metric that is

contained in the RIP update message. If the value of the hop count metric in the RIP update message is not equal to the value of the hop count metric in the routing table, then the method 240 directs skipping to the sixth step 252, which, again, is described in detail below. If, on the other hand, the value of the hop count metric in the RIP update message is equal to the value of the hop count metric in the routing table, then, in a fifth step 250, the hop count metric in the RIP update message is modified by increasing the value of the hop count metric in the RIP update message.

Once the modification in the fifth step 250 is completed, then, in the sixth step 252, a determination is made as to whether there are more message pairs in the RIP update message. If there are no more message pairs in the RIP update message, then the RIP update message is further processed and forwarded in a manner consistent with typical RIP operation. If, on the other hand, there is at least one more message pair in the RIP update message, then, in a seventh step 254, the next message pair in the RIP update message is examined and processed in the manner described above with respect to steps 246 through 252.

Referring to Figure 7, a block diagram is provided illustrating the topology of a prior art emulated Local Area Network (LAN) 310 over an Asynchronous Transfer Mode (ATM) network 312. The emulated LAN 310 comprises a plurality of LAN Emulation Clients (LEC's) 314 and a single LAN Emulation Service (LE Service) 316. Each LEC 314 is a part of an ATM end station which may comprise a host 324, a bridge 326, or a network router 328. The LE Service 316 comprises a LAN Emulation Configuration Server (LECS) 318, a LAN Emulation Server (LES) 320, and a Broadcast and Unknown Server (BUS) 322. It should be noted that the LES 320 and the BUS 322 are shown coupled together as a combined LES/BUS server 330 because they always coexist in an emulated LAN. To minimize resource utilization in the ATM network 312, it is possible to distribute a plurality of the LES/BUS

servers 330 throughout the ATM network 312, and to assign each LEC 314 to a "local" LES/BUS server 330. For example, referring to Figure 8, an emulated LAN 340 is shown with a plurality of LES/BUS subservers 342 distributed throughout the ATM network 312. Each LEC 314 is typically assigned to a local LES/BUS subserver 342, thereby forming a corresponding plurality of LES/BUS subserver groups 344, 346, 348, and 350. The LES/BUS subservers 342 in the LES/BUS subserver groups 344, 346, 348, and 350 operate in a manner that is similar to the LES/BUS server 330 described above, but they result in less utilization of resources in the ATM network 312 since messages sent between LEC's 314 and local LES/BUS subservers 342 are required to travel shorter distances through the ATM network 312. To further minimize resource utilization in the ATM network 312, the present invention provides an apparatus and method for selectively modifying Routing Information Protocol

(RIP) update messages which are received by and then transmitted from LES/BUS subservers 342. More particularly, and with reference to Figure 9, an emulated LAN 360 having a plurality of LES/BUS subservers 342 is shown wherein each of the LES/BUS subservers 342 has an associated RIP Update

Message Editor (RUME) 362 and an associated Routing Table

(RT) 364 for selectively modifying RIP update messages which are received by and then transmitted from an associated LES/BUS subserver 342. It should be noted that, except as otherwise described below, the emulated LAN 360 operates in the manner defined in the specification entitled, LAN Emulation Over ATM, Version 1.0, The ATM Forum Technical Committee, January, 1995, which is hereby incorporated by reference.

Each LEC 314 in the emulated LAN 360 is assigned to an LES 320 and a BUS 322 of a local LES/BUS subserver 342 during an initialization phase. During this initialization phase, each LEC 314 is provided with the ATM address of its assigned LES 320 and BUS 322, and virtual channel connections (VCC's)

are established between each LEC 314 and its assigned LES 320 and BUS 322. After this initialization phase is completed, each LEC 314 which represents a router 328 will periodically send a Routing Information Protocol (RIP) update message to its local LES/BUS subserver 342 over an established VCC so that the RIP update message may be distributed to other components within the emulated LAN 360. As described below, an RIP update message, which is always initiated by a router 328, contains network routing information regarding the router 328 that initiated the RIP update message.

It should be noted that RIP update messages are broadcast messages and, as such, must be handled by the BUS component 322 of a local LES/BUS subserver 342. It should also be noted that RIP update messages are actually part of multicast data frames which are sent over established VCC's in the emulated LAN 360.

The VCC's which are established between each LEC 314 and its local LES/BUS subserver 342 include a multicast point-to- point VCC and a multicast point-to-multipoint VCC. The multicast point-to-point VCC allows an LEC 314 to send multicast data frames containing RIP update messages to its local LES/BUS subserver 342. The multicast point-to- multipoint VCC allows an LES/BUS subserver 342 to distribute multicast data frames containing RIP update messages to all of the "local" LEC's 314 within a particular LES/BUS subserver group 344, 346, 348, or 350. It should be noted that the multicast point-to-multipoint VCC may alternatively be provided by one or more multicast point-to-point VCC's at the discretion of the LE Service 316. In addition to the above-described VCC's, an inter- server point-to-multipoint VCC is established for each LES/BUS subserver 342 within the emulated LAN 360. This inter-server point-to-multipoint VCC allows each LES/BUS subserver 342 to distribute multicast data frames containing RIP update messages to other LES/BUS subservers 342 within the emulated LAN 360. These other LES/BUS subservers 342 may

then use a multicast point-to-multipoint VCC to distribute the multicast data frames to all of the "local" LEC's 314 within their particular LES/BUS subserver group 344, 346, 348, or 350. However, before these other LES/BUS subservers 342 distribute the multicast data frames to their "local" LEC's 314, the RIP update messages contained in the multicast data frames may be modified by the RUME 362 and the RT 364 associated with each LES/BUS subserver 342 in accordance with the present invention. Referring to Figure 10, an emulated LAN 370 is shown illustrating the various VCC's which are established between each LEC 314 and its local LES/BUS subserver 342. A multicast point-to-point VCC 372 is directed from each LEC 314 to its local LES/BUS subserver 342, and a multicast point-to-multipoint VCC 374 is directed from each LES/BUS subserver 342 to all of the "local" LEC's 314 within a corresponding LES/BUS subserver group 377, 378, or 379. An inter-server point-to-multipoint VCC 376 is directed from each LES/BUS subserver 342 to every other LES/BUS subserver 342 within the emulated LAN 370. These inter-server point- to-multipoint VCC's 376 allow each LES/BUS subserver 342 to distribute multicast data frames containing RIP update messages to other LES/BUS subservers 342 within the emulated LAN 360. These other LES/BUS subservers 342 may then use a multicast point-to-multipoint VCC 374 to distribute the multicast data frames to all of the "local" LEC's 314 within a corresponding LES/BUS subserver group 377, 378, or 379. However, before these other LES/BUS subservers 342 distribute the multicast data frames to their "local" LEC's 314, the RIP update messages contained in the multicast data frames may be modified by the RUME 362 and the RT 364 associated with each LES/BUS subserver 342 in accordance with the present invention.

As described above, each RIP update message contains information taken from a routing table of the network router that initiated the RIP update message, and includes at least

one message pair containing a destination network address and an integer distance between the network router that initiated the RIP update message and the destination network address. A hop count metric is used to measure the integer distance, wherein a network router is defined to be one hop from directly connected networks, two hops from networks that are reachable through one other network router, and so on. Thus, the number of hops, or the hop count, along a routing path from a given source to a given destination refers to the number of network routers that a data packet will encounter while traveling along that routing path.

Certain network elements, such as hosts and routers, receive RIP update messages and update their routing tables accordingly so that eventually all network hosts and routers will have stored in their routing tables a routing path to any given network. However, some of these routing paths may not be the most efficient routing path in terms of the utilization of network resources. For example, RIP specifies that once a network element learns a route from another network element, it must keep that route until it learns of a better one. In other words, to prevent a network host or router from oscillating between two or more equally efficient (equal cost) routing paths, RIP specifies that existing routing paths should be retained until a new routing path having a lower hop count is available. However, since RIP only takes into account network routers when determining the hop count of a routing path, other network elements, such as bridges and switches, are not considered. Thus, it is possible that the advertised routing paths of two or more network routers, although having the same hop count, are not equally efficient in terms of the utilization of network resources. The major factor in determining such network resource utilization efficiency is the location of the network routers within the network system. As described above, the present invention addresses the above-described problem by providing a network bridge for

selectively modifying RIP update messages according to information retrieved from a routing table of an associated network router. More particularly, a network bridge is provided to selectively modify RIP update messages so that the RIP update messages more accurately reflect the position of the network router that initiated a particular RIP update message, relative to the position of the network router associated with the network bridge, with respect to any given destination network. In the case of the emulated LAN 360 shown in Figure 9, an LES/BUS subserver 342 is provided having an associated RUME 362 for selectively modifying RIP update messages according to information retrieved from an associated RT 364. More particularly, an RUME 362 in association with an RT 364 are provided to selectively modify RIP update messages so that the RIP update messages more accurately reflect the position of the LEC 314, and hence the network router 328, that sent a particular RIP update message, relative to the position of the LES/BUS subserver 342 that is associated with the RUME 362 and the RT 364, and hence relative to the position of any LEC's 314 and network routers 328 that are "local" to the LES/BUS subserver 342 that is associated with the RUME 362 and the RT 364, with respect to any given destination network. In this manner, the utilization of network resources is reduced by having "local" ATM end stations (i.e., end stations within a particular LES/BUS subserver group 344, 346, 348, or 350) utilize the routing paths provided by "local" network routers 328, rather than routing paths provided by other network routers 328 within the emulated LAN 360. At this point it should be noted that each RT 364 typically includes entries for all destination networks, and each entry typically includes a hop count value for a "local" network router 328.

When an LES/BUS subserver 342 receives an RIP update message from a "local" LEC 314, the RUME 362 associated with the LES/BUS subserver 342 will update, if necessary, the

associated RT 364. That is, if the RT 364 does not have an initial entry for a routing path from a given source to a given destination, and the newly received RIP update message indicates that a "local" network router 328 can provide such a routing path, then the RUME 362 will update the RT 364 by adding an entry to the RT 364 which specifies that the "local" network router 328 can provide that routing path within a certain number of hop counts. Also, if the hop count for a routing path from a given source to a given destination may be improved (e.g., a lower hop count routing path may be provided) in view of information contained in the newly received RIP update message, then the RUME 362 will update the RT 364 by modifying the appropriate routing path entry in the RT 364 to reflect the improved routing path which can be provided by the "local" network router 328.

After an LES/BUS subserver 342 receives an RIP update message from a "local" LEC 314, the LES/BUS subserver 342 forwards the RIP update message to the other "local" LEC's 314 within the particular LES/BUS subserver group 344, 346, 348, or 350, and to other LES/BUS subservers 342 within the emulated LAN 360. The other "local" LEC's 314 within the particular LES/BUS subserver group 344, 346, 348, or 350 will provide the RIP update message directly to their associated end stations. The other LES/BUS subservers 342 within the emulated LAN 360, however, will utilize their associated

RUME's 362 and RT's 364 to selectively modify the RIP update message so that it more accurately reflects the position of the LEC 314, and hence the network router 328, that sent the RIP update message, relative to the position of these other LES/BUS subservers 342, and hence relative to the position of any LEC's 314 and network routers 328 that are "local" to these other LES/BUS subservers 342, with respect to any given destination network. That is, each RUME 362 will compare the contents of the RIP update message to the contents of their associated RT 364 and selectively modify the contents of the RIP update message. More specifically, the RUME 362 will

compare the hop count values that are contained in the associated RT 364 with the hop count values that are contained in message pairs within the RIP update message for each destination network and selectively modify the contents of the RIP update message.

If the value of a hop count in a message pair in the RIP update message for any given destination network is not equal to the value of a hop count in the RT 364 for a corresponding destination network, then the RUME 362 will not modify that message pair in the RIP update message and the associated LES/BUS subserver 342 will forward the RIP update message without modification of that message pair to all of the "local" LEC's 314 within the particular LES/BUS subserver group 344, 346, 348, or 350. If, on the other hand, the value of a hop count in a message pair in the RIP update message for any given destination network is equal to the value of a hop count in the RT 364 for a corresponding destination network, then the RUME 362 will modify the RIP update message by increasing the value of the hop count in that particular message pair and the associated LES/BUS subserver 342 will forward the modified RIP update message to all of the "local" LEC's 314 within the particular LES/BUS subserver group 344, 346, 348, or 350. In other words, the RUME 362 will modify the RIP update message so that it will more accurately reflect the position of the LEC 314, and hence the network router 328, that sent the RIP update message, relative to the position of the LES/BUS subserver 342 that is associated with the RUME 362 and the RT 364, and hence relative to the position of any LEC's 314 and network routers 328 that are "local" to the LES/BUS subserver 342 that is associated with the RUME 362 and the RT 364, with respect to any given destination network. The actual value to which the hop counts are increased need only be greater than the corresponding hop counts in the RT 364. Figure 11 illustrates the various steps of a method 380 for modifying an RIP update message in accordance with the

present invention. In a first step 382, an RIP message is received by an LES/BUS subserver from another LES/BUS subserver and a determination is made by the receiving LES/BUS subserver as to whether such an RIP message is an RIP update message. It should be noted that this first step 382, as well as all of the subsequent steps, are performed by a single LES/BUS subserver along with an associated RUME and RT.

If the RIP message is not an RIP update message, the LES/BUS subserver processes and forwards the RIP message in a manner consistent with typical emulated LAN operation. If, on the other hand, the RIP message is an RIP update message, then, in a second step 384, a first message pair in the RIP update message is examined by the RUME. In a third step 386, a determination is made by the RUME as to whether or not a routing path is listed in the associated RT for the destination network address contained in the first message pair. If there is no routing path listed in the associated RT for the destination network address contained in the first message pair, then the method 380 directs skipping to a subsequent sixth step 392, which is described below. If, on the other hand, there is a routing path listed in the associated RT for the destination network address contained in the first message pair, then, in a fourth step 388, a comparison is made between the value of the hop count that is contained in the associated RT and the value of the hop count that is contained in the RIP update message. If the value of the hop count in the RIP update message is not equal to the value of the hop count in the RT, then the method 380 directs skipping to the sixth step 392, which, again, is described below. If, on the other hand, the value of the hop count in the RIP update message is equal to the value of the hop count in the RT, then, in a fifth step 390, the value of the hop count in the RIP update message is modified by the RUME by increasing the value of the hop count in the RIP update message.

Once the modification in the fifth step 390 is completed, then, in the sixth step 392, a determination is made by the RUME as to whether there are more message pairs in the RIP update message. If there are no more message pairs in the RIP update message, then the LES/BUS subserver processes and forwards the RIP update message in a manner consistent with typical emulated LAN operation. That is, the LES/BUS subserver forwards the modified RIP update message to all of the "local" LEC's within the particular LES/BUS subserver group. If, on the other hand, there is at least one more message pair in the RIP update message, then, in a seventh step 394, the next message pair in the RIP update message is examined by the RUME and processed in the manner described above with respect to steps 386 through 392. It will be understood by those of ordinary skill in the art that other embodiments and variations on the presently disclosed embodiments may be envisioned without departing from the inventive concepts disclosed herein. Accordingly, the present invention is not to be viewed as limited, except in accordance with the scope and spirit of the appended claims .