United States Patent [19]
`Hart et al.
`
`[11] Patent Number:
`[45] Date of Patent:
`
`4,706,081
`Nov. 10, 1987
`
`[54] METHOD AND APPARATUS FOR
`BRIDGING LOCAL AREA NETWORKS
`[75] Inventors: John H. Hart, Campbell; Frederick J.
`Baker Sam Clara both of Calif
`’
`a
`’
`'
`[73] Assignee: Vitalink Communications
`Corporation, Fremont, Calif.
`
`_
`[21] APPl' N°" 682,061
`[22] Filed:
`Dec. 14, 1984
`
`.
`
`[51] Int. Cl.4 ....................... .. H04Q 11/04; H04] 3/00
`[52] US. Cl. ............................... .. 340/825.03; 370/61;
`370/94; 375/7
`[58] Field of Search ......... .. 340/825.03, 825.5, 825.05,
`340/8502, 325,03; 375/7, 3; 370/60, 61, 62,
`94, 91, 94 U, 35
`
`[56]
`
`_
`References Clted
`US. PATENT DOCUMENTS
`
`Ulug ............................... .. 370/94 U
`
`4:5O9:167 4/1985
`4,539,679 9/1935
`4,547,880 lO/l985
`
`OTHER PUBLICATIONS
`The Ethernet, a Local Area Network Data Link Layer
`
`and Physical Layer Speci?cations, Version 2.0, Nov.
`1982.
`IEEE Project 802’ Local Area Network Standards’
`IEEE Computer Soc1ety, Jul. 1983.
`Ethernet System Product Line, Communications
`Server User’s Guide, Feb. 1984, Bridge Communication
`Inc. (updated copy of the May 1982 Document 2.4
`Listed at p. 39 OP Speci?cation).
`ESPL Software Technical Reference Manual, vols. 1,
`2, and 3, all Jul. 1983, Bridge Communication Inc.
`
`Primary Examiner—Donald J. Yusko
`Attorney, Agent, or Firm-Donald C. Feix
`'
`
`ABSTRACT
`[57]
`A communications system interconnects local Area
`Networks (LAN’s) across broadcast simplex channels.
`The LAN’s are connected independently and transpar
`ently of protocols above the data link layer so that the
`system appears to the user at a station in one Local Area
`Network as one large single network. A bridge inter
`connects the LAN,S across Simplex channels‘ The
`bridge is constructed to permit more than two local area
`networks to be interconnected across simplex channels
`to the bridge and_ to provide communication between
`stations.
`
`19 Claims, 23 Drawing Figures
`
`A-Z LAN STATIONS
`VB1-4 VITALINK BRIDGES
`l-IV ETHERNET /802.3 LAN' S
`PRESENT INVENTION
`ONE CONFIGURATION OF THE
`
`Petitioners' Ex. 1016 - Page 1
`
`

`
`U. S. Patent Nov. 10,1987
`
`Sheetl of19
`
`4,706,081
`
`ISO LAYER
`
`. APPLICATION
`
`PRESENTAION
`
`SESSION
`
`TRANSPORT
`
`NETWORK
`
`-
`
`DATA LINK
`
`PHYSICAL
`
`+ ---------------------- = -= +
`
`A
`
`7 I
`
`+~= -
`I 6 I
`I " “‘
`5 l
`4’ “' ‘°
`
`'
`
`HIGHER LAYER
`GATEWAY S
`
`I
`
`:
`
`-==-+
`I
`|
`“‘ “I I
`I
`I
`‘“ " ‘I’
`I
`
`INCREASING
`1) SPECIALIZATION
`2) OVERHEAD
`3) COMPLEXITY
`
`4 I
`
`+ ----- - — -l -------------- -=- ~= +
`
`I
`
`3 l
`
`FIOUTEFIS
`
`I
`
`+ ---------------------- - - +
`
`I
`
`|
`
`I
`
`|
`
`I <
`I
`BRIDGES
`2 I
`+ ---------------------- --+ |
`I
`REPEATER
`|
`|
`
`1
`
`+ ---------------------- --= +
`
`FIG. 1 - LAN INTERCONNECT TAXONONY
`
`Petitioners' Ex. 1016 - Page 2
`
`

`
`U. S. Patent Nov. 10,1987
`
`Sheet2 ofl9
`
`4,706,081
`
`a
`
`BROADCAST
`
`u
`
`NETWORK
`
`)
`
`A-Z LAN STATIONS
`VB1-4 VITALINK BRIDGES
`HV ETHERNET /802.3 LAN' S
`F|G_ 2 - ONE CONFIGURATION OF THE PRESENT INVENTION
`
`Petitioners' Ex. 1016 - Page 3
`
`

`
`U. 8. Patent Nov. 10,1987
`
`Sheet3 ofl9
`
`4,706,081
`
`<N .GI
`
`Petitioners' Ex. 1016 - Page 4
`
`

