US 5,862,344 AGrant

Apparatus and Methods for Routing Data Packets Through a Processing System Network

Issue Date:1999-01-19

•33 Claims

•9 Drawing Sheets

Abstract

Apparatus and methods are presented for providing processing system network connectivity, and more particularly, for routing data packets between at least two processing system networks. A first memory for storing at least one address for each of the networks, and a second memory for storing selectively at least one address for particular ones of the networks, are provided. A control circuit for routing a received data packet from a source network to a destination network is also provided. The control circuit utilizes a destination address which was retrieved from one of the first memory and the second memory, in response to a determination as to whether at least one address corresponding to the destination network is stored in the second memory.

Metadata

Assignee

NCR Corporation

Inventor

Benjamin P. Hart

Application Information

Application Number:US 5203201

Filing Date:1995-08-28

Priority Date:1995-08-28

Art Unit:276

Classifications

IPC:

G06F 1300

Field of Search:

395370200.15;200.53;200.54;200.68;200.7285.13-85.16

Patent Drawings (9 sheets)

Description

A portion of the disclosure of this patent document contains material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of this patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all copyright rights whatsoever.

Technical Field of the Invention

The present invention relates generally to processing system network connectivity, and more particularly, to apparatus and methods for routing data packets through a processing system network.

Background

A processing system network, such as a computer network, is a combination of two or more independent nodes capable of communicating with one another over a communications path or link. A network node may be an independent processing system, such as a personal computer, or another processing system network.

Network nodes communicate with one another in order to share resources, such as databases and data files, software applications, hardware peripherals and communication links. Communication links are shared, for example, to enable two or more nodes which are not directly linked together to communicate through one or more intermediate nodes. Resource sharing generally involves the transfer and reception of large amounts of data. The data is typically divided into packets, frames, groups, etc. ("data packets"). Each data packet includes a collection of related data items, as well as any information necessary to route the data packet between network nodes.

Networks traditionally belong in one of two general categories, namely, local area networks ("LANs") and wide area networks ("WANs"). A LAN is a group of communicating nodes which are located relatively close to one another, such as within the same building or building complex. The communication links between LAN nodes are typically characterized by relatively high-speed data packet transfers. A WAN, on the other hand, is a collection of independent and distinct network nodes which work together over relatively long distances. Communication links between WAN nodes are routinely provided by third-party carriers such as by long-distance telephone companies. The InterNet is an example of a worldwide WAN. Communications between WAN nodes are generally characterized by relatively slower data packet transfers as compared with communications between LAN nodes.

Many organizations setup LANs at different strategic locations, such as on each floor of an office building or at each one of several different buildings. It often becomes necessary to share resources among LANs.

There are two broad approaches for establishing LAN-to-LAN communications, namely, private ownership and leasing from commercial communication suppliers. Many organizations setup their own private electric, microwave, light beam and/or fiber optic transmission systems to carry data locally around metropolitan areas and campuses. However, when communication connections extend beyond a particular area, circuits are typically leased from commercial suppliers, including telephone carriers such as AT&T (New York, N.Y.) and MCI (Washington, D.C.); specialized communications companies such as Tymnet (British Telecommunications Public Limited Company, located in London, England) and Telenet (Sprint International Communication Corporation, located in Reston, Va.); and satellite system providers such as GTE (Stamford, Conn.).

Leased services typically fall into one of three general categories, namely, circuit-switched, full-period and packet-switched. Circuit-switched services are those with a dial tone, such as switched-56 digital services or the Integrated Services Digital Network ("ISDN"), for example, wherein a connection is dialed, data is transferred, and the system hangs up upon completion of the transaction. Full-period services, such as leased telephone lines, provide a circuit dedicated to an organization's full time use. Packet-switched systems, such as CompuServe (Columbus, Ohio), Tymnet and SprintNet (Kansas City, Mo.), for example, allow multi-point connections for bursts of short data packets. Packet-switched networks, also called X.25 networks after an older Consultive Committee International Telegraph and Telephone ("CCITT") packet-switching standard, commonly use a newer standard called frame relay.

Network portal devices are used to couple LANs and WANs together (i.e., LAN-to-LAN, LAN-to-WAN and WAN-to-WAN). The conventional approach is to use the portal device as a junction point through which data packets received from a source network are routed to one or more destination networks. The portal device typically includes control circuitry and a memory.

The memory typically includes the routing address for each LAN and each WAN coupled to the portal device, and typically includes the address of one or more of the nodes of each of the LANs and WANs. In the event that a particular network node is itself a LAN or a WAN, the addresses of one or more of its nodes are also often stored within the memory.

When a data packet is forwarded from a LAN node to a WAN node, the data packet is received by the portal device. The control circuitry searches the memory and retrieves the address of the destination WAN node. The control circuitry recognizes from the memory search that the destination node exists on a WAN and will typically wrap the data packet in a "data envelope" along with additional routing and transmission information. This additional information tells the commercial communication suppler how to route the data packet to the destination WAN node.

In an alternative case wherein a data packet is forwarded from one LAN node to another LAN node, the data packet is received by the portal device and the control circuitry is again required to search the memory. The control circuitry upon retrieving the address of the destination LAN node from memory determines whether the data packet requires additional processing, such as being wrapped in the aforementioned data envelope. Upon a determination that no additional processing is required, the control circuitry forwards the data packet to the destination LAN node.

