United States Patent 19
`Lidinskyet al.
`
`[11] Patent Number:
`
`[45] Date of Patent:
`
`4,897,874
`Jan, 30, 1990
`
`[54] METROPOLITAN AREA NETWORK
`ARRANGEMENT FOR SERVING VIRTUAL
`DATA NETWORKS
`
`[75]
`
`Inventors: William P. Lidinsky, Naperville;
`Gary A. Roediger, Downers Grove;
`Scott B. Steele, Naperville; Ronald C.
`Weddige, Western Springs; Bruce R.
`Zelle, Naperville, all of Til.
`
`[73] Assignee:
`
`American Telephone and Telegraph
`Company AT&T Bell Laboratories,
`Murray Hill, N.J.
`
`[21] Appl. No.: 175,548
`
`[22] Filed:
`
`Mar. 31, 1988
`
`[SU] Unt, C14 cccccccscscccceeee HO4L 9/00; HO4L 11/00
`P52] US. CM, ccccccccseesscssscssessesssssssesecee 380/3; 380/25;
`370/60; 370/94.1; 340/825.31; 340/825.34
`[58] Field of Search .............0000 380/3, 4, 23, 24, 25,
`380/49; 340/825.31, 825.34; 370/60, 85, 90, 94;
`178/2R
`
`[56}
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`wee 178/2 RK
`6/1978 Saito et al...
`4,093,819
`». 380/25
`- 380/49
`3/1983 Davidaet al.
`.......
`4,375,579
`4,531,020 7/1985 Wechselbergeret al.
`
`4,649,233
`3/1987 Bass etal. ...........-
`.. 380/25
`
`» 380/23
`4,691,355
`9/1987 Wirstrom et al.
`.. 370/60
`4,764,919
`8/1988 Hunter etal. ....
`
`- 380/23
`4,794,644 12/1988 Philip etal. ..
`
`1/1989 Hann et al...
`esessesssenceres 380/25
`4,799,153
`1/1989 Vaughan .......cssesecsereeeres 380/23
`4,800,590
`
`. 380/49
`4,802,220
`1/1989 Marker,Jr.
`3/1989 Shimizu oo...eesesseenesteeeeere 370/60
`4,815,071
`
`OTHER PUBLICATIONS
`
`Data Communication Networks Interfaces, CCITT
`“Red Book”,
`(Rec. X.20-X.32), vol. VII, Fascicle
`VIIL3, VIlIth Plenary Assembly, Oct. 8-19, 1984,
`Malaga-Torremolinos, pp. 108-243.
`J. S. Quartermanetal., “Notable Computer Networks”,
`Communications of the ACM, vol. 29, No. 10, Oct. 1986,
`pp. 932-971.
`“Metropolitan Area Network Generic Framework Sys-
`
`tems Requirements in Support of Switched Multi-
`-Megabit Data Service”, Technical Advisory TA-T-
`SY-000772, Bell Communications Research,Inc., issue
`1, Feb. 1988, pp. 1-1-12-1.
`
`Primary Examiner—Salvatore Cangialosi
`Attorney, Agent, or Firm—Werner Ulrich
`
`ABSTRACT
`[57]
`A high capacity metropolitan area network (MAN) is
`described. Data traffic from users is connected to data
`concentrators:at the edge of the network, and is trans-
`mitted over fiber optic data links to a hub where the
`data is switched. The hub includes a plurality of data
`switching modules, each having a control means, and
`each connected to a distributed control space division
`switch. Advantageously, the data switching modules,
`whose inputs are connected to the concentrators, per-
`form all checking and routing functions, while the
`1024 1024 maximum size space division switch, whose
`outputs are connected to the concentrators, provides a
`large fan-out distribution network for reaching many
`concentrators from each data switching module. Dis-
`tributed control of the space division switch permits
`several million connection and disconnection actions to
`be performed each second, while the pipelined and
`parallel operation within the control means permits
`each of the 256 switching modules to process at least
`50,000 transactions per second. The data switching
`modules chain groups of incoming packets destined for
`a common outlet of the space division switch so that
`only one connection in that switch is required for trans-
`mitting each group of chained packets from a data
`switching module to a concentrator. MAN provides
`security features including a port identification supplied
`by the data concentrators, and a check that each packet
`is from an authorized source user, transmitting on a port
`associated with that user, to an authorized destination
`user that is in the same group (virtual network) as the
`source user.
`
`8 Claims, 25 DrawingSheets
`
`USER/GROUP
`
`AUTHORIZATIONTABLE
`
`
`
` To
`
`
`TASLES
`
`Ta
`RINT
`
`To
`
`MINT
`
`To
`MINT
`
`TO
`PINT
`
`1
`
`SAMSUNG 1073
`SAMSUNG 1073
`SAMSUNG v. SMART MOBILE
`SAMSUNG v. SMART MOBILE
`IPR2022-01004
`IPR2022-01004
`
`1
`
`

`

`US. Patent
`
`Jan.30, 1990
`
`Sheet 10f25
`
`4,897,874
`
`-SECONDS
`
`NEEDEDRESPONSETIME
`
`
`
`
`
`gc]
`
`
`
`COMPUTER
`GRAPHICS
`TILLS
`
`
`Hoy
`
`102
`
`109
`
`10
`10>
`104
`TRANSACTION SIZE - BITS
`
`107
`
`198
`
`COMPUTER NETWORKING NEEDS
`
`FIG.
`
`1
`
`2
`
`

`