`
`U. S. Patent Nov. 10,1987
`
`Sheet4 of 19
`
`0.,
`
`
`
`
`
`s_5oms_._.Z_On_O._.._.Z_On__>5_nm_>_5<on_<omm
`
`
`
`
`
`
`
`1...mmogmmv_z:<:>N_OZ_._.Om_ZZOO¢m_._.Z_n.8VGE
`
`
`
`
`
`
`
`
`
`+Iuuuu+4.mm>_A::::::::::::!.v__m>__mm>_uuuuuuuuuuuuuuuv__m_>_+I..IIu+v_Z_.._xm._n5o_+..unun++....onu+Auuuuuuuuuuuuunu+nu......+
`
`
`
`
`+Iu|n..++nIuu..+M\uu-n_v-uiTunn_YuL.Tun_TuLTEOIL_n/9+u..uII+
`
`
`
`
`
`
`
`mdzz<:oxm._%__mw
`
`Petitioners’ Ex‘. 1016 - Page 5
`
`
`
`
`
`m2:._<:mmmmm:<02.9Nmanor.O._.ZO_._..Qn_<Im.G—H—
`
`_u___m__.Q.
`
`+uua++u|n++I:n+
`
`
`
`
`
`+n....++n.:.++..«..++uuu++nn..++uu..+u__>_N__>__x_\nO--O-oOu....|..O-!.O-..u..\+nuu++..au+
`
`
`+un..+____>_
`
`§ :
`
`3UJ
`
`E E
`
`.xmozfimz
`
`um_zom_v_o<m
`
`B<oo<omm
`
`m_._._._.._w._.<m
`
`Petitioners' Ex. 1016 - Page 5
`
`

`
`U. S. Patent Nov. 10,1987
`
`0
`
`794
`
`1oo0m,
`
`
`
`s5_nm_s_._.Z_On_op._.Z_On__2:_nm_s_5<oo<omm
`
`
`
`
`
`
`
`
`
`
`
`
`,Tu!:.+xz:xm_._%o713+7-11,.m_zz<_._oxm._n_s__m
`+'|'llv+i1._—v.loIIr"+IIIIIII'|II‘III||_mm_>_A.............lv___mm:_................iv
`
`.__..
`
`
`
`
`
`.__m>_..._mzz<:oxm#_s__m
`
`%.mm__@9on_o»aim-D.0_n_
`
`6mxz:xm._%oTzmdzz<:oxm._..._s__mzeVemmzosmi
`
`
`
`
`mmposmmmmfizmo%+.i»a-++l""++1}-..dzz<:oxm._n_s__m_Zm>_AIIIIIIIIIIIIIIIV—__Zm>_II|IIIIIIIIIIIIIIIV
`+uaa:u+V.v_z_._xm_._n5o__Tlul..............I_R.
`
`
`
`0ZII
`
`mmpzmo
`
`Petitioners’ Ex. 1016 - Page 6
`
`Petitioners' Ex. 1016 - Page 6
`
`

`
`U. S. Patent Nov. 10,1987
`
`Sheet6 of19
`
`4,706,081
`
`<m .GE
`
`Petitioners' Ex. 1016 - Page 7
`
`

`
`U. S. Patent Nov. 10, 1987
`
`
`
`
`
` ¢usu++unn++unn+_m__m_.._m_+ua:++IIu++I:n+
`
`
`
`
`
`~--o-----ouuuuusouuuonaux
`
`
`
`mDI_m>_E<azoom_m+-4--+
`
`+unuuu+
`
`mos:..
`
`smom.
`
`t
`
`1
`
`00nuM
`
`11
`
`wswam_.hmos:..SB
`
`am+||l||+
`
`
`.Nxmcosmm_m>_HI+IuvuI+
`
`+aun++III+7.,.m._m_AH+Iun++uII+._-0aunaoun«a|l
`n7\AU%\
`
`mm.G_n_
`
`
`
`
`
` +:nuuu+_m>_+-----+ma:_\---o--o....--o-----o--.
`
`
`
` +a|u++uuu++unu+_m_...m__m_+|ll++l.Il++.Ill+
`
`
`
`....oo2_
`
`
`
`..zmom
`
`mmQ02.
`
`
`
`..zmom
`
`+nnrnu+
`
`+nun++Iv:+_m__m_+lII++lII+__\---o--o------o--\.+auuuI+_m>_._wczmm
`
`Petitioners’ Ex. 1016 - Page 8
`
`Petitioners' Ex. 1016 - Page 8
`
`