Thus, although the foregoing process is both necessary and effective for processing a data packet routed to the WAN, it is equally unnecessary and ineffective when routing a data packet between LAN nodes. In point of fact the search and retrieval processes performed by the control circuitry when transferring a data packet from one locally connected LAN to another cause significant delays. The delay is compounded by the determination as to whether the data packet requires additional processing. These delays are compounded still further when considering that the portal device may, and often does, receive hundreds, if not thousands, of data packets per second. Many, if not most, of these data packets are queued and routed on a first come, first serve basis. A LAN-to-LAN data packet that is preceded by several data packets requiring special processing typically is required to wait unnecessarily. This wait curtails portal device throughput and the overall functionality of the processing system network.

Accordingly, there exists a need in the art to substantially eliminate delays associated with routing a data packet between two nodes wherein the data packet requires little or no additional processing.

There exists a further need to substantially eliminate delays associated with routing a data packet from a source LAN to a destination LAN.

There exists a still further need to reduce over-all memory access time associated with searching and retrieving addressing data from the memory of a portal device.

Summary of the Invention

Broadly, the present invention is directed to apparatus and methods which provide processing system network connectivity, and more particularly, which enable data packets to be routed through a processing system network. The processing system network includes a plurality of sub-processing system networks (also called "sub-networks") wherein each sub-network is either a LAN or a WAN and includes at least one node. Each node may be either a processing system or another sub-network.

An apparatus in accordance with the principles of the present invention routes ones of a plurality of data packets between at least two of a plurality of sub-networks of a processing system network. Preferably the apparatus includes first and second memories and a control circuit. The first memory is operative to store addressing data for routing ones of the data packets between at least two of the sub-networks. The second memory is operative to store selectively addressing data for routing ones of the data packets between particular ones of the sub-networks.

An important aspect regarding the functionality provided by either or both of the first and second memories is that it may in point of fact be provided by one or more suitably arranged conventional memory storage devices and/or data structure configurations.

The control circuit is operative to receive at least one data packet. The data packet includes destination indicia which directs the control circuit to route the received data packet from a first sub-network to at least a second sub-network. The control circuit retrieves a routing address associated with the destination indicia from either the second memory, in the event that the routing address is selectively stored therein, or the first memory otherwise. The retrieved routing address is utilized by the routing circuit to route the received data packet to the second sub-network.

An important aspect of any circuit, and more generally any apparatus, in accordance with the principles of the present invention is that it may be processing system, firmware or hardware based.

A processing system network in accordance with the principles of the present invention includes a plurality of sub-networks and an apparatus for routing ones of a plurality of data packets between at least two of the sub-networks. Each one of the sub-networks preferably includes at least one node.

The apparatus includes first and second memories and a circuit. The circuit is preferably in operative communication with both memories. The first memory operates to store a plurality of addresses for use in routing ones of the data packets between ones of the sub-networks. The second memory operates to store selectively ones of the addresses for use in routing ones of the data packets between particular ones of the sub-networks.

The circuit is preferably suitably arranged to route a received data packet from a first node of a first sub-network to a second node of a second sub-network. The circuit operates to retrieve an address associated with the second node from either the second memory, in the event the associated address is selectively stored therein, or the first memory otherwise. The retrieved address is utilized by the apparatus to route the received data packet to the second node.

A method in accordance with the principles of the present invention concerns routing ones of a plurality of data packets between at least two of a plurality of sub-networks of a processing system network. At least one address for each one of the sub-networks is stored in a first memory. At least one address for particular ones of the sub-networks is stored selectively in a second memory. A data packet from a first sub-network is received. The data packet includes destination indicia which indicates that the received data packet is to be routed to at least a second sub-network. A determination is made as to whether at least one address associated with the second sub-network is stored in the second memory. The received data packet is routed to the second sub-network utilizing, in response to the determination, the associated address stored in one of the second memory or the first memory.

One embodiment for using and/or distributing the present invention is as software. The software includes a plurality of processing unit instructions which are stored to a conventional storage medium. The instructions are readable and executable by one or more processing units. The instructions, upon execution, operate to control the one or more processing units to route data packets through a processing system network. Preferred storage media include without limitation, magnetic, optical, and semi-conductor, as well as suitably arranged combinations thereof.

Brief Description of the Drawings

For a more complete understanding of the present invention, and the advantages thereof, reference is now made to the following Detailed Description of the Invention taken in conjunction with the accompanying drawings in which like numbers designate like parts, and in which:

FIG. 1 illustrates a block diagram of an exemplary processing system network;

FIG. 2 illustrates a block diagram of an exemplary LAN which may suitably be arranged for use in conjunction with the processing system network of FIG. 1.

FIG. 3 illustrates an isometric view of an exemplary processing system capable of functioning as a node within the processing system network of FIG. 1 and the LAN of FIG. 2;

FIG. 4 illustrates a block diagram of a microprocessing system which may be utilized in conjunction with the processing system of FIG. 3;

FIG. 5 illustrates a block diagram of an exemplary circuit operable to facilitate communications between one or more processing system nodes and/or processing system networks in accordance with the principles of the present invention;

FIG. 6 illustrates a block diagram of an exemplary conventional timing circuit which may be utilized in conjunction with an exemplary control circuit shown in FIG. 5;

FIG. 7 illustrates a more detailed block diagram of one embodiment of the exemplary processing system network of FIG. 1;

FIG. 8 illustrates a flow diagram for controlling the routing of a data packet through a processing system network in accordance with the principles of the present invention;

FIG. 9a illustrates an exemplary flow diagram for sequentially accessing a first memory and a second memory in accordance with one embodiment of the principles of the present invention;