`US. Patent
`
`Jan. 30, 1990
`
`Sheet 20f25
`
`4,897,874
`
`.
`
`Tr
`
`(]
`
`a
`7
`|i
`Kt
`
`|
`
`cta 3.HE
`
`N
`
`1200
`
`SWITCH
`
`x<
`
`o
`“es
`ig
`
`29
`
`on
`o
`mm:
`20
`I
`+
`
`g
`
`©
`
`x
`a
`
`N
`|
`
`x
`=
`z
`
`o
`
`N
`
`“
`
`l>
`
`<=
`
`3NIM |
`|<|—SSaer2
`FIG.2
`
`
`
`
`aw
`wi ol
`J1>
`
`= i
`
`h
`
`w
`
`rT
`
`(
`
`x
`z
`
`x
`z
`
`TF
`2
`
`8b] 2
`FILESERVER
`
`<r
`\
`
`XN
`
`
`
`3
`
`

`

`US. Patent
`
`Jan. 30, 1990
`
`Wrel||V1[WINaINIW
`eanoToniHHZIONLININGCral
`
`z_TIFT]8H|
`
`9zSNVH
`
`4,897,874
`
`(1-914)
`
`(21°914)
`
`Ls
`
`-
`
`Sheet 3 of 25
`
`977::WIN(O1’9IS)
`nket
`yUti|ZZleeantZlzisintwi
`a[|
`
`N.
`
`LANIW
`
`nN(91‘9otd)—cre-
`
`
`
`(Z'914)
`
`4
`
`

`

`US. Patent
`
`Jan.30, 1990
`
`Sheet 40f25
`
`4,897,874
`
` CONTROL
`
`=PINT ahiDtt
`
`fee te
`
`rh m OD © cp oO Cpo~
`
`ATA FABRIC
`
`MANS
`
`FIG.4
`
`1
`
`UIM
`
`13
`
`(UPTO20)
`
`13
`
`97
`
`RECEIVE
`
`CONTROL
`
`5
`
`

`

`Sheet 50f25
`
`4,897,874
`
`US. Patent
`
`Jan. 30, 1990
`
`FIG.5
`
`6
`
`

`

`US. Patent
`
`Jan. 30, 1990
`
`INLETS
`
`Sheet 60f25
`
`4,897,874
`
`
`OUTLETS
`
`Lz|
`
`FIG. 6
`
`7
`
`

`

`
`
`US. Patent—Jan. 30, 1990 Sheet 70f25 4,897,874
`
`
`
`PASC L-—=
`-
`-
`re
`:
`1s
`25
`:
`
`(32)|cuitcy switcn|6! 8)
`4s
`:
`+
`
`1s¢ xpc|
`
`«7
`
`|25c xpc
`
`21
`
`DATA NETWORK
`
`121
`
`123
`
`290
`
`1227:
`(64)
`.
`
`rat
`
`1247,
`
`=
`(64)
`.
`
`1
`
`t
`
`+
`-
`+2
`[|
`:
`
`(32)|_[5 2s|C6)
`—liscwo] fase)
`“|
`SWITCH
`SWITCH
`--befpasth =
`|
`=
`|
`Ui
`(FIG.25)
`a
`_
`ILs
`7
`
`
`(4)|MINT REQ 196 ~ 130
`
`
`ACK ee '3'~Veac]|139
`~-
`132
`140
`Wa Sa)
`1)
`
`
`
`
`(256)
`Ibs
`
`:
`
`“tT
`
`(4)
`
`ce
`
`RE
`CONTROL MSG
`
`NETWORK
`
`|
`
`eo||
`
`|
`
`CONTROL
`22
`
`8
`
`

`

`US. Patent
`
`Jan. 30, 1990
`
`Sheet 8 of 25
`
`4,897,874
`
`'021| SQIS
`SOlAYdsS
`
`ێ
`l
`
`(6’914)
`
`()anano
`LOSNNOOSIG
`
`LATLNOSASVA1SY
`
`
`
`(A101yavW)
`
`SyVINI
`
`
`
`
`
`9Ol4
`
`SGIS
`
`SdnowoINIW&SWoudSLSanosY
`
`
`
`9s!bSI
`
`LOANNOSSIOyOLOANNOD
`
`LOANNOSS1d
`
`esl
`
`LOZINNOO
`
`
`
`
`
`MVNG_ONSSKSAGLan
`
`cSl
`
`Z31
`
`(6914)
`
`'|
`
`(9)ANSNO
`
`avnosy
`
`
`
`LATLNOAZIAS
`
`
`
`(ASNBWYyvHW)
`
`ON
`
`Yyv1n9esY
`
`anand
`
`VINA
`
`ast
`
`|
`99
`
`(a)anand
`
`ALIYOTad
`
`
`
`LAILANG3Z135S
`
`
`
`(ASNENYVW)
`
`091
`
`ON
`
`ALLYOLYd
`
`ANaANO
`
`TINA
`
`INIWOLLod
`
`MYNDONAS
`
`INIWOL
`
`LAMOVd
`
`9
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`

`

`US. Patent
`
`Jan. 30, 1990
`
`Sheet 9 of 25
`
`4,897,874
`
`
`
`
`
`LNIWOLINIWOLYYNA(ANGIyavu)
`
`
`
`
`
`OVONaSGNaS‘qayo07g-LATINO3sva13Y
`
`Z61eZ192!
`
`
`
`A9VLIS-1Sa14ASOOHS
`
`MNIVONYLSINI
`
`SNON
`
`
`
`
`
`SGISSOLAYMaS6‘OIA
`
`
`
`
`
`961S61/HOLH
`
`
`ONVNITSavONVYANIDVIvosdLOSANNOOSIGWNITGSW
`
`
`
`
`A1G1LAWISHOLOHDLAINIALLMOLYd
`
`NOT
`
`gol
`
`
`
`H9VLS-1SYI14ON3SS
`
`oS|OLYAGHO9dX
`
`GNVMNITsav
`
`ASNLSNI
`
`SXNIT&‘SLAINIZOlQIsoYNeS
`
`LYSANOS
`
`
`
`SOV1IS-ONOO3SGNAS
`
`
`
`oS@OlYAGHOIdx
`
`CNVSINTSYOLS
`
`
`
`SS9LOHDLAINI
`
`10
`
`10
`
`
`
`
`
`
`

`