`
`U. S. Patent Nov. 10,1987
`
`Sheet8 of19
`
`4,706,081
`
`+----'+
`
`.. VB3 TX <---
`
`. VB1 Rx --->
`VB2 Rx --->
`
`VB3
`
`+_._.—---.-—-—_———
`
`+-----
`
`o
`°0
`
`. ‘
`
`‘
`
`c o
`
`n 0 9 I
`
`: n
`
`+-----+
`
`---> VB1 TX .
`
`<--- VB2 Rx
`<--- ves Rx
`
`.
`
`VB1
`
`<--- VBN Rx
`
`-
`
`+-—---+
`
`' .
`
`-
`
`N SIMPLEX CHANNELS
`
`+-----+
`I
`I <-“
`I
`I <"" VB3 FIX
`I
`'
`C
`I VB2
`I
`-
`-
`I
`I
`|
`| <--- VBN RX
`I
`I
`|
`|
`--—> VB2 TX
`+----—+
`
`n a
`
`no
`
`.°
`
`-°
`
`-'
`
`.'
`
`N
`
`Z
`0
`=-
`G
`
`Z
`*3
`=-
`=7
`
`I
`G
`-
`C
`
`Z
`u
`-=
`‘-
`
`_
`
`G I
`
`‘B
`
`‘-
`
`‘-»
`
`‘I.
`
`'-
`
`'-
`
`+-----+
`-‘-> I
`U
`VB2 RX "“‘> :
`a
`G
`-
`I VBN I
`I
`I
`VBN-1 RX ‘> :
`:
`VBN TX <"‘ I
`I
`+——-—-+
`
`FIG. 6 " FULLY CONNECTED TOPOLOGY
`
`REMOTE VB'S AND LAN'S
`
`REMOTE VB'S AND LAN'S
`
`STAR1 '
`
`+-----+
`I v31 I
`+-—--—+
`
`sTAR2
`
`+-----+
`I v32 I
`+-----+
`
`I
`CENTRAL SITE
`I
`1 ------o----o ----- --o----- --o---—o------I
`LANI
`I
`I
`I
`+---=+
`«I----+
`+-——+
`
`|_AN|
`
`ISI
`+---+
`
`ISI
`+——-+
`
`ISI STATIONS
`+---+
`
`FIG. 7 - DOUBLE STAR TOPOLOGY
`
`Petitioners’ Ex. 1016 - Page 9
`
`Petitioners' Ex. 1016 - Page 9
`
`

`
`U. S. Patent Nov. 10,1987
`
`Sheet9 of19
`
`4,706,081
`
`.._m_.¢m>_+sIv++I:Iuv+._\|IIOI|O|tInOII\___Z<4
`..e>443;
`..aompomzzoo
`
`+a|v++nIn:n+
`....xmo;»mz.
`
`mmtmmmxpo
`
`
`
`mmpaEMIHO
`
`___z<4_
`
`+uIuIu+_om>_+u:n:s+\
`
`\X23JE-E
`
`
`
`_mm>__m_.._m_
`
`\+In|uu++uuu++un:+
`
`
`
`
`
` +Iun++:::+_m._..._m_+Ina++Isu+__T-o---o....--o-L
`
`.23__+Iuuuu+
`
`
` +:nuuu+_mm>__.m>_+Iau»n++uuunu+
`
`Nmim_aim
`
`
`
`
`
` +Iuau|++IuI++::n+___T-o-----o--o....--o--o---L
`
`
`
`
`
`zo:<m:o_n_zooNmanor.omoz<n_xm_-G.mv_n_.
`
`Pefifi0ners'Ex.1016-Pagelfl
`
`Petitioners' Ex. 1016 - Page 10
`
`

`
`U. S. Patent Nov. 10,1987
`
`Sheet 10 ofl9 4,706,081
`
`EXPANDED CONFIGURATION
`
`STARI + LANI + STAR2
`+ FULLY CONNECTED ‘’
`LAN II * STAR 3
`
`9 ‘ USER PERSPECTIVE
`
`FIG. 10
`
`PRIMARY ROLE OF VITALINK
`
`BRIDGE
`
`(
`
`)
`
`+----—+
`I VB I
`+-—---+
`I
`—-0 ----- --o ------ --o--
`I
`I
`+---+
`+---+
`I S 1 n I I‘ S I
`+----+, +-——+
`
`+-----=+
`I VB I
`+---—-+
`I
`--o—---—o ---- ---O--
`I
`I
`+<--—+
`+---+
`l S l. I l I S ‘
`+---+
`+---+
`
`BRIDGE
`VB = VITALINK
`S = ETHERNET/802.3 LAN STATIONS
`
`Petitioners' Ex. 1016 - Page 11
`
`

`
`U. S. Patent Nov. 10,1987
`
`Sheet 11 0f19 4,706,081
`
`FIG. 11
`SECONDARY ROLE OF VITALINK
`
`BRIDGE
`
`SATTELITE BACKBONE
`
`SATELLITE BACKBONE
`
`I
`I
`----o——--o---o-—-----o-
`
`I
`+-----+
`
`I
`---—--o-------o-——o-,
`
`v.8
`S
`
`" VITALINK
`
`BRIDGE
`
`= ETHERNET/802.3 LAN STATIONS
`
`|
`I
`+---+
`+---*
`I '8 |...| s I
`
`Petitioners' Ex. 1016 - Page 12
`
`

`
`U. S. Patent Nov. 10,1937
`
`Sheet 12 of19 4,706,081
`
`
`
`
`
`oz_om<om_o..oz_zm<m._m__2<...E
`
`
`
`mmom<2Eou_ms_<E
`
`Nw.G_u_
`
`
`
`620.529.oz_m<2Eou.oz<
`
`+uuuuuuuuuuuuuuuuso++uuuuuuuuuuu1++uuuuuuuuuuuuuuuucu+_________mmo<z<s__.__mo<nEm:z__AIV_mooim_Auv_mo<n_m_m._.z_V__+uuuuuuuuuuuu+__v_m_O>>._.m_Z_>__xmozfimzfl___<__u_<OO..__+IIIIIIIIII11+_m_zomv_o<m____.!..v__u..v____Al._.Al.__++IIIIIIIIIIIIIIIIII+
`
`u_<OO._mzomv_o<m
`
`
`..u+.wzo:.oz:u_+uuuuuuuuuuuuuuuuuuuuuuuuuuuuuu
`m>_5om_xm__wm<>>Dm<I®+uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu+|u|..|lu>>.__mzo:ozEG<<mm<25m<:
`
`
`
`_A-vEO>>.Ez..v._Auuuuuuuuuuunu:n_o.2uuuuuuuuuuuv__AIE0352uv_
`
`
`
`
`
`
`
`
`
`om<om“Som_<ommmSn.s_ooZ_<S_nE<om_.:._\_
`
`
`
`
`
`
`
`muo<#m:z_mommm
`
`
`
`
`
`mmoEmm:z_Annm_2<E
`
`
`
`
`
`n_Z<:_Om._.ZOOAlvEzm22:02luv
`
`Petitioners’ Ex. 1016 - Page 13
`
`Petitioners' Ex. 1016 - Page 13
`
`