FIG. 9b illustrates an exemplary flow diagram for accessing a first memory and a second memory substantially in parallel in accordance with one embodiment of the principles of the present invention;

FIG. 10a illustrates an exemplary flow diagram for monitoring at least one address associated with at least one sub-network and/or network node; and

FIG. 10b illustrates another exemplary flow diagram for monitoring at least one address associated with at least one sub-network and/or network node.

Detailed Description of the Invention

FIG. 1 illustrates a block diagram of an exemplary processing system network in which the principles of the present invention are particularly advantageous. A Multiple Communications Adapter Module ("MCAM") 100, a network to network portal device, is shown suitably coupled via communications bus 101 with a Front End Processor ("FEP") 102. In a preferred exemplary embodiment, MCAM 100 is an Intel 486-based micro-channel subsystem, model no. 2705, available from AT&T Global Information Solutions ("AT&T GIS"), located in St. Paul, Minn. and Dayton, Ohio; communications bus 101 is a SCSI II communications cable available from AT&T GIS, located in St. Paul, Minn. and Dayton, Ohio; and FEP 102 is a Comten 56XX front end processor available from AT&T GIS, located in Dayton, Ohio. The preferred MCAM 100 embodiment is more fully disclosed in the Comten HA-MCAM and MCAM Brochure, Document No. SP-4355, which is incorporated herein by reference. This documentation is available upon request from AT&T GIS by contacting AT&T GIS Information Products Publishing which is located in Dayton, Ohio, U.S.A.

The Comten 56XX FEP includes up to eight SCSI ports, and is operative to connect up to seven MCAMs 100 together on each of its SCSI ports, for a total of 56 possible MCAMS 100. The Comten 56XX FEP is more fully disclosed in the "Comten 5675-B Communications Processor," NCR Document No. SP-4359-1093, which is incorporated herein by reference. This documentation is also available upon request from AT&T GIS by contacting AT&T GIS Information Products Publishing which is located in Dayton, Ohio, U.S.A.

MCAM 100 is operative to provide processing system network connectivity enabling the sharing of resources among a plurality of high-speed LANs 103a to 103n and one or more slower WANs 104 via FEP 102. More particularly, MCAM 100 is operative to route a received data packet from a first node associated with a first processing system network to a second node associated with a second processing system network. Exemplary network interfaces to which connectivity is provided include without limitation ISDN, Frame Relay, Token Ring, Ethernet, TCP/IP Channel, FDDI, and the like.

Resource sharing among network nodes is typically governed by two sets of rules, namely, standards and protocols. Standards describe minimum performance levels for various aspects of the network, as well as performance levels of individual network nodes. Protocols define the interaction between the communicating nodes, providing file transfer, remote log-in, electronic mail, and other services, including without limitation distributed processing and shared use of peripheral devices. The aforementioned non-exclusive list of interfaces are each based upon particular protocols and standards. For example, the InterNet Protocol ("IP") governs a worldwide network of networks. IP, among its other facilities, enables a data packet from a source node to traverse multiple networks on its way to one or more destination network nodes.

Each of the illustrated LANs 103a to 103n includes a plurality of nodes 105a to 105n, as does WAN 104 which also includes nodes 105a to 105n. Each one of the nodes 105a to 105n may in point of fact be a single processing system, or alternatively, may be a separate processing system network. Further, although WAN 104 and LANs 103a to 103n have each been shown to include a plurality of nodes, each may include as few as a single node.

Conventional data transmission media, such as copper wire or fiber optic cable, are typically used to couple LANs 103a to 103n to MCAM 100. These cables may extend over relatively long distances, and may accumulate noise from the outside environment as well as from one another. As the pulses of electricity or light representing the data packets traverse the exemplary copper wires or fiber optic cables, they may lose sharpness and/or experience signal degradation. Induced noise and signal degradation are two primary factors limiting the effective length of conventional high-speed LAN cable. Long-distance LAN-to-LAN connections accordingly move data more slowly than local LAN-to-LAN connections and often require intermediate signal processing and quality checks between LANs.

The principles of the present invention are well suited, from both a practical as well as an illustrative standpoint, for providing network connectivity between LANs and WANs. These same principles are also in point of fact particularly advantageous in providing network connectivity in many other communication applications wherein one or more transferred data packets may or may not require special processing. Preferably, the one or more data packets are passed from at least one node of at least one sub-processing system network to at least one node of at least a second sub-processing system network. Other examples include, without limitation, connectivity between sub-networks using private and public communication links, as well as, sub-networks using wired (e.g., copper wire, fiber optic cable, etc.) and wireless (e.g., radio wave, microwave, etc.) communications, for example.

FIG. 2 illustrates a block diagram of an exemplary LAN, such as any of LANs 103a to 103n, which may suitably be arranged for use in conjunction with the processing system network of FIG. 1. The illustrated LAN includes a plurality of processing system nodes 105a to 105n which are coupled via cables 201a to 201n (e.g., a conventional voice-data line) to a network portal device 202. Device 202 is coupled via cable 203 to MCAM 100. Device 202 is operative to transfer one or more data packets between two or more nodes within LAN 103, or between one or more nodes of LAN 103 and a node of another network (not shown) via MCAM 100. Data packet transference using MCAM 100 typically requires utilization of one or more common protocols.