`
`vival]0SSTONVHYNITTWNYSLXa|vivaVNUALNIQYSTONVHYNIT
`
`
`
`vival]©USTONWHYNITTWNUALNI€&YSTONVHNITTVWNYSLX3viva
`vivaZYSTGNVHNITTWNYSLXS||
`
`Viva);|1MSTONVHMNI7“IWNUALNI|YSTONVHNITWNYALXS
`
`(e191)(Zt914)viva
`
`
`7OULINODFviva
`
`
`
`
`
`TWLO'1N3O“IOYLNOD
`
`U.S. Patent
`
`Jan. 30, 1990
`
`Sheet 10 of 25
`
`4,897,874
`
`11
`
`Zi
`
`ZSEad
`
`Ol“9I4
`
`
`
`
`
`W8VOOlSNVWOL
`
`LYOdSNVYL
`
`
`
`
`
`“OYLNOD
`
`FOULNOO
`
`7ONINOD
`
`11
`
`11
`
`
`
`
`€
`
`

`

`U.S. Patent
`
`Jan. 30, 1990
`
`Sheet 11 of 25
`
`4,897,874
`
`£02
`
`02%———
`
`SSA00V99
`
`IZe
`
`CES
`
`b
`oS
`
`ESS
`
`AYOWSW
`SSS3YdGY
`SNLVLSTSANNVHSD
`
`
`g
`oS
`
`OULNODOVIC
`
`
`
`ysaLS1OSyYOUN
`
`MOYHSSyds5y
`
`Sé7~
`
`|
`
`SS3ydGy
`
`sssy00dv
`
`SS3yu00y
`
`sssyqdv
`
`SS3yuGGV
`
`
`
`
`
`ssauday|LNO |SSsyudgv|LNOyNno
`
`
`ll:9I4|
`“ano|INd|“aNd|sim|!
`
`“und|TAXZAil— INO|LXZN||||ssaeqav|LINO}“yNnD|IND}
`
`AND|LX3N|
`IND|LX3N’||||sSaudav|INO}
`€Hl7
`
`
`
`
`
`
` =z
`
`ax
`
`12
`
`12
`
`
`
`
`
`

`

`US. Patent
`
`Jan. 30, 1990
`
`Sheet 12 of 25
`
`4,897,874
`
`AVWNUSLXa
`
`
`
`
`
`9!“TENNYHOG343dSMO}
`
`
`
`_ANT)@SZ
`
`UanIGNVHSay
`
`SGLanovdZzONYtYaTaWVYOSad
`
`
`
`
`.odI47090.L0ud
`
`cl“OIA
`
`SLO
`
`HXOL
`
`YSAOVNVLH
`
`soe
`
`Wous/ot
`6lald
`
`|_|ONTY
`FOVAYSLNI
`
`TOYLNOS
`
`YAONANOAS
`
`SYSTONVH
`
`g92
`
`Y30VSH
`
`OsI4
`
`AaWVvadMINIT
`
`TOULNOD
`
`9573OL°1Ldo
`
`MOOVUNV
`
`AMAAODSY
`
`13
`
`13
`
`
`
`
`
`
`
`
`

`

`US. Patent
`
`Jan. 30, 1990
`
`Sheet 13 of 25
`
`4,897,874
`
`OL||os
`“dO
`YsaTEHVYOS
`o5Vd
`
`062
`
`862
`
`962
`
`
`
`TANNVHOG3S3adSMOT
`
`b6S
`
`OLuavS
`
`Zi
`
`avdovzGNV|Layovd|YSIGNVH
`
`(ez913)||NTTSUSIGNVHove||_|70901L0udOLS
`
`-98%FWNUSINI~
`
`
`~~cezGeeSOVAYSINI!=|ONTY
`gezTSA31ZzYNIT
`
`|VLVG||SNVW|iz7
`€l“O14
`ANTTYyOSS300Ud
`SOVAYMSLNI
`f—..w">
`
`SS3yq0v“JOULNOSD
`OslSYSONanNodAs
`
`ANIWOL
`
`“WYLN3S
`
`“TOYLNOD
`
`02
`
`paz
`
`Sec
`
`/OL
`
`Wows
`
`yLG
`
`6t
`
`14
`
`14
`
`€
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 30, 1990
`
`Sheet 14 of 25
`
`4,897,874
`
`\o1e4—\eue*tOle
`_— B0€
`
`
`
`pea3OWNVLI
`
`
`
`dnowo‘SWVN|:10d
`
`AYOWAW
`
`HOLIMS
`
`TOYULNOD
`
`gel‘9el
`
`
`
`TOYLNOSdN-L3s
`
`HOLIMS
`
`HII
`
`Zt
`
`WIN
`
`SNANO
`
`dsoVNV
`
`LNIW
`
`W8VO
`
`
`
`YOLINOW
`
`W8VO
`
`“WYLNAS
`
`“JOULNOD
`
`cSE
`
`15
`
`
`
`
`
`TOYLNOD“WHINSSLINIW
`
`15
`
`
`
`
`
`