`
`U. S. Patent Nov. 10,1987
`
`Sheet 13 ofl9 4,706,081
`
`LOCAL NETWORK TO FORWARDING FUNCTION
`
`----------- --+
`|
`l
`I
`
`+--------------—----+
`|
`FORWARDING
`I
`FUNCTION
`| ----------------- ——
`
`.——__n-_—_—_
`
`+------------
`
`BACKBONE
`NETWORK
`CONTROL
`
`|_..-.__.________.
`
`T
`‘
`I/P CALL L
`I I I l I I I I I l I V
`
`LOCAL
`NETWORK
`CONTROL
`
`I
`I
`l
`I
`I
`I
`l
`
`I
`
`|
`l
`I
`
`l/P RETN
`
`1. 'CREATES INPUT
`TO FORWARDING
`DATA STORE
`MAINTENANCE
`0"” CAL‘
`FUNCTION
`2 FORWARDS ENET ______ “’
`n
`-
`-
`FRAME
`
`O/P RETN
`
`Petitioners' Ex. 1016 - Page 14
`
`

`
`U. S. Patent Nov. 10,1987
`
`Sheet 14 ofl9 4,706,081
`
`FIG. 14
`MANAGEMENT FUNCTIONS TO FORWARDING FUNCTION
`
`l..ll._ @
` m." A_ C.
`P.
`O.
`l.
`
`
`
`.lll. _ _ L_
`
`
`. >
`
`G4" N
`MN. E
`R“. D AC. R
`DO. S
`WN. AE
`OF- RA F _ OR " FF
`HU_ WM
`
`E .
`
`u a
`
`ORO
`E NKL
`BOR
`CTN
`BNC
`AEO
`KWT
`
`l I I l l | I I ll.
`
`I I I I | l I I ||.|__
`
`O/P CALL
`-—-——------—>
`
`_ T
`
`ms
`
`Wm GTII.
`
`AC MN
`MW
`
`-----------+
`
`Petitioners' Ex. 1016 - Page 15
`
`

`
`U. S. Patent Nov. 10,1987
`
`Sheet 150m 4,706,081
`
`FIG. 15
`
`65536 OCTET SEGMENT
`
`FDS INDEX
`
`+------——--—--------+
`I
`I
`FDS INDEX FOR
`I
`I
`I
`I
`+
`+
`l
`I
`I
`l
`l
`l
`
`FGII‘B O m m . .
`MAEQQ
`VAR-0e.
`Mfr-So:
`
`MDNIG URE.3
`AOT-n
`IWRu
`noa
`mwA
`I+ . _ _ _ _ . _ _ _ _ _ _ . _ _
`
`‘I'll’, A T
`
`OCTET
`
`1’ 0000
`
`2 0 O O +
`
`+1FFE
`
`0
`
`I
`
`n
`
`O
`
`-
`
`O _ - w“ “ I+ I .I +
`
`+ n n
`
`_ _
`
`I 00000000 | 00111111 I
`I 01234557 I 89012345 I
`+--------+--------+
`I
`| 000 + FDSE INDEX
`+--------+--------+
`F
`“A; u “N: u H. .
`8+ .f D u n
`
`+ll+ “ u - _
`
`I
`I000 1' FDSE INDEX
`+-----——-+--------+
`
`G i l 0 O I Q l I 0
`
`FIRST FDSE FOR GLOBAL ADDRESS = XXXXXXXXX001(16)
`
`.
`
`| 00000000 | 001111 11 1 11112222 1 22222233 1
`I 01234557 I 39012345 I 67890123 1 45678901 I
`
`I
`
`GLOBAL ADDRESS (1ST 40 BITS]
`
`I
`+
`|- — - - +--------+--------+-------
`l-"> FIRST
`I SNlD/AID I FFF 4' CFSE INDEX
`+------—-+--------+-—------+—-----_--+
`CFDSE
`
`FIG. 13
`
`MADSE
`
`|
`
`BITS ASSOCIATED WITH TDSE
`
`‘III:I:II:II:i:I:I:1:111:11:
`
`BITS ASSOCIATED1WITH RDSE
`
`I
`1»
`
`Petitioners' Ex. 1016 - Page 16
`
`