Network portal devices (e.g., bridges, routers, etc.) are typically used to link LANs and WANs and to exercise discrimination over the traffic passing between them. Bridges may be used, for example, to link the fast cable of a LAN to slower links, such as LANs and WANs using leased telephone lines. The primary purposes of a bridge are to extend a processing system network and to isolate network traffic, transferring data packets between various types of media and forwarding only traffic which is addressed to devices of another cable system. Conventionally, local bridges link fast cable segments on a local network and remote bridges link fast local cables to slower long-distance cables to connect physically separated networks.

Routers are operative to read more complex network addressing information from within a transmitted data packet. Routers often add additional information in order to route the data packet through the network. For example, a router might wrap an Ethernet data packet in an "envelope" of data containing routing and transmission information for transmission through an X.25 packet-switched network. When the data envelope passes through the X.25 network, a receiving router strips off the X.25 data, readdresses the Ethernet data packet, and sequences it on its attached LAN segment. Routers may choose from redundant paths between networked segments or may link networked segments using very different data packaging and media accessing schemes.

FIG. 3 illustrates an isometric view of an exemplary processing system 105 capable of functioning as a network node. Processing system 105 is a suitably equipped conventional personal computer, such as a model no. System 3333, from AT&T GIS, located in Dayton, Ohio, for example.

Processing system 105 includes a monitor 301, a housing 302 and a keyboard 303. Monitor 301 and keyboard 303 may suitably be replaced by other conventional output and input devices, respectively. Housing 302 includes both a floppy disk drive 304 and a hard disk drive 305. Floppy disk drive 304 is suitably operative to receive, read and write to external disks and hard disk drive 305 is suitably operative for fast access storage and retrieval. Floppy disk drive 304 may be replaced by conventional with other conventional structures operative to receive and transmit data and/or instructions, including without limitation, tape and compact disc drives, telephony systems and devices (including conventional telephone, videophone, facsimile, and paging technologies), and serial and parallel ports.

Housing 302 is illustrated having a cut-away portion which includes a battery 306, a clock 307, a processing unit 308 and a memory storage device 309. Processing unit 308 is suitably coupled with memory storage device 309. Although processing system 105 is illustrated having a single processing unit, a single hard disk drive and a single memory storage device, processing system 105 may be equipped with a plurality of processing units and/or suitably arranged memory storage devices.

It should be noted that any conventional processing system having at least one processing unit and which is suitable to function as a network node may replace, or be utilized in conjunction with, processing system 105, including without limitation, videophones, telephones, televisions, sophisticated calculators and, hand-held, laptop/notebook, mini, mainframe and super computers, including RISC and parallel processing architectures, as well as within processing system network combinations of the foregoing. Conventional processing system architecture is more fully discussed in Computer Organization and Architecture, by William Stallings, MacMillan Publishing Co. (3rd ed. 1993), which is incorporated herein by reference.

FIG. 4 illustrates a block diagram of one exemplary microprocessing system which may suitably be utilized in conjunction with processing system 105 of FIG. 3. The microprocessing system includes a single processing unit 308 coupled via data bus 401 with a single memory storage device 309. Memory storage device 309 is suitably operative to store data and/or one or more processing system instructions which processing unit 308 is operative to retrieve and execute. Memory storage device 309 may be any suitable conventional memory storage device. Processing unit 308 includes a control unit 402, an arithmetic logic unit ("ALU") 403, and a local memory storage device 404 (e.g., stackable cache, a plurality of registers, etc.). Control unit 402 is operative to fetch processing system instructions from memory storage device 309. ALU 403 is operative to perform a plurality of operations, including without limitation addition and Boolean AND, needed to carry out those instructions. Local memory storage device 404 is operative to provide local high speed storage used for storing temporary results and control information.

FIG. 5 illustrates a detailed block diagram of MCAM 100, as previously shown in FIGS. 1 and 2, and in which the principles of the present invention are particularly advantageous. MCAM 100 is operative to facilitate communications between two or more processing system networks and their respective nodes. MCAM 100 includes a control circuit 501, a plurality of network interfaces 502a to 502n, a first memory 503 and a second memory 504.

Control circuit 501 is shown suitably coupled via buses 505a to 505n to each one of the network interfaces 502a to 502n, and via bus 506 to first memory 503 and second memory 504. Each of the network interfaces 502a to 502n is operative to link MCAM 100 with a different sub-processing system network, thus providing a shared boundary defining functional, signaling and physical interconnection capabilities. For example, one or more of the network interfaces 502a to 502n might be an Ethernet or a Token Ring LAN Micro Channel adapter. Alternatively, one or more of the network interfaces 502a to 502n might be a conventional WAN interface, such as a frame relay TCP/IP interface, for example.

Data packets received by MCAM 100 are suitably processed to determine their respective destinations. Preferably, each received data packet includes destination indica, among other data, directing MCAM 100, and more particularly control circuit 501, to destination route each received data packet. In alternate embodiments, other indica may also be included within one or more data packets. This other indica may, for example, direct control circuit 501 to perform a particular task or it may indicate that the data packet under consideration has specific processing requirements. These particular aspects of the invention will be more fully discussed momentarily.

First memory 503 preferably functions as a main memory and is operative to store addressing data for routing data packets from a source network to one or more destination networks via the network interfaces 502a to 502n. Second memory 504 preferably functions as a fast "look up" memory and is operative to store selectively addressing data for routing data packets between particular source and destination networks, again, via the network interfaces 502a to 502n. More particularly, second memory 504 is preferably a high-speed buffer storage that is continuously updated to contain recently accessed contents of first/main memory 503 (e.g., addressing data). An important aspect of second memory 504, which will be discussed in greater detail with reference to FIG. 8, is the reduction of over-all memory access time.