`

`US. Patent
`
`Jan. 30, 1990
`
`Sheet 15 of 25
`
`4,897,874
`
`SIC’bIE€Sec9€"(SE
`
`dN0y9/xyasn
`
`SIAVLNOLLYZTYOHLAV
`
`o9€
`
`
`
`
`
`saravlALITIEVvdv9
`
`dasn
`
`ISe
`
`W8vO
`
`WALSAS
`
`
`
`Gl‘Olds
`
`16
`
`W8VvO
`
`WYLN3D
`
`“TOULNOD
`
`W8vO
`
`“WYLNAD
`
`“OULNOD
`
`W8VO
`
`TWHYLNSAOD
`
`“TOYULNOD
`
`ol
`
`OL
`
`LNIW
`
`LNIW
`
`OLOL
`olOL
`
`ANIWLNIW
`LINIWANIW
`
`ee ee ee ee ey ey ee”
`
`16
`
`
`
`
`
`
`
`

`

`US. Patent
`
`Jan. 30, 1990
`
`Sheet 16 of 25
`
`4,897,874
`
`91“SIA
`
`ad3d0030
`
`
`
`SovSYSLNIISN
`
`OSI4
`
`Yy345N8
`
`“ONLUOd
`
`Nao17sna
`
`sngLIWSNVYL
`
`bor
`
`SNESATSO3y
`
`Y344N8
`
`O410b
`
`Obr
`
`SOVAYSINI1X
`
`
`
`96:Tbe
`
`orbbb
`
`YAYd/S
`
`wi},ooSois6
`
`
`
`SOVAYSLNI1SN3
`
`60+Olp
`
`Ysd0030saluLWXA
`
`“ONLYOd
`
`Nao|qsna
`
`17
`
`17
`
`
`
`

`

`Sheet 17 of 25
`
`4,897,874
`
`
`
`I
`
`ercop
`
`91LSV1A
`
`Y4345Ne
`
`YSONaNOAS
`
`WWAMOWAHW
`
`3Sb
`
`Zi“914
`
`|WSAWYd3assNeAOY|
`
`56
`
`US. Patent
`
`Jan. 30, 1990
`
`0ab
`
`
`
`bl}pepSl
`
`|
`
`O44
`
`SOVAYSLNI
`
`ONTSSA00Nd
`
`0S
`
`
`
`MYOMLAN(ob
`
`
`
`—_—SALS3034y34ine
`
`>ANTTYSaTIGNVHSOVAYSLNIons
`
`
`SngeneZSrsnaWouds
`
`Nv¥WANTI7OL
`
`18
`
`18
`
`
`
`
`

`

`US. Patent
`
`Jan. 30, 1990
`
`Sheet 18 of 25
`
`4,897,874
`
`30S
`
`quYvYOE~NO
`
`AYOWSW
`
`80S
`
`Ysa
`
`SNAWA
`
`IS
`
`VWd
`
`SOLARG
`
`Gl“OIA
`
`GxYuvVOE-NO
`
`Sng
`
`SYaLSVW
`
`19
`
`19
`
`
`
`
`

`

`US. Patent—Jan. 30, 1990
`4,897,874
`Sheet 19 of 25
`
`@
`
`Z
`
`=X
`uo
`rx
`
`=
`r
`ax
`a
`
`>O
`
`m)—
`
`“OIA
`
`9Z
`
`wn
`W
`
`>W
`
`El
`
`15
`
`0sS95S
`
`Ny TI
`N‘8
`
`Ni
`
`n
`
`SAN
`
`yasn
`
`y43asn
`
`__|MINI
`Wows|MINI
`
`
`O@S
`
`02S
`
`TIAN
`
`bes
`
`Odd
`
`_Nn
`eZS~4dd1L/dGan
`
`Eh
`
`sna|(tasews
`
`SAN
`
`Ody
`
`dol/dan
`
`[ai_
`
`YySaATYGa
`
`OL
`
`20
`
`20
`
`

`