`
`U. S. Patent Nov. 10,1987
`
`Sheet16 0H9 4,706,081
`
`+ - - - - - - - - - - - - - - - - - - - -+
`
`I
`
`LOCAL/BACKBONE NETWORK CONTROL
`
`I
`
`+--—---—-—------—+ |
`--------- —-+
`I
`I
`I.
`|
`I
`l """"""""""""""""""" T"
`|
`| < ---------------------------- --|
`I
`FORwAROING |
`I
`I
`I
`1-
`FUNCTION
`I
`T """""""" "T I
`l
`| -------- -->I
`TRANSLATION
`I-->I
`I
`I< ------- -- I
`OH
`I<"I
`I
`I
`I
`I ENCAPS/DECAPS I
`l
`--------- --+
`+-——------—-----+
`+--—-------—-----+
`A
`A
`I
`l
`v
`v
`+--------—-----------------------—-—-+
`
`--------- --+
`
`2,
`+-—-+
`
`|
`
`l
`
`|
`
`NETWORK
`INTERFACE
`PROCESSES
`
`l
`
`I
`
`I
`
`I
`
`|
`
`I
`I
`LOCAL/BACKBONE
`IéI :2”:
`:
`MANAGEMENT I
`" NETWORK MANAGEMENT PR CESSES
`FUNCTIONS
`I-->I Q I
`I
`+ ---------------------- "9 ————————— —-+ I
`I<"I
`|
`I
`I E I
`
`I
`
`l
`
`I
`
`I + - - ~ - - - ~ - - - - - - - - ~ - - - -+
`
`I
`
`|
`
`+--—+
`
`I
`NETWORK
`I
`< ---------------- -- MCPU ----------------- -->l<- INTERFACE ->I
`BOARD
`I
`BOARD.
`I
`
`Petitioners' Ex. 1016 - Page 17
`
`

`
`U. S. Patent Nov. 10,1987
`
`Sheetl7 ofl9 4,706,081
`
`FIG. 18
`
`|
`|
`
`I
`
`1
`
`I
`FORWARDING FUNCTION
`l
`PROCESSES
`|-------+
`
`Illa V
`
`ENET FRAME
`
`ENCAPULATED_ FRAME
`SA
`
`DA
`
`DATA
`
`m I I w n I a
`
`_ _ _ _ _
`
`_ S O _ W _ T _ E _ N _ E . N _ O _ B _ K _ C _ A _ B
`
`II. V
`
` U. T EN MW
`
`*ll
`
`.flll _ _ _ _ _ _
`_ S _ S _ E _ C . O _ R _ DI _ E . C . A .EF
`
`Petitioners' Ex. 1016 - Page 18
`
`

`
`U. S. Patent Nov. 10,1987
`
`Sheetl8 0119 4,706,081
`
`FIG. 19
`|
`SATELLITE/LAN
`I
`|
`BACKBONE NETWORK INTERFACE PROCESS
`l
`+ ———————————————— -- |
`| --------------- —-+
`
`ENCAPSULATED FRAME
`+ ------- --+ --------- -—+ ------ -- / / -------- -—+
`l
`SA
`1
`DA
`|
`DATA
`|
`+ ——————— —-+ ————————————————— -—// -------- --+
`
`I
`N
`2
`I
`1
`I
`0
`OCTET l
`+ ---------------- --+ ----- --+—-=//--+ ----- --+
`1
`ENET FRAME
`|
`
`+ ------- --+ ------- -—+ ----- --+--//--+ ----- —-+
`
`l
`I
`l
`V
`
`+ —————— -—|
`| ----- --+
`l
`FORWARDING FUNCTION
`
`Petitioners' Ex. 1016 - Page 19
`
`

`
`U. S. Patent Nov. 10,1987
`
`Sheetl9 ofl9 4,706,081
`
`
`
`EwOOE SGQOE
`
`ON .GE
`
`Petitioners' Ex. 1016 - Page 20
`
`