Although memories 503 and 504 are illustrated as separate memory storage devices, the functionality supported by each may suitably be provided utilizing one or more data structures within one or more suitable memory storage devices. Further, although memories 503 and 504 are shown to juxtapose control circuit 501, either one, or both, may in point of fact be located within circuit 501, or alternatively external and juxtaposed to MCAM 100.

Control circuit 501 is operative to determine whether addressing data corresponding to the destination indica of a received data packet has been stored within second memory 504. If the destination addressing data is stored in second memory 504 then it is retrieved therefrom, otherwise the destination addressing data is retrieved from first memory 503. Control circuit 501 utilizes the retrieved addressing data to destination route a particular received data packet.

In the event that the addressing data was retrieved from first memory 503 and not second memory 504, control circuit 501, as will also be discussed in greater detail with reference to FIG. 8, may update second memory 504 so it contains the retrieved addressing data from first memory 503.

In one preferred exemplary embodiment, second memory 504 is accessed first. The determination is made as to whether addressing data corresponding to the data packet's destination indica has been stored in second memory 504. If not, then first memory 503 is accessed. In other words, control circuit 501 is operative to sequentially access second memory 504 and then optionally first memory 503.

In another preferred exemplary embodiment, control circuit 501 is operative to access first memory 503 and second memory 504 substantially in parallel. Preferably, both memories 503 and 504 are accessed, a determination is made as to whether addressing data corresponding to the data packet's destination indica has been stored in second memory 504, and if it has been stored therein, control circuit 501 aborts further access to first memory 503. An important aspect of accessing both memories in tandem, is that any latency associated with the sequential accessing embodiment discussed above is substantially eliminated.

Control circuit 501 is further operative to monitor one or more of the network interfaces 502a to 502n to determine whether addressing data associated with any one the interfaces has changed. In the event that one or more network addresses have changed, the addressing data associated with those interfaces which are stored in first memory 503 and/or second memory 504 will be updated to reflect the changed address. In an alternate embodiment, addressing data associated with a changed interface, will be deleted from second memory 504 and may be re-stored at a later time, again as will be discussed with reference to FIG. 8, to reflect the addressing data from first memory 503.

Alternate preferred exemplary embodiments providing network connectivity include without limitation programmable logic devices, such as PALs (programmable array logic) and PLAs (programmable logic arrays), DSPs (digital signal processors), FPGAs (field programmable gate arrays), ASICs (application specific integrated circuits), and the like.

FIG. 6 illustrates a block diagram of an exemplary conventional timing circuit 601 which may be utilized in conjunction with control circuit 501 of FIG. 5. Although timing circuit 601 is shown coupled with control circuit 501 within MCAM 100, in point of fact, timing circuit 601 may also be located within control circuit 501, or may be external to and juxtapose MCAM 100.

Timing circuit 601 is operative to generate one or more signals indicating passage of a time period (e.g., second, millisecond, etc.) during which addressing data associated with one or more interfaces 502a to 502n has remained stored in memory. Control circuit 501 is operative to compare one or more of the generated signals with a predetermined value (e.g., a threshold value, a conventional time-out value, etc.) to determine whether the addressing data has remained stored for too long. In response to a determination that one or more particular signals compare unfavorably to the value, such as to exceed or equal a threshold value for example, control circuit 501 is further operative to update or delete the addressing data corresponding to the particular interfaces 502a to 502n associated with those particular signals from either one, or both, first and second memories 503 and 504, respectively.

FIG. 7 illustrates a more detailed block diagram of one embodiment of the exemplary processing system network of FIG. 1 wherein MCAM 100 is operative to provide network connectivity between a WAN 104 and a plurality of LANs 103a to 103c. Exemplary WAN 104 is a X.25 TCP/IP network. Exemplary LANs 103a and 103c are each an Ethernet TCP/IP sub-network or non-sub-netted network of TCP/IP workstations, wherein the sub-network is comprised of a single Ethernet media or Ethernet network fabric (i.e., coax-cables or twisted copper pair wire and Ethernet hubs). Exemplary LAN 103b is a Token Ring TCP/IP sub-network or non-sub-netted network of TCP/IP workstations on a Token Ring or set of bridged Token Rings.

MCAM 100 includes a TCP/IP interface 502a, two Ethernet interfaces 502b and 502d, and a Token Ring interface 502b. Exemplary TCP/IP interface 502a provides connectivity between MCAM 100 and FEP 102. Exemplary Ethernet interfaces 502b and 502d may be, for example, Cogent Ethernet Micro-Channel Adapters, model no. F110, available from AT&T GIS, located in Dayton, Ohio. Exemplary Token Ring interface 502c may be a Micro-Channel Token Ring Adapter, model no. F111, available from AT&T GIS, located in Dayton, Ohio.

First memory 503 includes a Spider Data link Interface Module ("SDIM") 701, a TCP stack 702 and an IP stack 703. SDIM 701 is operative to provide a generic lower streams interface for all LAN interfaces (also known as "drivers") 502b-502n to the main TCP/IP protocol stack. SDIM is also used to utilize IP and ARP streams to these drivers. An ARP stream is a special stream to the TCP/IP Stack that is used to pass Address Resolution Protocol frames to the IP layer in the TCP/IP stack. TCP stack 702 is operative to provide TCP protocol support to all devices contained in connected networks (TCP provides end point functions such as FTP, Telnet, NFS, etc.). IP stack 703 includes an address table 704, and is operative to provide routing between LAN and WAN nodes 105. Address table 704 is operative to provide network configuration information that may, for example, have been statically defined, determined in real time via network frame receipt, and the like.