`U.S. Patent
`
`Jan. 30, 1990
`
`Sheet 20 0f 25
`
`4,897,874
`
`MSB
`
`LSB
`
`NIM/MINT
`HEADER
`
`MAN
`HEADER
`
`624
`
`622
`
`SOURCE/DEST PORT (S)
`
`DESTINATION
`
`SOURCE
`
`™ PROTOCOL |
`GROUP
`
`PKT LENGTH
`
`GRP 1D
`
`SERVICE
`
`600
`
`612
`
`614
`
`616
`bs1a
`
`623
`
`r~610
`
`
`
`
`
`626[torcecesso
`
`HDR CHECK SEQ
`
`EUS TO EUS
`HEADER
`
`696
`
`[wepUWU LENGTH
`
`634
`
`—~ . PACKET
`
`PROTOCOL
`
`638
`
`INITIAL BYTE NO.
`
`sss
`
`INTERNAL
`EUS
`AND DATA
`
`42~ DSTPORT
`
`DATA
`DATA
`
`
`SRCPORT
`
`644
`
`
`
`
`
`|
`
`640
`
`eae
`
`DATA CHECK SEQ
`
`FIG. 20
`
`21
`
`21
`
`

`

`US. Patent
`
`Jan. 30, 1990
`
`Sheet 21 of 25
`
`4,897,874 ©
`
`Pitcittl
`
`
`oe888eweel
`
`YaTIONLNOS
`SSA00V
`oe
`
`OOll
`
`LNIW
`
`22
`
`22
`
`

`

`US. Patent
`
`Jan. 30, 1990
`
`Sheet 22 of 25
`
`4,897,874
`
`WIN
`
`
`LNdNIvivd
`Z1Z1
`SNHNW
`SNVW
`
`LNIW
`
`LANTWce
`
`LNIL
`
`avd
`
`HOLIMS
`
`W
`
`9
`
`dvd
`
`i
`
`cf“OlA
`
`6121
`
`“91d
`
`Xd
`
`23
`
`23
`
`
`

`

`US. Patent
`
`Jan. 30, 1990
`
`Sheet 23 of 25
`
`4,897,874
`
`DELAYLINE
`
`<E
`
`e<a Qu
`
`JZ6 ax — @
`
`SELECTOR
`
`DATALATCHES
`
`REFCLK
`
`1007
`
`CLEAR
`
`1001
`
`TAPPED
`
`
`
`UNALIGNED DATA
`
` REFCLK
`
`FIG.23
`
`24
`
`24
`
`

`

`US. Patent
`
`Jan. 30, 1990
`
`Sheet 24 of 25
`
`4,897,874
`
` iHOLIMS
`
`
`7\LAmMOVd*
`
`ciel
`
`Zlel
`
`&@WINWows
`
`25
`
`25
`
`
`
`

`

`US. Patent
`
`30rt
`
`
`
`daTIOYLNODHOLIMSNVW
`
`OLLanLn0
`
`562MACHOHOLIMS
`ane1u0d
`3OV1S-GNOO3SWAWSALVLS
`
`Jan. 30, 1990
`
`Sheet 25 of 25
`
`4,897,874
`
`
`
`YaGuOHOLIMS
`
` 1u0d|
`
`1u0dASNOdS3YOV
`
`AXOWAWHLVd
`
`S3OVLS-1SY14
`
`LOANNOOS1d
`
`anand
`
`dVWOILLVLS
`
`ALTYOLYd
`
`anand
`
`AYOWSWMNT
`
`AOLAYSS
`
`“JONLNOD
`
`yvInesd
`
`anand
`
`SXVINI
`
`TOYLNOD
`
`.LYOd
`
`LS3No03ag
`
`SAVINI
`
`26
`
`26
`
`
`
`
`
`
`
`
`
`
`
`

`

`1
`
`4,897,874
`
`rae 0
`
`15
`
`25
`
`30
`
`45
`
`METROPOLITAN AREA NETWORK
`ARRANGEMENT FOR SERVING VIRTUAL DATA
`NETWORKS
`
`CROSS-REFERENCE TO RELATED
`APPLICATIONS
`
`This application is related to the applicationsof:
`Jayant G. Hemmady, William P. Lidinsky, Robert K.
`Nichols, Gaylord W. Richards, Gary A. Roediger,
`Scott B. Steele, Ronald C. Weddige, and Bruce R. Zelle
`entitled “Architecture And Organization Of A High
`Performance Metropolitan Area Telecommunications
`Packet Network”;
`Gary A. Roediger entitled “Architecture Of The
`Control Of A High Performance Packet Switching
`Distribution Network”;
`William P. Lidinsky, Gary A. Roediger, Scott B.
`Steele, Ronald C. Weddige, and Bruce R. Zelle entitled
`“Identification And Authentication Of End User Sys-
`tems For Packet Communications Network Services”;
`Jayant G. Hemmady, William P. Lidinsky, Gary A.
`Roediger, Scott B. Steele, Ronald C. Weddige, and
`Bruce R. Zelle entitled “Packet Network Architecture
`For Providing Rapid Response Time”;
`William P. Lidinsky, Gary A. Roediger, Scott B.
`Steele, and Ronald C. Weddige entitled “User To Net-
`work Interface Protocol For Packet Communications
`Networks”;
`Robert K. Nichols and Bruce R. Zelle entitled “Syn-
`chronization Of Non-Continuous Digital Bit Streams”;
`Scott B. Steele entitled “High Bit Rate Telecommu-
`nications Packet Network Interface”;
`Jayant G. Hemmady, Michael J. Knudsen, William P.
`Lidinsky, Robert K. Nichols, Gaylord W. Richards,
`Gary A. Roediger, Scot B. Steele, Ronald C. Weddige,
`and Bruce R.Zelle entitled “Arrangement For Switch-
`ing Concentrated Telecommunications Packet Traffic”;
`Gaylord W. Richards entitled “Distributed Control
`Rapid Connection Circuit Switch”;
`Robert K. Nichols and Gary A. Roedigerentitled “A
`High Bandwidth Interleaved Buffer Memory and Con-
`trol”;
`Jayant G. Hemmady, Michael J. Knudsen, Robert K.
`Nichols, Gaylord W. Richards, and Gary A. Roediger
`entitled “Control Network For A Rapid Connection
`Circuit Switch”;
`Bruce R. Zelle entitled “Concurrent Resource Re-
`quest Resolution Mechanism”; and
`Jayant G. Hemmady, William P. Lidinsky, Scott B.
`Steele, Werner Ulrich, and Ronald C. Weddigeentitled
`“Integrated Packetized Voice And Data Switching
`System” which applicationsare assigned to the assignee
`of the present application, and are being filed concur-
`rently herewith.
`TECHNICAL FIELD
`
`This invention relates to data networks for serving a
`plurality of user groups.
`PROBLEM
`
`Large data networks for manyusers in, for example,
`a metropolitan area are called metropolitan area net-
`works. In order to make efficient use of such large
`networks, it is desirable to be able to offer the equiva-
`lent of private network service to each of a plurality of
`
`65
`
`2
`user groups. Such arrangements are called virtual net-
`works.
`A problem in the prior art is that it is difficult to
`ensure that users of one virtual network do not gain
`access to private data accessed by users of another vir-
`tual network. Even within one entity, such as a corpora-
`tion, a university or a government agency,it is fre-
`quencydesirable to restrict access to certain data such
`as payroll records. Prior art systems do not provide
`adequate protection from unauthorized access to virtual
`networks served by a common data network, because
`such networksutilize common media architectures and
`because they lack adequate per packet authentication.
`SOLUTION
`
`The above problems are solved and an advance is
`made over the prior art in accordance with the princi-
`ples of this invention wherein the source, destination,
`and user group of each data entity is checked in the
`network for proper authorization. In one embodiment,
`the network further prefixes a port identification to
`each data entry, such as a packet, so that the authoriza-
`tion check also checks to ensure that the entity is com-
`ing from a legitimate port, and that the portis the same
`port on which the user logged into the system. Advan-
`tageously, with such an arrangement, only a user having
`a login name and password which have been authorized
`to communicate with the destination group, and trans-
`mitting from a port for which such authority has been
`granted and on which a login has taken place, may
`communicate with a given destination group.
`In one embodiment,the user’s port is checked against
`a list of ports authorized for that user. Advantageously,
`such an arranged prevents an unauthorized user who
`“has fraudulently obtained a password from accessing a
`system from another port as if her were the legitimate
`user.
`In accordance with one embodimentofthe invention,
`when a user logs into the commoncarrier network, the
`user provides his own identification, a password and
`identification of the particular virtual private network
`to which that user wishes to have access during this
`session. The networkverifies the authorization of that
`user to access that private network. The authorization
`of a user may be for read only access, read and write
`access, or write only access and the commoncarrier
`networkwill subsequently screen out any unauthorized
`access requests. Subsequently, only data packets for
`authorized communications are transmitted to their
`destinations by the network. Advantageously, once the
`user’s authority has been established,all further check-
`ing on messages to and from that user are performed
`with a minimum of overhead in the network and virtu-
`ally no overhead at the end terminal.
`In accordance with one aspect of this invention, a
`common group: can also be defined. Users who have
`access to that common group can have network access
`to any other member of that common group. If the
`commongroup contains users having sensitive informa-
`tion, then further password procedures involving end
`terminals are required for accessing such information
`using common group facilities. Advantageously, such
`an arrangement permits simple connectivity through
`the network for routine administrative data messages.
`Advantageously, for users who do not need the special
`characteristics of a private virtual network, the services
`provided by the common user network are adequate.
`
`27
`
`

`

`3
`GENERAL DESCRIPTION
`
`4,897,874
`
`The Detailed Description of this specification is a
`description of an exemplary metropolitan area network
`(MAN)that incorporates the present invention. Such a
`network as shown in FIGS. 2 and 3 includes an outer
`ring of network interface modules (NIMs) 2 connected
`by fiber optic links 3 to a hub 1. The hub interconnects
`data and voice packets from any of the NIMsto any
`other NIM. The NIMs,in turn, are connectedviainter-
`face modules to user devices connected to the network.
`A MANofthe type described in the Detailed De-
`scription is capable of serving a large numberof cus-
`tomers. To take advantage of these capabilities, such a
`networkis likely to serve a numberofvirtual networks,
`each of which may, for example, be dedicated to a dif-
`ferent business entity. Under such circumstances, it is
`important
`that the privacy between different virtual
`networks be carefully protected by ensuring that no
`user not a member of a particular virtual network has
`access to data files of that virtual network. In accor-
`dance with the principles of this invention, this is ac-
`complished by identifying the source port for each
`packet that is switched through the MAN network in 9
`order to ensure that only ports associated with a virtual
`network can access other ports of that network.
`The invention claimed herein concerns the arrange-
`ments for providing virtual network service to groups
`of users. The arrangement is implemented largely by
`using the authorization data 360 and entering data into
`source checker tables 308 and routing tables 310 in the
`MINTcentral control 20 (FIG.14). Section 10 is specif-
`ically devoted to virtual network implementation and
`section 9 describes the protocol.
`BRIEF DESCRIPTION OF THE DRAWING
`
`35
`
`FIG.1 is a graphic representation of the characteris-
`tics of the type of communicationstraffic in a metropol-
`itan area network.
`FIG.2 is a high level block diagram of an exemplary
`metropolitan area network (referred to herein as MAN)
`including typical input user stations that communicate
`via such a network.
`FIG.3 is a more detailed block diagram of the hub of
`MANand the units communicating with that hub.
`FIGS. 4 and 5 are block diagrams of MANillustrat-
`ing how data flows from input user systems to the hub
`of MANand backto output user systems.
`FIG.6 is a simplified illustrative example of a type of
`network which can be used as a circuit switch in the
`hub of MAN.
`
`FIG.7 is a block diagram ofan illustrative embodi-
`ment of a MANcircuit switch and its associated control
`network.
`FIGS.8 and 9 are flowcharts representing the flow of
`requests from the data distribution stage of the hub to
`the controllers of the circuit switch of the hub.
`FIG.10 is a block diagram of one data distribution
`switch of a hub.
`FIGS. 11-14 are block diagrams and data layouts of
`portions of the data distribution switch of the hub.
`FIG. 15 is a block diagram of an operation, adminis-
`tration, and maintenance (OA&M) system for control-
`ling the data distribution stage of the hub.
`FIG.16 is a block diagram ofan interface module for
`interfacing between end user systems and the hub.
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`FIG. 17 is a block diagram of an arrangement for
`interfacing between an end user system and a network
`interface.
`FIG.18 is a block diagram of a typical end user sys-
`tem.
`
`FIG. 19 is a block diagram of a control arrangement
`for interfacing between an end user system and the hub
`of MAN.
`FIG. 20 is a layout of a data packet arranged for
`transmission through MANillustrating the MAN pro-
`tocol.
`FIG.21illustrates an alternate arrangement for con-
`trolling access from the data distribution switchesto the
`circuit switch control.
`FIG. 22 is a block diagram illustrating arrangements
`for using MANto switch voice as well as data.
`FIG.23illustrates an arrangement for synchronizing
`data received from the circuit switch by one of the data
`distribution switches.
`FIG. 24 illustrates an alternate arrangement for the
`hub for switching packetized voice and data.
`FIG.25 is a block diagram of a MANcircuit switch
`controller.
`
`DETAILED DESCRIPTION
`1, INTRODUCTION
`Data networks often are classified by their size and
`scope of ownership. Local area network (LANs) are
`usually ownedby a single organization and havea reach
`of a few kilometers. They interconnect tens to hundreds
`of terminals, computers, and other end user systems
`(EUSs). At the other extreme are wide area networks
`(WANs) spanning continents, owned by commoncarri-
`ers, and interconnecting tens of thousands of EUSs.
`Between these extremes other data networks have been
`identified whose scope ranges from a campusto a met-
`ropolitan area. The high performance metropolitan area
`network to be described herein will be referred to as
`MAN.A table of acronyms and abbreviations is found
`in Appendix A.
`Metropolitan area networks serve a variety of EUSs
`ranging from simple reporting devices and low intelli-
`gence terminals through personal computers to large
`mainframes and supercomputers. The demands that
`these EUSs place on a network vary widely. Some may
`issue messages infrequently while others may issue
`many messages each second. Some messages may be
`only a few bytes while others maybe files of millions of
`bytes. Some EUSs may require delivery any time within
`the next few hours while others may require delivery
`within microseconds.
`This invention of a metropolitan area network is a
`computer and telephone communications networkthat
`has been designed for transmitting broadband low la-
`tency data which retains and indeed exceeds the perfor-
`mance characteristics of the highest performancelocal
`area networks. A metropolitan area network has size
`characteristics similar to those of a class § or end-office
`telephone central office; consequently, with respect to
`size a metropolitan area network can be thoughtof as an
`end-office for data. The exemplary embodiment of the
`invention, hereinafter called MAN, was designed with
`this in mind. However, MANalso fits well either as an
`adjunct to or as part of a switch module for an end-
`office, thus supporting broadband Integrated Services
`Digital Network (ISDN) services. MAN can also be
`effective as either a local area or campus area network.
`
`28
`
`28
`
`

`

`= 0
`
`40
`
`45
`
`5
`It is able to grow gracefully from a small LAN through
`campussized networks to a full MAN.
`The rapid proliferation of workstations and their
`servers, and the growth of distributed computing are
`major factors that motivated the design of this inven-
`tion. MAN was designed to provide networking for
`tens of thousands of diskless workstations and servers
`and other computers over tens of kilometers, where
`each user has tens to hundreds of simultaneous and
`different associations with other computers on the net-
`work. Each networked computer can concurrently
`generate tens to hundreds of messages per second, and
`require I/O rates of tens to hundreds of millions of
`bits/second (Mbps). Message sizes may range from
`hundredsofbits to millions of bits. With this level of
`performance, MAN is capable of supporting remote
`procedure calls,
`interobject communications, remote
`demand paging, remote swapping,
`file transfer, and
`computer graphics. The goal is to move most messages
`(or transactions as they will be referred to henceforth)
`from an EUS memoryto another EUS memory within
`less than a millisecond for small transaction and within
`a few millisecondsfor large transactions. FIG.1 classi-
`fies transaction types and show desired EUS response
`times as a function of both transaction type and size,
`simple (i.e., low intelligence) terminals 70, remote pro-
`cedure calls (RPCs) and interobject communications
`(IOCs) 72, demand paging 74, memory swapping 76,
`animated computer graphics 78, computer graphicsstill
`pictures 80, file transfers 82, and packetized voice 84.
`Meeting the response time/transaction speeds of FIG. 1
`represents part of the goals of the MAN network. As a
`calibration, lines of constant bit rate are shown where
`the bit rate is likely to dominate the response time.
`MANhasan aggregate bit rate of 150 gigabits per sec-
`ond and can handle:20 million network transactions per
`second with the exemplary choice of the processor
`elements shown in FIG. 14. Furthermore, it has been
`designed to handle traffic overloads gracefully.
`MANis a network which performs switching and
`routing as many systemsdo, but also addresses a myriad
`of other necessary functions such as error handling, user
`interfacing, and the like. Significant privacy and secu-
`rity features in MANare provided by an authentication
`capability. This capability prevents unauthorized net-
`work use, enables usage-sensitive billing, and provides
`non-forgeable source identification for all information.
`Capability also exists for defining virtual private net-
`works.
`MANis a transaction-oriented (ie., connectionless)
`network. It does not need to incur the overhead of
`establishing or maintaining connections although a con-
`nection veneer can be added in a straightforward fash-
`ion if desired.
`/
`MAN can also be used for switching packetized
`voice. Because of the short delay in traversing the net-
`work, the priority which may be given to the transmis-
`sion of single packet entities, and the low variation of
`delay when the network is not heavily loaded, voice or
`a mixture of voice and data can be readily supported by
`MAN.Forclarity, the term data as used hereinafter
`includes digital data representing voice signals, as well
`as digital data representing commands, numerical data,
`graphics, programs, data files and other contents of
`memory.
`though not yet completely built, has been
`MAN,
`extensively simulated. Many of the capacity estimates
`presented hereinafter are based on these simulations.
`
`4,897,874
`6
`2. ARCHITECTURE AND OPERATION
`2.1. Architecture
`The MANnetworkis a hierarchical star architecture
`with two or three levels depending upon howclosely
`one looksat the topology. FIG. 2 showsthe network as
`consisting of a switching center called a hub 1 linked to
`network interface modules 2 (NIMs) at the edge of the
`network.
`The hub is a very high performancetransaction store-
`and-forward system that gracefully grows from a small
`four link system to something very large that is capable
`of handling over 20 million network transactions per
`second and that has an aggregatebit rate of 150 gigabits
`per second.
`Radiating out from the hub for distances of up to tens
`of kilometersare optical fibers (or alternative data chan-
`nels) called external
`links (XLs) (connect NIM to
`MINT), each capable of handling full duplex bit rates
`on the order of 150 megabits per second. An XL termi-
`nates in a NIM.
`A NIM,the outer edge of which delineates the edge
`of the network, acts as a concentrator/demultiplexer
`and also identifies network ports. It concentrates when
`moving information into the network and demultiplexes
`when moving information out of the network. Its pur-
`pose in concentrating/demultiplexing is to interface
`multiple end user systems 26 (EUSs) to the network in
`such a way as to use thelink efficiently and cost effec-
`tively. Up to 20 EUSs 26 can be supported by each NIM
`depending upon the EUSs networking needs. Examples
`of such EUSs are the increasingly common advanced
`function workstations 4 where the burst rates are al-
`ready in the 10 Mbps range (with the expectation that
`much faster systems will soon be available) with aver-
`age rates orders of magnitude lower. If the EUS needs
`an average rate.that is closer to its burst rate and the
`averagerates are of the same order of magnitudeas that
`of a NIM,then a NIM caneither provide multiple inter-
`faces to a single EUS 26 or can provide a single inter-
`face with the entire NIM and XL dedicated to that
`EUS. Examples of EUSs of this type include large
`mainframes 5 andfile servers 6 for the above worksta-
`tions,
`local’ area networks such as ETHERNET ®) 8
`and high performance local area networks 7 such as
`Proteon @) 80, an 80 MBit token ring manufactured by
`Proteon Corp., or a system using a fiber distributed data
`interface (FDDI), an evolving American National Stan-
`dards Institute (ANSI) standard protocolring interface.
`In the latter two cases, the LANitself may do the con-
`centration and the NIM then degenerates to a single
`port network interface module. Lower performance
`local area networks such as ETHERNET8 and IBM
`token rings may not need all of the capability that an
`entire NIM provides. In these cases, the LAN, even
`though it concentrates, may connect to a port 8 on a
`multiport NIM.
`Within each EUSthere is a user interface module
`(UIM)13. This unit serves as a high bit rate direct mem-
`ory access port for the EUSandas a buffer for transac-
`tions received from the network. It also off-loads the
`EUS from MANinterface protocol concerns. Closely
`associated with the UIM is the MAN EUS-resident
`driver. It works with the UIM to format outgoing trans-
`actions, receive incoming transactions, implement pro-
`tocols, and interface with the EUSs operating system.
`A closer inspection (see FIG. 3) of the hub reveals
`two different functional units—a MAN switch (MANS)
`10 and one or more memory interface modules 11
`
`35
`
`65
`
`29
`
`29
`
`

`

`15
`
`2oO
`
`4,897,874
`
`7
`(MINTs). Each MINTis connected to up to four NIMs
`via XLs 3 and thus can accommodate up to 80 EUSs.
`The choice of four NIMs per MINT is based upon a
`numberoffactors including transaction handling capac-
`ity, buffer memory size within the MINT, growability
`of the network, failure group size, and aggregate bit
`rate.
`
`8
`circuit board for most applications. The UIM 13 con-
`nects to the NIM 2 over a duplex optical fiber link
`called the EUS link 14 (EUSL), driven by optical trans-
`mitter 97 and 85. This link runs at the same speed as the
`external link (XL) 3. The UIM has a memory queue 15
`used to store information on its way to the network.
`Packets and SUWUsare stored and forwarded to the
`Each MINTis connected to the MANSbyfourinter-
`NIM using out-of-band flow control.
`nal links 12 (Ls) (connect MINT and MAN switch)
`By way of contrast, a receive buffer memory 90 must
`exist to receive information from the network. In this
`one of which is shown for each of the MINTsin FIG.
`3. The reason for four linksin this case is different than
`case entire EUStransactions may sometimes be stored
`until
`they can be transferred into End User System
`it is for the XLs. Here multiple links are necessary be-
`cause the MINT will normally be sending information
`memory. The receive buffer must be capable of dy-
`namic buffer chaining. Partial EUS transactions may
`through the MANSto multiple destinations concur-
`rently; a single IL would present a bottleneck. The
`arrive concurrently in an interleaved fashion.
`Optical Receiver 87 receives signals from optical link
`choice of 4 ILs (as well as many other design choices of
`a similar nature) was made on the basis of extensive
`14 for storage in receive buffer memory 90. Control 25
`analytical and simulation modeling. The ILs run at the
`controls UIM 13, and controls exchange of data be-
`same bit rate as the external links but are very short
`tween transmit first-in-first-out (FIFO) queue 15 or
`since the entire hub is colocated.
`receive buffer memory 90 and a businterface for inter-
`The smallest hub consists of one MINT with the ILs
`facing with bus 92 which