`
`1
`
`4,706,081
`
`METHOD AND APPARATUS FOR BRIDGING
`LOCAL AREA NETWORKS
`
`BACKGROUND OF THE INVENTION
`
`This invention relates to methods and apparatus for
`bridging together local area networks.
`This invention relates particularly to a communica-
`tion system for interconnecting multiple local area net-
`works across broadcast simplex channels independently
`and transparently of protocols above the data link layer
`so that the system appears to a user at a station in a local
`area network as one large single network.
`Ethernet networks and/or 802.3 Local Area Net-
`works (LAN’s) are being installed in conjunction with a
`wide variety of office automation and data communica-
`tion products. The LAN’s are used to interconnect a
`number of products which use various network archi-
`tectures (e.g., TCP/IP, XNS, DECnet, etc.). As addi-
`tional LAN’s are installed in other locations the need to
`link together’ the remote LAN’s is often initially ig-
`nored. Then, when interconnect options for intercon-
`necting the remote LAN’s are investigated,
`it often
`becomes apparent that the simple, multipurpose data
`highway environment (that exists within a building or a
`single LAN) has disappeared.
`Connecting a number of remote LAN’s can present
`problems in software and can also present problems in
`complex mult-vendor compatibility. The architecture
`for interconnection can also become an issue. Redun-
`dant configurations for different internet protocols may
`be required, and some to the LAN stations may not
`support an intemet implementation.
`
`SUMMARY OF THE PRESENT INVENTION
`
`It is a primary object of the present invention to inter-
`connect multiple Local Area Networks by a communi-
`cations system which avoids problems presented by
`prior art techniques.
`It is a specific object of the present invention to con-
`nect more than two Local Area Networks across sim-
`plex channels through a bridge and to provide commu-
`nication between stations.
`It is a related object to communicate with one or
`more stations and one or more remote Local Area Net-
`works independently and transparently of protocols
`above the data link layer so that the system appears to a
`user at a station in a Local Area Network as one large
`single network.
`In accordance with the present invention a plurality
`of Local Area Networks are connected together by
`multiple bridges. Each Local Area Network has at least»
`one station for sending or receiving communications to
`or from another station using data link frames contain-
`ing at least a destination address and a source address.
`The bridge interconnects the Local Area Networks
`across simplex channels and permits one or more sta-
`tions in one Local Area Network to communicate with
`one or more stations in one or more of the other Local
`Area Networks independently and transparently of
`protocols above the data link layer.
`The bridge is constructed to permit more than two
`Local Area Networks to be interconnected across sim-
`plex channels through the bridge.
`In the present invention there are four basic novel
`principles involved in the operation of the system.
`
`5
`
`l0
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`First, a simplex channel is associated with one and
`only one network.
`-
`Secondly, at each bridge a network has one and only
`one output simplex channel and one or more input sim-
`plex channels.
`Thirdly, from the standpoint of the bridge, all net-
`works and LAN’s can be defined in terms of simplex
`channels.
`
`Fourthly, a bridge is capable of bridging between
`more than two networks and LAN’s.
`and methods
`Communication system apparatus
`which incorporate the structures and techniques de-
`scribed above and which are effective to function as
`described above constitute further, specific objects of
`this invention.
`Other and further objects of the present invention
`will be apparent from the following description and
`claims and are illustrated in the accompanying drawings
`which, by way of illustration, show preferred embodi-
`ments of the present
`invention and the principles
`thereof and what are now considered to be the best
`modes contemplated for applying these principles.
`Other embodiments of the invention embodying the
`same or equivalent principles may be used and struc-
`tural changes may be made as desired by those skilled in
`the art without departing from the present invention
`and the purview of the appended claims.
`BRIEF DESCRIPTION OF THE DRAWING
`VIEWS
`
`FIG. 1 is a diagram illustrating a taxonomy for de-
`scribing Local Area Network (LAN) interconnection.
`FIG. 2 is a view of four Ethernet networks bridged
`together across a satellite network in accordance with
`one embodiment of the present invention.
`FIG. 2A is a view which corresponds to FIG. 2 but
`which shows the actual simplex channel configuration
`for a four node network.
`FIG. 3 illustrates how the FIG. 2 configuration can
`be expanded using a terrestrial line.
`FIG. 4 illustrates how two bridges can be intercon-
`nected in accordance with the present invention using
`either a broadcast medium or a point to point medium
`(e.g., a terrestrial data link).
`FIG. 5 is a comparison view showing the use of sim-
`plex channels including a single broadcast simplex chan-
`nel for star communications contrasted with the use of
`multiple point to point duplex links for star communica-
`tions.
`FIG. 5A is a view like FIG. 5 showing a star topol-
`ogy. FIG. 5A is a four node network and illustrates the
`simplex channel used for star configuration.
`FIG. 5B illustrates another topology. In FIG. 5B a
`four node network is connected in what is referred to as
`multistar topology. FIG. 5B illustrates the simplex
`channels required to support that topology.
`FIG. 6 shows how simplex channels are used in ac-
`cordance with the present invention to support a fully
`connected topology. FIG. 6 is a view like FIG. 2 but
`emphasizing and illustrating the simplex channels.
`FIG. 7 illustrates a configuration containing two star
`topologies connected to a LAN in the central site.
`FIG. 8 is a view of an expanded FIG. 7 configuration.
`FIG. 8 shows a communication system constructed in
`accordance with the present invention and embodying a
`fully connected network. FIG. 8 illustrates how star
`configurations are connected through a Local Area
`Network, and how a number of those locations can be
`
`Petitioners’ Ex. 1016 - Page 21
`
`Petitioners' Ex. 1016 - Page 21
`
`

`
`3
`connected by a fully connected network. FIG. 8 illus-
`trates the actual configuration (as distinct from the user
`perspective). The user perspective is illustrated in FIG.
`9.
`
`4,706,081
`
`5
`
`FIG. 9 is a diagrammatic View showing the user per-
`spective of a communication system incorporating the
`present invention. As illustrated in FIG. 9 the overall
`configuration is viewed by all LAN stations as contain-
`ing a single LAN.
`FIG. 10 illustrates the primary role of the bridge of 10
`the present invention.
`FIG. 11 illustrates secondary roles of the bridge of
`the present invention.
`FIG. 12 is a view of a bridge constructed in accor-
`dance with one embodiment of the present invention.
`FIG. 12 shows major component parts of the bridge.
`Subsequent figures of the drawings show further details
`of these component parts.
`FIG. 13 illustrates features of the forwarding function
`of the bridge.
`FIG. 14 illustrates features of the management func-
`tions of the bridge.
`FIG. 15 shows the format of a forwarding data store
`incorporated in the bridge of the present invention.
`FIG. 16 shows details of a multicast array data store
`entry structure as used in the present invention.
`FIG. 17 illustrates the logical structure of a local or
`backbone network control component of the bridge
`shown in FIG. 12.
`
`15
`
`20
`
`25
`
`FIG. 18 illustrates how a frame is encapsulated in
`certain operations of the bridge illustrated in FIG. 12.
`FIG. 19 illustrates how an encapsulated frame is
`decapsulated in the bridge illustrated in FIG. 12.
`FIG. 20 is a pictorial view of a communications sys-
`tem for interconnecting Local Area Networks in accor-
`dance with one embodiment of the present invention.
`DESCRIPTION OF THE PREFERRED
`EMBODIMENTS
`
`In the text of this description the following references
`. will be referred to by the abbreviations in the brackets
`as indicated.
`
`30
`
`35
`
`40
`
`45
`
`50
`
`[DEC84] Digital Equipment Corporation, Network and
`Communications Catalog, Summer, 1984
`[DIX82] Digital, Intel, and Xerox, The Ethernet: A
`Local Area Network Data Link Layer and Physical
`Layer Specifications, Version 2.0, November, 1982
`[Hawe84] Bill Hawe, Alan Kirby, and Bob Stewart,
`“Local Area Network Connection”, Telecommuni-
`cations, April, 1984
`[IEEa83] IEEE Project 802 Local Area Network Stan-
`dards, “IEEE Standard 802.3 CSMA/CO Access
`Method and Physical Layer Specifications”, Ap-
`proved Standard, July, 1983
`[IEEb83] IEEE Project 802 Local Area Network Stan- 55
`dards, “Draft IEEE‘Standard 802.4 Token Bus Ac-
`‘
`cess Method and Physical Layer Specifications”,
`Working Draft E, July, 1983
`[IEEc83] IEEE Project 802 Local Area Network Stan-
`dards, “Draft IEEE Standard 802.5 Token Ring Ac-
`cess Method and Physical Layer Specifications”,
`Working Draft, July 1983
`[ISO33] ISO-3309, “HDLC, Frame Structure”, avail-
`able from Computer and Business Equipment Manu-
`facturers Association, 1828 L St., N.W. Washington,
`DC, 20036
`[Orns75] Severo M. Ornstein and David C. Walden,
`“The Evolution of a High Performance Modular
`
`60
`
`65
`
`4
`Packet Switch”, 1975 Internat. Conf. on Comm., San
`Francisco, CA, June, 1975
`[Stew84] Bob Stewart, Bill Hawe, and Alan Kirby,
`“Local Area Network Interconnection”, Telecom-
`munications, Mar. 1984
`Currently, Ethernet networks and/or 802.3 Local
`Area Networks(LAN’s) are being installed in conjunc-
`tion with a wide variety of office automation and data
`communication products. Once installed, many of these
`LAN’s become the data highway for interconnecting
`multiple products which utilize various network archi-
`tectures (e.g. TCP/IP, XNS, DECnet, etc.).
`After one successful LAN installation, many organi-
`zations repeat the installation in multiple other loca-
`tions. In many cases the need to link remote LAN’s
`together is initially ignored. Later as organization begin
`to investigate their interconnect options, they discover
`that the simple multiple purpose data highway environ-
`ment that exists within the building has disappeared.
`The traditional Internet LAN interconnection tech-
`niques support a single architecture and consequently a
`subset of the current or potential LAN population.
`Also, since Internet processes in the LAN stations must
`assist in the interconnection, costly software upgrades
`may be required and complex multi-vendor compatibil-
`ity problems can occur. Which architecture to intercon-
`nect becomes an issue. Redundant configurations for
`the different Internet protocols may be required. Some
`of LAN stations may not support an Internet implemen-
`tation.
`
`In contrast the TransLAN configuration and method
`of the present invention provide a simple and elegant
`LAN interconnect solution that transparently extends
`the public data highway paradigm to LAN interconnec-
`tion. From the perspective of all LAN stations, the
`present invention turns on arbitrary number of Ether-
`net/802.3 LAN’s into a single LAN. Using the ISO
`Reference Model, this description briefly describes the
`relationship of the present
`invention to other LAN
`interconnect devices. Next the simple architecture and
`operational characteristics of the present invention are
`defined. This is followed by a description of the fiexibil-I
`ity of the present invention relative to satellite, terre-
`trial, and mixed configuration support, as well as its
`extensibility to 802.4 andother LAN’s.
`
`Relationship of the Present Invention to Other Products
`
`An interconnection system and method constructed
`and operated in accordance with the present invention
`uses a device termed with Vitalink Bridge. Before dis-
`cussing how the Vitalink Bridge operates, it is useful to
`understand its relationship to other LAN interconnect
`devices.
`,
`‘
`FIG. 1 illustrates a taxonomy for describing LAN
`interconnection [Stew84]. The taxonomy associates a
`LAN interconnection device with an ISO Reference
`Model layer. A device is associated with the layer in
`which it relays information from one network to an-
`other. The term network in this context ranges from
`LAN segments, satellite links, and terrestrial lines in the
`lower layers to network architectures (e.g. DECnet to
`SNA) in the higher layers.
`In this taxonomy it is important to note that the layer
`performing the relay does not utilize information from
`the higher layers. In fact, differing higher layer proto-
`cols can (and do) concurrently utilize the same lower
`layer relay. Generally, the higher the relay layer, the
`more specialized are the set of products and protocols
`
`Petitioners’ Ex. 1016 - Page 22
`
`Petitioners' Ex. 1016 - Page 22
`
`