Similarly, second memory 504 includes an address table 705 which like address table 704 is operative to provide selective access to the above-identified information stored in address table 704. More particularly, the entries in address table 705, unlike address table 704, are limited to selectively stored addressing data for routing data packets between particular ones of source and destination nodes 105 (e.g. N.sub.1 -N.sub.6). Address table 705 is preferably a high-speed storage structure which is continuously updated to contain selected recently accessed addressing data of first memory 503.

Recall that FEP 102 includes a plurality of ports, and is operative to connect a plurality of MCAMs 100 together. In accordance with the embodiment of FIG. 7, FEP 102 provides for direct connections to X.25 TCP/IP network interface 104 (although only one is illustrated). Accordingly, there is a TCP/IP layer within FEP 102 that is operative to maintain and route to the TCP/IP interface 502a of the one or more MCAM 100 subsystems and to the X.25 TCP/IP WAN 104. FEP 102 also includes a main TCP/IP stack (not shown) which is operative to maintain, and is used to control, all TCP/IP interfaces within FEP 102. The TCP/IP stacks within each of the one or more MCAM 100 subsystems are each a sub-stack of the FEP TCP/IP stack, and are operative to maintain, and are used to control, all interfaces within their respective MCAM 100.

FIG. 8 illustrates a flow diagram for routing a data packet through a processing system network in accordance with the principles of the present invention. The processing system network preferably includes a plurality of sub-networks, such as LANs 103 and WAN 104 of FIGS. 1, 2 and 7. Each of the sub-networks includes at least one network node 105.

More particularly, one or more data packets are routed through a network portal device, such as MCAM 100 for example. Recall that one preferred exemplary embodiment for using and/or distributing the present invention is as software. The software includes a plurality of processing unit instructions which are stored to a conventional storage medium. A preferred exemplary software source code implementation is attached hereto as an Appendix.

At least one address is stored for each one of the sub-networks in a first memory 503 (process step 801). The memory includes at least one routing address for each LAN and each WAN coupled to the portal device, and typically includes the address of one or more of the nodes of each of the respective LANs and WANs. In the event that a particular network node is itself a LAN or a WAN, the addresses of one or more of its nodes may also suitably be stored therein.

A first data packet is received by the portal device from a first sub-network (input/output step 802). The received data packet preferably includes destination indicia among other information/data. The destination indicia identifies the one or more nodes of one or more sub-networks to which the received data packet is to be routed. In alternate preferred embodiments, the received data packet also includes source indicia. The source indicia identifies the one or more nodes of the first sub-network from which the data packet was transmitted.

The portal device determines whether an associated address for each one of the one or more destination sub-networks, and/or the one or more nodes of the one or more destination sub-networks, is stored within a second memory 504 (decision step 803). Second memory 504 preferably selectively stores at least one address for particular ones of the sub-networks, and/or their nodes. Routing one or more data packets to these particular destination sub-networks and/or network nodes requires little or no additional/special processing, as previously discussed.

In alternate exemplary embodiments, assuming there are at least two destination nodes of one or more destination sub-networks, the two or more nodes may suitably be processed sequentially, in parallel, selectively, or the like. The techniques for performing such processing, and in particular associated memory accesses, are known.

In the event that one or more associated addresses are stored in second memory 504 (YES branch of decision step 803), then at least one of those addresses are retrieved therefrom (process step 804). Otherwise (NO branch of decision step 803) one or more addresses are retrieved from first memory 503 (process step 805). The received data packet is routed to each of the one or more destination sub-networks, and/or network nodes, using the one or more retrieved addresses (process step 806).

In alternate exemplary embodiments, assuming there are at least two destination nodes of one or more destination sub-networks, the two or more nodes may suitably be routed sequentially, in parallel, selectively, or the like. In other words, all of the addresses of the two or more nodes may be completely or partially retrieved and then the data packet may suitably be routed sequentially, in parallel, selectively or the like to the two or more destination nodes. In another alternate embodiment, the addresses of the two or more nodes may be sequentially or selectively retrieved and then the data packet may suitably be routed sequentially, in parallel, selectively or the like to the two or more destination nodes.

In the event that a particular destination address is not stored in second memory 504 (NO branch of decision step 803), a determination is made as to whether a data packet directed to the particular destination address requires additional/special processing (decision step 807), as previously discussed. If the particular destination address does not require additional/special processing (NO branch of decision step 807), then it is suitably stored in second memory 504 (process step 808).

Although decision and process steps 807 and 808, respectively, are illustrated as being performed substantially in parallel with process step 806, in alternate exemplary embodiments, steps 807 and 808 may suitably be performed before, after or in combination with step 806.

FIG. 9a illustrates an exemplary flow diagram for sequentially accessing first and second memories 503 and 504, respectively. In accordance with determining whether an address has been stored in second memory 504 for one or more destination sub-networks, and/or their respective nodes, second memory 504 is accessed (process step 901). In the event that the address has not been stored in second memory 504 (NO branch of decision step 803), first memory 503 is accessed (process step 902).

