_
`
`Umted States Patent 1191
`Derby et al.
`p
`
`US005426637A
`
`[11] Patent Number:
`[45] Date of Patent:
`
`5,426,637
`Jun. 20, 1995
`
`[54] METHODS AND APPARATUS FOR
`INTERCONNECI'ING LOCAL AREA
`NETWORKS WITH WIDE AREA BACKBONE
`NETWORKS
`
`_
`[75] Inventors: Jwei?rigl?lkl?gzz;ifgzfiggkagca
`_
`Harold D‘ pykeman’ R_ueschl_lkon’
`both of Switzerland; Llang L1,
`Chapel Hill; 1111111611 J. Sandick,
`Durham; Ken V. Vu, Cary, all of
`N.C.
`[73] Assignee: International Business Machines
`_
`Corporatlon, Armonk, NY.
`
`[21] App]. No.: 992,857
`_
`Dec- 14, 1992
`[22] Flledi
`[51] Int. Cl? ........................................... .. H04L 12/66
`[52] US. Cl. ...................................... .. 370/8513
`[58] Field Of Search ............... .. 370/8513, 85.14, 85.1,
`370/94.l, 94.2, 60, 60.1; 364/200, 2403, 94031,
`94052; 395/325
`
`[56]
`
`References Cited
`U_S_ PATENT DOCUMENTS
`
`"f """""""" " 370/8513
`5’018’137 5/1991 Backes ct
`5,086,426 2/1992 Tsukakosh1 et a1.
`.. 370/85.13
`5,179,555 1/1993 Videlock et al. .......... .. 370/85.13
`5,214,646 5/1993 Yacoby .................. .. 370/85.13
`5,251,205 10/1993 Callon e161. ................ .. 370/60
`5,251,213 10/1993 Videlock et a1. .............. .. 370/8513
`
`5,309,437 5/1994 Perlrnan ......................... .. 370/85.13
`OTHER PUBLICATIONS
`
`R. Letson, “LAN-WAN-Smater and Faster Links,”
`Systems Integration, pp. 32-36, Dec. 1990.
`M. Grimshaw, “LAN Interconnection Technology,”
`Telecommunications, pp. 37-46, Jun. 1991.
`R. L. Shanna, “Interconnecting LANs” IEEE Spec
`t
`.
`. 2-44, A .1 1,
`mm PP 3
`“g 99
`Primary Examiner-Douglas W. Olms
`Assistant Examiner-Ajit Patel
`Attorney, Agent, or Firm-Gerald R. Woods; Robert O.
`Nimtz
`
`ABSTRACT
`57
`_
`_
`_
`[
`1
`A system for interconnecting w1dely separated local
`area networks (LANs) by means of a wide area network
`(WAN) utilizes netWQrk level facilities to establish a
`Connection thwugh the Wide area “em/0Y1‘ and to cre
`ate connection table em?es at the WAN access Pomt
`which allow subsequent data frames to be transmitted
`through the wide area network without such network
`level operations. More particularly, the various LANs
`are combined into search groups, represented by ad
`dress pre?xes, to which LAN-initiated connection re
`quests can be broadcast and which can respond so as to
`establish the data path connections. This system has the
`_
`? .
`.
`.
`f
`.
`conneqlon exlblhty O a Pm‘ a“ .router an?’ at the
`Same “me, the low Overhead of a P110r a" bridge
`
`14 Claims, 6 Drawing Sheets
`
`LOCAL
`ACCESS
`AGENT
`
`CONNECTON
`TABLE?
`
`73
`
`SEND
`SEARCH
`REQUEST
`\74
`
`RETRIEVE
`TABLE
`ENTRY
`
`,
`;
`78 -
`1
`ADJUST
`FRAME
`.
`(IF REQ'D)
`1
`19' :
`
`SEND
`:
`DATAFRAME '
`\
`.
`i
`so .
`'.
`':
`
`: RESPONSE 1
`WWI-"Q5;
`
`RECEIVE
`SEARCH
`neouesr
`
`‘81
`
`SEARCH
`ADDRESS
`CACHE
`
`serum:
`LANB
`ADDRESS
`
`Petitioners' Ex. 1014 - Page 1
`
`

`
`US. Patent
`
`June 20, 1995
`
`Sheet 1 0f 6
`
`5,426,637
`
`FIG. 1
`
`LOCAL
`AREA
`NETWORK A
`
`WAN
`-> ACCESS
`NODE 1
`
`WIDE
`AREA
`NETWORK
`
`WAN
`LOCAL
`AREA
`ACCESS 0
`MODE 2
`NETWORK B
`
`FIG. 2
`
`r-----_-------.--__-------__------_----__..--_--_--
`
`w, 2
`
`N D o L
`C E L 9 C
`A A T CL E
`C R O N 1 Y
`.L 0 EB R m mA
`A D C 0 \ A
`0 C
`T
`
`G C m N
`N E N1 EP N E H N E
`“A. m mm cc mm m
`N TN T E CO T
`\ NT 3
`E Ski-CK 9 Wk \
`T mm \
`
`L
`
`mm om
`R=M N TEM mA m." AA
`
`03 As
`
`w . . . . . . . . . . . , T . . , , . . . . T , . . . . . . . . . . 1 . . . . -
`
`mm NR
`ms \ RS \ OE OE
`ME \ ME DS TS
`Tm 9m
`
`1 \ V
`
`E
`
`2 3
`2 T 2
`
`S mu
`0 WT
`
`Petitioners' Ex. 1014 - Page 2
`
`

`
`US. Patent
`
`June 20, 1995
`
`Sheet 2 0f 6
`
`‘ 5,426,637
`
`FIG. 3
`
`SOURCE
`NOOE
`
`DESTINATION
`NODE
`
`APPLICATION
`LAYER
`
`1
`
`\31
`
`PRESENTATION
`LAYER
`
`APPLICATION
`LAYER
`
`1
`
`\3a
`
`PRESENTATION
`LAYER
`
`1
`
`\32
`
`1
`
`\4o
`
`SESSION
`LAYER
`
`1
`
`\33
`
`TRANSPORT
`LAYER
`
`1
`
`\34
`
`SESSION
`LAYER
`
`1
`
`\41
`
`TRANSPORT
`LAYER
`
`1
`
`\42
`
`NETWORK
`LAYER
`
`ROUTER
`M
`
`NETWORK
`LAYER
`
`1
`
`\as
`
`1
`
`\43
`
`DATA LINK
`LAYER
`
`BRIDGE
`
`DATA LINK
`LAYER
`
`‘
`
`\36
`
`1
`
`\44
`
`PHYSICAL
`LAYER
`
`\37
`
`PHYSICAL
`LAYER
`
`\4s
`
`Petitioners' Ex. 1014 - Page 3
`
`

`
`US. Patent
`
`June 20, 1995
`
`Sheet 3 0f 6
`
`5,426,637
`
`FIG. 4
`
`LAN A
`
`WAN AN-1
`
`WAN AN-2
`
`LAN B
`
`- ~ -
`
`“ -
`
`a}- I 1 I l I 1 I | iiv.
`
`Ki . . l ‘ . , l I I‘;
`
`S S 9
`
`O O 0 a5
`
`3 2 1 u
`
`a-‘ I . I . . . 1 1 III-v.
`
`r2 ........ we
`
`2 _ 5 .
`\ u
`
`
`
`A: 1 1 1 | | I 1 l | .- xnxd
`
`3 5 \
`
`\|.. l | | 1 | | l x izlzut
`
`\ _
`o -
`
`5 u
`
`\ u
`
`1 5 s v
`
`_
`
`u
`
`_ _ . "m t
`
`- -
`
`.5
`_\
`
`_ _
`
`
`
`“7 .5 t
`
`_
`
`FIG. 5
`
`LAN A
`
`WAN AN-1
`
`WAN AN-2
`
`LAN 8
`
`I l I I l l I l l1
`
`iv.
`
`""2
`I
`I
`
`l
`l
`-->I
`
`OS! 3
`
`FIG. 6
`
`TMG DMAC SMAC ROUTING DSAP
`
`SSAP
`
`DATA
`
`H50
`
`H51
`
`We
`
`\ss
`
`Petitioners' Ex. 1014 - Page 4
`
`

`
`Petitioners' Ex. 1014 - Page 5
`
`

`
`US. Patent
`
`June 20, 1995
`
`Sheet 5 0f 6
`
`5,426,637
`
`FIG. 9
`
`RECEIVE
`DATA FRAME
`PACKET
`
`ADJUST
`ADDRESS
`(IF REQ’D)
`I \102
`LAUNCH
`FRAME
`ON LAN
`\103
`
`END
`
`104
`
`' ESPONSE
`RECEIVED?
`
`OBTAIN
`m INFO
`(IF REQ’D)
`I, \92
`CALCULATE
`WAN
`ROUTE
`I \93
`ESTABLISH
`WAN
`CONNECTION
`
`ABANDON
`SEARCH
`REQUEST
`
`100
`
`EXCHANGE
`MAC
`INFORMATION
`\106
`
`I
`
`UPDATE LOCAL
`CONNECTION
`TABLE
`
`LOCAL ACCESS AGENT
`
`- - - - - - - - - - - _ - - - - _ - - _ - - _ _ ---g---------------_----------___----
`
`I
`
`ACCEPT
`CONNECTION
`I We
`EXCHANGE
`MAC
`INFORMATION
`\ss
`
`REMOTE ACCESS AGENT
`
`——I
`UPDATE REMOTE
`CONNECTION
`TABLE
`
`98
`
`Petitioners' Ex. 1014 - Page 6
`
`

`
`US. Patent
`
`June 20, 1995
`
`Sheet 6 0f 6
`
`5,426,637
`
`FIG. 10
`
`7
`WAN
`LAN A =
`-Source LAN Access Agts-
`---Dest. LAN Access Agts---
`NB AA NB AA NB AA
`NB AA NB AA NB AA
`S1 .1
`S1 .2
`S1 .3
`02.1
`02.2
`Q23
`
`NB
`Usr_s
`
`LAN B
`/118
`NB
`Usr_d
`
`122i
`121
`1205
`5
`i
`5 NAME EDUERY
`2
`'3
`:
`n
`5
`\12s 3
`NAME_RECOGNIZED
`'
`'
`E125;;
`E126:
`MAC_R UTING
`127;
`128;
`
`E124;
`5
`
`FIND
`
`Z
`E
`k129:
`I
`=
`§
`=
`
`E
`5
`E
`E
`X
`C131’:l
`k130;
`NAME__QuEBY
`\1325
`T
`NAMEJECDIGNIZED ,
`l
`-'
`I
`(1’
`l
`5‘
`133
`134
`135 5
`
`L
`
`"
`
`136
`
`FOUND
`
`\137
`
`FOUND _
`
`_
`
`a
`
`\138 i
`a
`139
`§
`SELECTIOPLREQUES‘T
`ESTABLISH CONNECTON
`(L
`s
`.
`‘14° .
`u
`§ CONNECTION TABLE DPDATE
`‘B
`Y
`.
`\141
`SELECLRFSPONSE?
`142=
`s
`=
`5143
`§
`§
`5
`NZAMEjEGEOGNIZEDi
`'
`
`2
`z
`2
`=
`4
`a
`E
`?
`5
`
`DATA
`
`DATA
`
`DATA
`
`Petitioners' Ex. 1014 - Page 7
`
`

`
`1
`
`5,426,637
`
`METHODS AND APPARATUS FOR
`INTERCONNECI‘ING LOCAL AREA NETWORKS
`WITH WIDE AREA BACKBONE NETWORKS
`
`2
`turing, across the interconnection between similar LAN
`media. That is, since the LANs on both sides of the
`interconnection use the same protocols, the frames need
`not be converted at the common LAN interface, but
`merely delivered across the interconnection from the
`source LAN to the destination LAN without signi?cant
`conversion.
`More recently, wide area networks, spanning large
`geographical areas including national and international
`coverage, have become available for transmitting digi
`tal data streams over long distances between users of
`the system with very high transmission rates, matching,
`or even exceeding, those of present LANs. Such wide
`area networks (WANs) have their own transmission,
`signaling and error handling facilities which generally
`do not match those of any local area network. It has
`become a signi?cant problem to transparently intercon
`nect two or more of the LANs described above by
`means of a WAN backbone in order to permit users on
`the different LANs to communicate directly with each
`other. The dif?culties in such interconnections are a
`result, in large part, of the differences in the protocols
`used by the various LANs, the further different proto
`cols of the WANs themselves, and the widely varying
`addressing schemes employed by the various LAN
`protocols.
`This proliferation of different protocols for the trans
`mission of digital data packets between geographically
`separated users has required router style interfaces be
`tween the various interconnection systems (LANs and
`WANs). Such routers, however, are expensive to de
`sign and maintain and, moreover, require expensive and
`time-consuming overhead in order to make all of the
`high level conversions required at each of the network
`interfaces. Such overhead interferes severely with the
`throughput of such systems and signi?cantly increases
`the cost of interconnecting local area networks by
`means of the increasingly available wide area networks.
`
`l0
`
`15
`
`TECHNICAL
`This invention relates to digital communication net
`works and, more particularly, to ef?cient interconnec
`tion of local area networks (LANs) by way of wide area
`networks (W ANs).
`BACKGROUND OF THE INVENTION
`It has become common to interconnect a plurality of
`user digital facilities with a “local area network,” i.e., a
`digital broadcast transmission system located in a re
`stricted geographical area and designed to interconnect
`the facilities of a single commercial or academic com
`munity of users. Such local area networks, LANs, have
`a variety of different con?gurations and employ many
`different transmission protocols. Ethernet ® and token
`rings are two of the major types of local area networks
`that are available today. These local area networks
`(LANs) use various types of digital packets, various
`signaling protocols and various error detection and
`25
`correction schemes to insure accurate transmission of
`digital streams between the users of the local area net—
`Work. Due to limitations on transmission distance with
`LAN technology, LAN networks tend to be very re
`stricted in geographical size, typically limited to a uni
`versity campus or commercial location. Such LAN
`characteristics are well known and will not be further
`described here.
`It has become increasingly important to interconnect
`such local area networks together to permit users of
`different LANs to communicate with each other. Two
`35
`general types of direct LAN interconnections have
`been made available, depending on the type of LANs
`being interconnected. These two interconnection tech
`nologies are known as routers and bridges. In general,
`routers are used to interconnect different con?gurations
`40
`of LANs (Ethernet to token ring, for example), over
`arbitrary distances, while bridges are used to intercon
`nect locally like con?gurations of LANs (token ring to
`token ring, for example). Using the Open Systems Inter
`connection (OSI) model (“Information Processing Sys
`tems-Open Systems Interconnection—Basic Refer
`ence Model,” ISO International Standard 7498, First
`Edition, Oct. 15, 1984), routers operate at layer 3 of the
`model (the network layer) while bridges operate at
`layer 2 (the data link layer, or more precisely, the Me
`dium Access Control (MAC) layer). More speci?cally,
`routers at layer 3 terminate the local data link layer
`protocols and utilize network layer addresses and data
`frame restructuring to communicate across the WAN
`interconnection. Layer 3 architectures in which such
`routers might ?nd use include such well known systems
`as TCP/IP Internet Protocols (Internetworking with
`TCP/IP-Princzlples, Protocols and Architecture, Comer,
`Prentice-Hall, 1989), 0813 (“Intermediate System to
`Intermediate System Intra-Domain Routing Protocol
`for Use in Conjunction with the Protocol for Providing
`the Connectionless-Mode Network Service,” ISO 8473,
`ISO/DIS 10589, 1990), and SNA (“System Network
`Architecture-Format and Protocol Reference Man
`ual,” IBM Document SC30-3ll2, 1980).
`65
`Bridges at layer 2, on the other hand, utilize the MAC
`address of the destination from the source LAN itself
`and thus communicate directly, without frame restruc
`
`45
`
`SUMMARY OF THE INVENTION
`In accordance with the illustrative embodiment of the
`present invention, the overhead required for intercon
`nections between local area networks via wide area
`networks is reduced by utilizing high level (081 layer 3)
`interactions for interconnection signaling, but utilizing
`low level (OSI layer 2) interactions for the actual data
`transmissions across the wide area network. More par
`ticularly, if the widely separated LANs utilize compati
`ble MAC protocols, data packets are exchanged be
`tween them across the WAN backbone based solely on
`MAC-layer information with no signi?cant conversion.
`The call setup and other control messages, on the other
`hand, must be analyzed at the respective protocol’s
`network layer in order to locate the remote communica
`tion partner by means of the WAN directory services,
`to ensure suf?cient compatibility between the MAC
`protocols at the source and destination LANs, and to
`establish a suitable connection across the WAN to serve
`the communicating LAN stations. The present inven
`tion is, in general, directed toward the use of high level
`signaling combined with low level data transfer.
`More particularly, requests for connections from a
`source LAN are analyzed at the source access node to
`the WAN, using resources at 081 network layer 3 to
`determine the location and the MAC protocol of the
`destination LAN. If the destination can be located by
`the WAN directory services and if these protocols
`
`Petitioners' Ex. 1014 - Page 8
`
`

`
`5,426,637
`3
`match (highly likely between LANs wishing to commu
`nicate with each other), a connection is calculated
`through the WAN to a WAN access node attached to
`the destination LAN. After assuring an optimal connec
`tion through the WAN, the source access node and the
`destination access node create connection table entries
`at both ends of the WAN connection which can be used
`to convert a source LAN data frame into a form suitable
`for packet transmission across the WAN connection
`and, conversely, convert the received packet into a
`form suitable for delivery to the local LAN. These
`connection table entries are symmetrical so that data
`frames can be exchanged in both directions. The con
`nection tables can be invoked at 081 data link layer 2,
`signi?cantly reducing the overhead involved in deliver
`ing data frames across the WAN.
`Using the “high signaling level, low data exchange
`level” paradigm of the present invention, all of the
`flexibility of the router form of interconnection between
`source and destination LANs is preserved while, at the
`20
`same time, securing all of the simplicity and speed of the
`bridge form of interconnection. This approach to the
`interconnection of LANs over a WAN optimizes the
`use of all of the resources of the WAN to provide sim
`ple and fast interconnections.
`It is to be noted that, although the present invention
`will be described in terms of interconnecting local area
`networks (LANs) by means of wide area networks
`(WANs), the high signaling level, low data exchange
`level approach is also suitable for interconnecting
`LANs by means of “metropolitan area networks”
`(MANs), and for interconnecting MANs by means of
`WANs. Indeed, the present invention can be described
`as a technique for conserving the resources of any rela
`tively wide area network which is used to interconnect
`two more localized networks.
`
`25
`
`4
`response to the arrival of a frame from a connected
`local area network in accordance with the present in
`vention;
`FIG. 8 is a flow chart of the procedures taking place
`in the access node of FIG. 1 in response to the arrival of
`a response from a remote access node of the wide area
`network in accordance with the present invention;
`FIG. 9 is a ?ow chart of the procedures taking place
`in the access agents of FIG. 1 when a data frame is
`received at a remote access agent in accordance with
`the present invention; and
`FIG. 10 shows a schematic time line diagram of the
`message exchanges necessary to set up a “NetBIOS”
`connection between two similar local area networks
`using the high level control and low level data ex
`change principles of the present invention.
`To facilitate reader understanding, identical refer
`ence numerals are used to designate elements common
`to the ?gures.
`
`DETAILED DESCRIPTION
`Before proceeding to a description of the present
`invention, the prior art mechanisms for interconnecting
`local area networks (LANs) will be described. The
`principal LANs currently available are token rings,
`typi?ed by IBM’s Token Ring and Fiber Digital Data
`Interconnect (FDDI) System, and backbone switched
`bus systems, typi?ed by Ethernet ®. Such LANs are of
`limited geographical size due to signal propagation
`range, delay distortion and other digital transmission
`limitations. It has therefore become of increasing impor
`tance to interconnect such LANs to enable users of
`different LANS to communicate directly with each
`other. Attempts to use repeaters to extend the area over
`which LANs can operate are limited by the inherent
`delay distortions involved in transmission facilities with
`propagation delays large compared to the duration of
`signals being transmitted.
`Devices currently available for the interconnection
`of LANs are MAC (media access control) data link
`layer bridges and network layer routers. MAC bridges
`provide a very fast, high throughput data path with
`frame forwarding determined completely by the con
`tents of the MAC header. The destination address in the
`MAC header is located in a ?at, unstructured address
`space, making it difficult to partition the address space
`into segments suitable for network management, rout
`ing and bandwidth control. More importantly, LANs
`initiate a connection by broadcasting a connection setup
`request message across the entire network, leading to an
`explosion of broadcast traf?c on large networks, and
`interrupting end stations which must respond to such
`connection request messages. Such broadcast signaling
`procedures on LANs are known as “discovery proce
`dures” which can consume signi?cant portions of the
`available bandwidth as the LAN population grows, and
`can in?ict on the network what is commonly referred to
`as “broadcast storms” which severely restrict the trans
`mission capacity of the network.
`MAC bridges have the advantages of simplicity, since
`every packet uses the same address formats irrespective
`of the network layer protocols, since packets are for
`warded without decomposition, permitting easy deci
`sions (to forward or not to forward), and being less
`expensive due to these advantages. On the other hand,
`bridges must look at all packets to determine routing,
`leading to more likely overloads, will generally not
`tolerate loops (multiple paths) in the network, will not
`
`35
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`A complete understanding of the present invention
`may be gained by considering the following detailed
`40
`description in conjunction with the accompanying
`drawings, in which:
`FIG. 1 shows a general block diagram of a wide area
`network used to interconnect two local area networks
`and in which the interconnection system of the present
`45
`invention might be used;
`FIG. 2 shows a general block diagram of a wide area
`network access node which might be used to interface
`the local area networks of FIG. 1 with the wide area
`network in accordance with the present invention;
`50
`FIG. 3 shows a schematic block diagram of the Open
`Systems Interconnect (081) Reference Model for a
`layered communications architecture showing the dif
`ference between the bridge and router approaches to
`local area network interconnection;
`55
`FIG. 4 shows a general block diagram of the OSI
`layer levels required for processing control frames in
`accordance with the present invention;
`FIG. 5 shows a general block diagram of the OSI
`layer levels required for processing data frames in ac
`60
`cordance with the present invention;
`FIG. 6 shows a schematic diagram of a typical local
`area network data frame which might be transmitted
`between geographically separated local area networks
`by way of a wide area network in accordance with the
`present invention;
`FIG. 7 is a ?ow chart of the procedures taking place
`in the access nodes of FIG. 1 of a wide area network in
`
`65
`
`Petitioners' Ex. 1014 - Page 9
`
`

`
`5,426,637
`5
`permit transmission redundancy or load splitting and
`hence require the disablement of redundant connections
`by some form of “spanning tree” algorithm. Finally, a
`bridge must pass on all broadcasts since it does not
`contain the resources to determine suitability of for
`warding.
`Routers, on the other hand, operate at the network
`layer of the supported protocols and utilize network
`layer addresses (logical addresses) to forward packets.
`Such logical addresses are generally hierarchical in
`nature, readily supporting network partitioning and
`permitting packet flow control and traffic management.
`Only the packets addressed to the local router need be
`examined, reducing the possibility of traffic overload by
`broadcast storms. On the other hand, routers are more
`complicated and dif?cult to design than bridges. For
`each packet, the network header must be examined and
`decoded to obtain its destination address, requiring
`customization for every different protocol, requiring a
`routing table to translate the logical addresses into sub
`net addresses, and hence being more expensive. More
`over, such high levels of per packet processing severely
`limit the router throughput capability.
`It has become increasingly common to package both
`a bridge and a router in the same device, called a
`“brouter,” but where each sub-device operates indepen
`dently of the other. The router portion is used if the
`brouter understands the network layer protocols, and
`the bridge is used otherwise.
`A large number of wide area networks (WANs) are
`becoming available to interconnect widely separated
`users. Such WANs utilize a plurality of switching nodes
`at which packets are routed on to the next node depend
`ing on routing information in the packet header. Routes
`are precalculated depending on loading, facility avail
`abilities and special needs of the connection. One of the
`most important problems of the present time is to effi
`ciently use the new WANs to interconnect the large
`number of existing LANs. The present invention is
`directed toward a solution to this problem.
`40
`In FIG. 1 there is shown a general block diagram of
`wide area network (WAN) 10 being used to intercon
`nect two local area networks (LANs) 11 and 12 and in
`which the interconnection system of the present inven
`tion might ?nd use. In order to accomplish these inter
`connections, a plurality of WAN access nodes, includ
`ing access nodes 13 and 14, are used at the interface
`between the LANs 11 and 12 and WAN 10. Access
`nodes 13 and 14 provide the mechanisms to accept
`control and data frames from the connected LANs 11
`and 12 and to perform all of the control functions neces
`sary to effect the interconnection between LANs 11 and
`12.
`In FIG. 2 there is shown a more detailed block dia
`gram of one of the WAN access nodes 13 and 14 of
`55
`FIG. 1. WAN access node 15 of FIG. 2 comprises a
`LAN access agent 16, used to directly interface with a
`local area network accessed at the left of FIG. 2, direc
`tory services unit 22, used to translate logical addresses
`of network layer entities into the WAN address of a
`suitable destination WAN access node and destination
`MAC address, which can be used to actually route data
`packets to the destination LANs, and transport services
`unit 23 which provides the services necessary to encap
`sulate LAN frames for transmission across the WAN 10
`of FIG. 1. The constituents of the WAN access node 15
`of FIG. 1 can be implemented in special purpose cir
`cuitry but, in the preferred embodiment, are imple
`
`6
`mented in software which can be executed by a large
`class of general purpose computers.
`More particularly, the transport services unit 23 satis
`?es the communication requirements set by its users in
`order to optimally match the quality of service require
`ments of the users to the underlying transmission facili
`ties. The major functions of unit 23 include the selection
`of optimum routes and the maintenance of the desired
`quality of service parameters. The users of these ser
`vices are the LAN access agents such as agent 16, iden
`ti?ed by suitable WAN addresses. In general, transport
`services unit 23 provides low latency, high-bandwidth
`unicast and multicast connections through the wide
`area network, including real-time services, bandwidth
`reservation and multicasting between groups of trans
`port users which can be dynamically created and identi
`?ed by a group address.
`Directory services unit 22 provides the distributed
`procedures required to dynamically map the addresses
`of network layer entities in stations attached to the
`interconnected LANs into the WAN transport ad
`dresses of peer access agents through which communi
`cation with the respective stations can be accommo
`dated, and into the pertinent destination MAC ad
`dresses of the LAN stations where the respective enti
`ties reside. Directory services unit 22 relies on the regis
`tration of the necessary addressing information by the
`local LAN access agents in the form of suitable address
`pre?xes as employed by the external protocols executed
`on the LAN, thus indicating reachability of stations
`identi?ed by network layer addresses derived from such
`pre?xes. If the LAN protocol incorporates a network
`layer with structured addresses, the access agent learns
`these provided pre?xes by dynamically participating in
`the local protocols or by querying the local con?gura
`tion. If a LAN protocol uses a flat, unstructured ad
`dressing scheme, the WAN-attached LANs are arbi
`trarily and administratively partitioned into selected
`groups which are assigned virtual address pre?xes un—
`known to the local protocol but used by the access
`agents to locate destinations as in the case of structured
`addresses described above. When requested by a LAN
`access agent, directory services unit 22 performs ad
`dress resolution among the group of LAN access agents
`which support a speci?ed protocol and have previously
`registered the speci?ed address pre?x. (See “Efficient,
`Real-Time Address Resolution in Backbone Net
`works,” by W. Doeringer et al., IBM Research Report
`RZ2357, July, 1992.)
`LAN access agent 16 forms the point of attachment
`between the WAN and the attached external LANs.
`The principal purpose of access agent 16 is to mediate
`between the external LAN protocols and the protocols
`available on the backbone WAN used to achieve the
`transparent inter-LAN connection. LAN access agent
`16 comprises a protocol component 18 which interacts
`with control frames from the LAN to set up, take down
`and otherwise control the connection to the remote
`LAN. A relay component 18 of access agent 16 inter
`acts at the MAC-layer level with data frames from the
`LAN to forward such data frames through WAN 10.
`Connection tables 19 are created and augmented to
`provide the information necessary to control separate
`WAN connections for each active pair of source and
`destination MAC addresses. More speci?cally, connec
`tion tables 19 hold entries that map pairs of MAC ad
`dresses (the source and destination MAC addresses
`found in a MAC~layer packet header) to the WAN
`
`25
`
`35
`
`45
`
`50
`
`60
`
`65
`
`Petitioners' Ex. 1014 - Page 10
`
`

`
`20
`
`30
`
`5,426,637
`8
`7
`connection that was previously established to relay the
`an entry in the connection tables 19, established by
`protocol component 18, to encapsulate the MAC-layer
`MAC frames between the two LAN stations identi?ed
`by these MAC addresses. The entries in the connection
`frame and to forward the data frame through the previ
`ously de?ned WAN connection.
`tables 19 include no awareness of network layer infor
`mation.
`The present invention utilizes the access agent archi
`Connection component 21 invokes transport services
`tecture of FIG. 2 to provide a “high-level signaling,
`low-level switching” scheme for interconnecting LANs
`unit 23 to establish and manage suitable WAN connec
`tions for the relaying of LAN data frames as requested
`through a backbone WAN. In general, the LAN access
`by the protocol component 18. The separation of con
`agents monitor the local LAN broadcast search proce
`trol and data frames shown in FIG. 2 is based only on
`dures and extract pertinent address information from
`information in the MAC layer headers. Most typically,
`the network layer signaling information. From this, a
`control frames are comprised of MAC frames destined
`suitable address pre?x is derived which is then pres
`ented to directory services 22 to guide the locate proce
`to a LAN broadcast or group address, whereas point
`to-point MAC frames are treated as plain data frames.
`dures for the looked-for resource, thus minimizing the
`signaling overhead in the WAN backbone. When the
`In every case, some mechanism is provided to distin
`guish between control and data frames.
`requested resource is located, exactly one LAN access
`The protocol component 18 is cognizant of the local
`agent at the source LAN and one access agent at the
`LAN protocol formats and semantics and is used to
`destination LAN are chosen to support the relaying of
`subsequent point-to-point LAN frames exchanged be
`convert between such local LAN protocols and its
`broadcast signaling procedures and the services pro
`tween the LAN end stations. The selected LAN access
`vided by the other components of the LAN access
`agents establish between themselves a WAN transport
`agent 16 and by the WAN components. In this way, the
`connection with suitable bandwidth guarantees and
`local protocol particulars are hidden from the balance
`service characteristics. The LAN access agents then
`of the wide area network. For example, when the LAN
`perform a reliable message exchange (such as over a
`protocol initiates a search procedure, the protocol agent
`long-lived WAN connection established between these
`25
`18 registers, if present, the reachability information for
`agents to perform such control exchanges) to communi
`the local resources embedded in the respective protocol
`cate all information required to establish the required
`frames (i.e., the address pre?xes) with directory ser
`entries in their connection tables. These connection
`table entries map the pair of MAC addresses of the
`vices unit 22 and initiates searches for resources which
`are not available locally. Reciprocally, directory ser
`source and destination LAN stations into a correspond
`ing WAN connection. Any subsequent point-to-point
`vices unit 22 invokes the protocol components 18 in the
`traffic between the two LAN stations is encapsulated
`appropriate access nodes in order to search the local
`LANs for the location of a particular destination LAN
`and routed through this WAN connection across the
`backbone WAN. That is, any point-to-point LAN frame
`station. The results of such searches may then be cached
`by the WAN access agents in address cache 24 con
`received by either LAN access agent is forwarded
`nected to protocol component 18, used to expedite the
`across the selected WAN connectionto the other LAN
`processing of future search procedures. That is, address
`access agent which, in turn, forwards the frame onto the
`cache 24 stores network layer addresses of network
`local LAN for delivery to the destination LAN end
`layer entities residing in stations attached to local and
`station.
`remote LANs, along with supporting information. For
`FIG. 3 shows a schematic diagram of the traditional
`40
`entities attached locally, the supporting information is
`Open Systems Interconnection (OSI) reference model
`disclosed in “Information Processing SystemsOpen
`the respective MAC addresses. For entities in LAN
`Systems InterconnectionBasic Reference Mode ,” ISO
`stations on remote LANs, the supporting information is
`International Standard 7498, First Edition, Oct. 15,
`the WAN transport addresses of the WAN access
`agents through which these entities may be reached. In
`1984. As can be seen in FIG. 3, communication between
`other words, the address cache 24 contains information
`two different users at a source node of a packet commu
`which was acquired via WAN directory services 22 and
`nications network and a destination node on that same
`LAN searches.
`network involves the use of up to seven layers of proto
`The connection component 20 establishes new WAN
`col. Each of the seven layers is isolated from the others
`connections upon request from protocol component 18,
`but meets interface standards that allow each layer to
`communicate with the adjacent layers. This layered
`enforces local policy constraints regarding the reuse of
`approach permits the implementation of the individual
`existing connection