`
`5
`serviced by the relay. Also, factors such as overhead
`and complexity increase the higher the layer number.
`The layer relays of direct interest to the present in-
`vention are Repeaters, Bridges, and Routers, layers 1-3
`respectively. The most common of the three, Repeaters
`and Routers are briefly described and then compared
`and contrasted with Bridges.
`
`REPEATERS: Physical Layer Relays
`
`Repeaters relay physical layer protocol data units
`(bits) and control signals (e.g. collision detection). They
`operate at LAN speed and add only a very small
`amount of addition delay (e.g. less than 1 microsecond).
`Repeaters are used to extend LAN configurations by
`connecting LAN channel segments together directly or
`across an internal point to point link. In general, the use
`of Repeaters in a LAN configuration is transparent to
`LAN station protocols.
`However, the use of Repeaters as a general mecha-
`nism for interconnecting multiple LAN’s is severely
`limited. The length of a single LAN (including any
`internal point to point links) is limited by Physical layer
`constraints such as maximum round trip propagation
`delay budget. This limits LAN expansion using Repeat-
`ers to a few kilometers. The maximum number of sta-
`tions that can be effectively serviced by a single LAN is
`another limiting factor.
`Since Repeaters relay bits, they are unable to selec-
`tively filter Data Link frames. Consequently, LAN
`expansion is restricted by maximum LAN capacity.
`Another consequence of the absence of filtering is that
`links used by repeaters to tie together two segments
`must operate at LAN speed.
`An Ethernet Repeater [DIX82] is an example of a
`Repeater device.
`
`ROUTERS: Network Layer Relays
`Routers are the traditional LAN interconnect de-
`vices. When using these devices, LAN stations must be
`able to distinguish between communication with a sta-
`tion on the same LAN and a remote LAN. Remote
`communication requires LAN stations to transmit/-
`receive Data Link frames to/from a Router on the same
`LAN.
`The frames contain Internet protocol data units
`(packets) created by the LAN stations. Routers utilizes
`the Internet protocol control information in the packets
`and a local configuration topology table to determine
`how to relay a packets between the LAN and other
`networks. (e.g., point to point data links).
`When compared to Repeaters, Routers are not trans-
`parent to LAN station protocols. They only work with
`LAN stations having a compatible Internet layer. Also,
`compared to Repeaters, Routers add significant delays.
`They operate as a store and—forward packet relay (not a
`bit relay). Their internal processing time usually ranges
`from 5 to 50 milliseconds but more significant are the
`internal queue delays and transmission time between
`Routers.
`
`5
`
`l0
`
`15
`
`20
`
`25
`
`30
`
`,35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`Since LAN stations perform the filtering function for
`a Router (by only sending it packets destined for a re-
`mote LAN), the Router to Router links do not need to
`operate at LAN speeds. Typical link speeds range from
`9.6 Kbps to 56 Kbps. Also, the maximum number of 65
`stations that can be effectively serviced by a single
`LAN is no longer a limiting factor. Stations can be
`spread amoung multiple interconnected LAN’s.
`
`4,706,081
`
`6
`A DECnet Router Server [DEC84] is an example of
`a Router device.
`
`BRIDGES: Data Link Layer Relays
`
`Bridges interconnect LAN’s using the same media as
`Routers, but operate totally within the Datak Link
`layer. LAN’s connected together by Bridges logically
`appear to the LAN stations as a single LAN.
`LAN stations simply address Data Link frames to
`other stations as if they were on the same LAN. Broad-
`cast and Multicast destination frames are handled prop-
`erly. They are received by the addressed group of sta-
`tions regardless of location. LAN stations do not ad-
`dress frames to Bridges as they must with Routers.
`The Frame Check Sum value created by the source
`system is delivered to the destination station. Bridged
`LAN’s have the same level of protection against cor-
`rupted data as is present on a single LAN. With Rout-
`ers, the original FCS is removed by the first Router and
`recreated by the Last.
`Like Routers, Bridges store and forward frames. This
`means, that unlike Repeaters, they are able to selec-
`tively filter and discard frames addressed to local sta-
`tions. Bridges keep local traffic on one LAN from inter-
`fering with local traffic on the other LAN’s. As a result,
`Bridge to Bridge links can operate at less than LAN
`speeds. In fact, in almost all configurations the same link
`speeds used to interconnect Routers can be used to
`interconnect Bridges.
`Also, as with Routers, the maximum number of sta-
`tions that can be effectively serviced by a single LAN is
`no longer a limiting factor. The stations can be spread
`amoung multiple bridged LAN’s [Hawe84]. In contrast
`with Routers, since Bridges relay and filter for all LAN
`stations, they provide the more general solution for a
`congested LAN.
`Since Bridges operate at a lower layer than Routers,
`they have less processing overhead and are capable of
`processing and relaying frames at higher rates (thou-
`sands of frames/second). Consequently, Bridges are
`capable of effectively utilizing high bandwidth links
`(1—lO megabits/sec) between LAN’s.
`When bridging remote LAN’s together with a link
`operating at LAN speed or two local LAN’s together
`directly, Bridges add a very small amount of additional
`delay (at most a few milliseconds). In contrast, when
`utilizing lower speed links, Bridges like Routers add
`significant delays due to transmission time. However,
`for the same configuration, the delay associated with a
`Bridge should be less than with a Router. This is due to
`the reduced processing overhead within a Bridge.
`While conceptually a Data Link Bridge is not a new
`idea, recently the potential for these devices has greatly
`increased. Specifically, Digital Equipment Corporation
`was the first to recognize this new potential [Stew84].
`The use of 48 bit global addressing in Ethernet and the
`802 LAN’s for the first time places a unique world wide
`identifier in the Data Link layer. Also, Bridges are pro-
`cessing and memory intensive devices that are able to
`exploit medium to high speed broadcast and point to
`point technologies. Significant cost reductions and tech-
`nical advancements are occurring in all of these areas.
`
`Operational Characteristics
`
`To describe the operational characteristics of the
`present invention it is useful to first illustrate and discuss
`one configuration of the present invention. FIG. 2 illus-
`trates four Ethernet [DIX82] and/or 802.3 [IEEa83]
`
`Petitioners’ Ex. 1016 - Page 23
`
`Petitioners' Ex. 1016 - Page 23
`
`

`
`4,706,081
`
`7
`LAN’s bridged together across a satellite backbone
`network.
`
`The backbone is operating in a fully connected broad-
`cast mode such that any frame transmitted by one Vita-
`link Bridge (VB1, VB2, VB3 or VB4) is received by all
`other Bridges. Each Vitalink Bridge can be configured
`to Transmit at the same or a different rate.
`A fully connected Vitalink satellite network is very
`similar to an Ethernet or 802.3 LAN. Both are a broad-
`cast transmission media, support a promiscuous (receive
`all frames) reception mode, and have a very low bit
`error rate.
`Both Ethernet and 802.3 utilize an unacknowledged
`datagram protocol. Likewise, the Vitalink Bridges uti-
`lize an unacknowledged datagram protocol ac