FIG. 9b illustrates an exemplary flow diagram for accessing substantially in parallel first and second memories 503 and 504, respectively. In accordance with determining whether an address has been stored in second memory 504 for one or more destination sub-networks, and/or their respective nodes, first and second memories 503 and 504, respectively, are accessed substantially in parallel (process step 903). In the event that the address has been stored in second memory 504 (YES branch of decision step 803), then the first memory access is aborted (process step 904). As previously discussed, an important aspect of accessing both memories in tandem is that any latency associated with the sequential accessing embodiment of FIG. 9a is substantially eliminated.

FIG. 10a illustrates an exemplary flow diagram for monitoring at least one address associated with at least one sub-network and/or network node. Assuming that each one of at least a first and a second sub-network are addressable, and/or their respective nodes, at least one of a first address associated with the first sub-network or a second address associated with a second sub-network is monitored (process step 1001). A periodic determination (e.g., second, millisecond, microsecond, etc.) is suitably made as to whether one or more of the one or more monitored addresses has changed (decision step 1002).

In the event that one or more of the one or more monitored addresses has changed (YES branch of decision step 1002), an associated address in first memory 503 is updated to reflect the changed address (process step 1003). Similarly, the associated address in second memory 504, assuming such an address has suitably been stored therein, is also updated to reflect the changed address (process step 1004). In an alternate embodiment, the associated address in second memory 504 is deleted therefrom.

FIG. 10b illustrates another exemplary flow diagram for monitoring at least one address associated with at least one sub-network and/or network node. At least one signal is generated indicative of a time period (e.g., minute, second, millisecond, etc.) during which at least one address associated with at least a first sub-network has been stored in second memory 504 (process step 1005). The signal is compared with a predetermined value (e.g., time limit, threshold, etc.) to determine whether the associated address is valid/acceptable (process step 1006). In the event that the signal compares unfavorably with the predetermined value (NO branch of decision step 1006), then the associated address is deleted from second memory 504 (process step 1007). In alternate preferred embodiments, when the signal compares unfavorably with the predetermined value (NO branch of decision step 1006), the associated address in second memory 504 is updated.

It should be appreciated that the present invention can substantially reduce the frequency of accesses to the IP stack for routing data packets among the nodes that are locally connected to a MCAM.

More specifically, in FIG. 7, when any one of the nodes N-N.sub.6 (locally connected to MCAM 100) communicates with node N.sub.7 or N.sub.8 (connected to WAN 104), or with a node connected to another MCAM (not shown), IP stack 703 is accesed for routing the data packets between the two nodes.

However, when data packets are routed between any of the nodes N.sub.1 -N.sub.6, the acces to IP stack 703 can be avoided, if the addresses of these two nodes can be found in address table 705.

Although the present invention and its advantages have been described in detail, it should be understood that various changes, substitutions and alterations can be made herein without departing from the spirit and scope of the invention. ##SPC1##

Claims

Certificate of Correction present

The claims shown below may not include correction changes. Use the corrected PDF for authoritative text.

I claim:

1. An apparatus for routing data packets between sub-networks of a processing system network, said apparatus comprising: a first means for storing addressing data for routing said data packets between said sub-networks; a second means, associated with said first means, for storing recently accessed addressing data for routing ones of said data packets between ones of said sub-networks; a control circuit, associated with said first means and said second means, that routes said data packets between sub-networks in response to said recently accessed addressing data and destination indicia associated with said data packets; and a timing circuit, associated with said control circuit, that indicates time periods during which said recently accessed addressing data are stored in said second means, wherein said control circuit deletes at least one of said recently accessed addressing data from said second means whenever a time period associated with said at least one recently accessed addressing data exceeds a maximum value said deletion thereby eliminating least recently accessed addressing data from said second means.

2. The apparatus as set forth in claim 1 wherein first sub-network and said second sub-network is one of a local area network and a wide area said control circuit is operative to determine whether both a first sub-network and a second sub-network are local area networks.

3. The apparatus as set forth in claim 2 wherein said control circuit, in the event that both said first sub-network and said second sub-network are local area networks, is further operative to store a routing address retrieved from said first means in said second means.

4. The apparatus as set forth in claim 1 wherein said control circuit, in the event that a routing address is not stored in said second means, is operative to determine whether a received data packet requires special processing.

5. The apparatus as set forth in claim 4 wherein said control circuit, in the event that said received data packet does not require special processing, is further operative to store said routing address in said second means.

6. The apparatus as set forth in claim 1 wherein said control circuit is operative to access initially said second means and, in the event that said routing address data is not stored in said second means, to access said first means.

7. The apparatus as set forth in claim 1 wherein said control circuit is operative to access initially substantially in parallel said first means and said second means.

8. The apparatus as set forth in claim 7 wherein said control circuit, in the event that a routing address is stored in said second means, is further operative to abort accessing said first means.

9. The apparatus as set forth in claim 1 further comprising a plurality of interfaces wherein each one of said plurality of interfaces has an address associated therewith, said control circuit is further operative to use said addresses to communicate with said sub-networks.

10. The apparatus as set forth in claim 9 wherein said control circuit is further operative to monitor at least one of said interfaces to determine whether an address of said at least one of said interfaces changed.

11. The apparatus as set forth in claim 10 wherein said control circuit, in the event that said address of said at least one of said interfaces changed, is further operative to at least one of: delete said changed address from said second means, and update said second means to reflect said changed address.

12. The apparatus as set forth in claim 10 wherein said control circuit, in the event that said address of said at least one of said interfaces changed, is further operative to update said first means to reflect said changed address.

13. The apparatus as set forth in claim 1 wherein said timing circuit is further operative to compare said time periods with a predetermined value.

14. The apparatus as set forth in claim 13 wherein said control circuit, in response to said comparison, is further operative to at least one of delete certain address data from said second means and update said second means in response certain address data stored in said first means.

15. A method for routing data packets between sub-networks of a processing system network, said method comprising the steps of: storing an address for each of said sub-networks in a first memory; storing recently accessed addresses for particular ones of said sub-networks in a second memory; routing said data packets between sub-networks in response to said recently accessed addresses and destination indicia associated with said data packets; using a timing circuit to indicate time periods during which said recently accessed addresses are stored in said second memory; and deleting at least one recently accessed address from said second means whenever a time period associated with said at least one recently accessed address exceed a maximum value, said deletion thereby eliminating least recently accessed addresses from said second memory.

16. The method as set forth in claim 15 further including, upon a determination that a particular address is not stored in said second memory, the step of storing said particular address from said first memory in said second memory.

17. The method as set forth in claim 15 further including the steps of: accessing said second memory; and accessing said first memory in the event that a particular address is not stored in said second memory.

18. The method as set forth in claim 15 wherein said routing step is preceded by the step of accessing substantially in parallel said first memory and said second memory.

19. The method as set forth in claim 18 further including the step of aborting said first memory access in the event that a particular address is stored in said second memory.

20. The method as set forth in claim 15 further including the step of monitoring at least one of said sub-networks to determine whether any of said addresses has changed.

21. The method as set forth in claim 20 further including, in the event that at least one of said addresses has changed, one of the steps of: deleting said changed address from said second memory; and updating said second memory to reflect said changed address.

22. The method as set forth in claim 20 further including, in the event that, at least one of said addresses has changed, the step of updating said first memory to reflect said changed address.

23. The method as set forth in claim 15 further comprising the steps of: comparing said time periods with a predetermined value; and deleting, in response to said comparison, at least one address from said second memory.

24. A processing system network comprising: a plurality of sub-networks wherein each said sub-networks includes at least one node; and an apparatus for routing data packets between said plurality of sub-networks, said apparatus comprising: a first means for storing addresses for routing data packets between ones of said plurality of sub-networks; a second means, associated with said first means, for storing ones of said recently accessed addresses for use in routing ones of said data packets between particular ones of said plurality of sub-networks; a control circuit, associated with said first means and said second means, arranged to route said data packets between said plurality of sub-networks in response to said recently accessed addresses and destination indicia associated with said data packets; and a timing circuit, associated with said control circuit, that indicates time periods during which said recently accessed addresses are stored in said second means, wherein said control circuit deletes at least one recently accessed address from said second means whenever a time period associated with said least one recently accessed address exceeds a maximum value, said deletion thereby eliminating least recently accessed addresses from said second means.

25. The network as set forth in claim 24 wherein said control circuit is operative to determine whether a particular received data packet requires special processing.

26. The network as set forth in claim 25 wherein said control circuit, in the event said particular received data packet does not require special processing, is further operative to store a retrieved address from said first means in said second means.

27. The network as set forth in claim 24 wherein said control circuit is operative to access initially said second means and then said first means in the event that a particular address is not stored therein.

28. The network as set forth in claim 24 wherein said control circuit is operative to access substantially in parallel said first means and said second means.

29. The network as set forth in claim 28 wherein said control circuit, in the event that a particular address is selectively stored in said second means, is further operative to abort accessing said first means.

30. The network as set forth in claim 24 wherein said apparatus includes a plurality of interfaces, wherein ones of said plurality of interfaces have an address associated therewith, and wherein said control circuit is further operative to use ones of said addresses to communicate with ones of said plurality of sub-networks.

31. The network as set forth in claim 30 wherein said control circuit is further operative to monitor at least one of said interfaces to determine whether at least one of said addresses has changed.

32. The network as set forth in claim 31 wherein said control circuit, in response to at least one of said monitored addresses being changed, is further operative to update at least one of said first means and said second means to reflect said changed address.

33. The network as set forth in claim 24 wherein said control circuit is further operative to: compare said time periods with a predetermined value; and delete, in response to said comparison, at least one address from said second means.

Patent Citations (11)

Patent	Date	Inventor
US5251205	1993-10-01	Callon et al.
US5325508	1994-06-01	Parks et al.
US5377329	1994-12-01	Seitz
US5394402	1995-02-01	Ross
US5394526	1995-02-01	Crouse et al.
US5426637	1995-06-01	Derby et al.
US5432907	1995-07-01	Picazo, Jr. et al.
US5434863	1995-07-01	Onishi et al.
US5463735	1995-10-01	Pascucci et al.
US5526489	1996-06-01	Nilakantan et al.
US5535338	1996-07-01	Krause et al.

Non-Patent Literature (6)

C. Hedrick, "Routing Information Protocol," Network Working Group, RFC 1058 Jun. 1988 pp. 1-33.
Rekhter et al, "Application of Border Gateway Protocol in the Internet", T.J. Watson Research Center, IBM Corp. RFC 1772 Mar. 1995.
Sidney Feit, "TCP/IP Architecture, Protocols and Implementation," McGraw-Hill Series on Computers, 1993, pp. 333-384.
David C. Plumm, "An Ethernet Address Revolution Protocol", Network Working Group, RFC 826, Nov. 1982 pp. 1-10.
Publication "Comten HA-MCAM and MCAM" AT&T Global Information Solutions Company, SP-4355 May 1995.
Publication "Comten 5675-B Communications Processor", NCR An AT&T Company, SP-4359 1093.

Abstract

Description