United States Patent (19)
`Hardwick et al.
`
`|||||I||
`US005550816A
`5,550,816
`11
`Patent Number:
`Aug. 27, 1996
`45) Date of Patent:
`
`(54) METHOD AND APPARATUS FOR VIRTUAL
`SWITCHING
`
`(75) inventors: Ken Hardwick, Sherwood, Oreg.;
`Geoffrey C. Stone, Minneapolis, Minn.
`73) Assignee: Storage Technology Corporation,
`Lousville, Colo.
`
`(21) Appl. No.: 366,227
`22 Filed:
`Dec. 29, 1994
`(51) Int. Cl. ............................. H04L 12156; G06F 13/00
`52 U.S. Cl. ........................ 370/60; 370/85.13; 370/94.1;
`395/650; 395/800; 395/200.02
`(58) Field of Search .................................. 370/58.1, 58.2,
`370/58.3, 60, 60.1, 61, 79, 85.13, 85.14,
`94.1, 94.2, 94.3; 395/200, 325, 375, 650,
`800, 500
`
`56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`4,218,756 8/1980 Fraser ..................................... 370/94.1
`5,119,369 6/1992 Tanabe et al. ............................ 370/60
`5,249,292 9/1993 Chiappa .
`... 395/650
`5,278,834
`1/1994 Mazzola ......
`370/941
`5,280,476 1/1994 Kojima et al. ......................... 370/60.1
`
`
`
`5/1994 Bixby et al. ......................... 370/85.13
`5,317,568
`5,321,692 6/1994 Wallmeier ................................. 370/60
`5,430,727 7/1995 Callon .................................. 370/85.13
`Primary Examiner-Alpus H. Hsu
`Attorney, Agent, or Firm-Timothy R. Schulte
`57
`ABSTRACT
`A physical switching device for use in a communication
`network to switch Open Systems Interconnection (OSI)
`network layer packets and method of use therefor is pro
`vided. The physical switching device includes at least a first
`and a second virtual switch. Each virtual switch includes a
`decision mechanism for determining an associated directive
`based on a destination identifier within a particular packet
`received at a data port. A processor is coupled to each virtual
`switch to insert the particular packet into an outgoing data
`stream on another data port to deliver the packet. Both data
`ports are associated with a plurality of data interfaces in the
`physical Switching device. A management apparatus is
`coupled to each virtual switch to maintain information on an
`association between the plurality of data interfaces and the
`virtual switches. The management apparatus limits each
`processor to only inserting the particular packet on another
`data port associated with the same virtual switch which
`received the particular packet.
`
`57 Claims, 35 Drawing Sheets
`
`
`
`O s
`DN
`PROCESSOR
`
`Ex.1008
`APPLE INC. / Page 1 of 65
`
`

`

`U.S. Patent
`
`Aug. 27, 1996
`
`Sheet 1 of 35
`
`5,550,816
`
`O
`O
`
`HD
`
`O
`O (1) CO CO
`SU
`S. sy
`
`CN
`O
`
`
`
`s
`SEC
`
`SE2.
`--- L ra
`
`
`
`--
`/
`
`8-
`
`Niyi ?is ?h
`t
`INS
`1N amas 5 (it
`3
`3
`
`Ex.1008
`APPLE INC. / Page 2 of 65
`
`

`

`U.S. Patent
`
`Aug. 27, 1996
`
`Sheet 2 of 35
`
`5,550,816
`
`
`
`Ex.1008
`APPLE INC. / Page 3 of 65
`
`

`

`U.S. Patent
`
`Aug. 27, 1996
`
`Sheet 3 of 35
`
`5,550,816
`
`90 || O_L
`
`No. Owl
`
`Gr?va}++)-LINEGI
`
`OZ | O ||
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`HEH LTI-J
`
`Ex.1008
`APPLE INC. / Page 4 of 65
`
`

`

`U.S. Patent
`
`Aug. 27, 1996
`
`Sheet 4 of 35
`
`5,550,816
`
`- 200
`
`STAR
`
`MANTAN DATABASE OF
`DESTINATION IDENTIFIERS
`
`LIMIT ACCESS TO DATABASE
`BY VRTUAL CLOSED USER
`GROUPS
`
`ASSIGN NCOMING TRAFFIC
`TO AVIRTUAL CLOSED USER
`GROUP BASED ON AN
`ACCESS POLICY
`
`
`
`
`
`2O2
`
`2O4
`
`2O6
`
`
`
`
`
`
`
`EXAM AND MODIFY
`PROTOCOL DATA UNIT
`FROM FIRST VIRTUAL
`CLOSED USER GROUP
`
`
`
`
`
`
`
`
`
`
`
`2O
`
`
`
`
`
`
`
`
`
`
`
`212
`
`VERIFY DESTINATION
`DENT FER IS REACHABLE
`FOR THE PROTOCOL DATA
`UNIT FROM FIRST VIRTUAL
`CLOSED USER GROUP
`
`ADD DESTINATION
`DENTIFER FOR NEWLY
`ATACHED DEVICE TO THE
`DAABASE
`
`
`
`
`
`EXAMAND MODIFY
`PROTOCOL DATA UNIT
`FROM SECOND VIRTUAL
`CLOSED USER GROUP
`
`
`
`VERIFY DESTINATION
`DENT FERS REACHABLE
`FOR THE PROTOCOL DATA
`UN N SECONO VRTUAL
`CLOSED USER GROUP
`
`ADO DESTINATION
`DENTFER FOR NEWLY
`AACHED DEVICE TO THE
`DATABASE
`
`O'
`
`22
`
`DELIVER PROTOCOL DATA
`UNIT FROM FIRST CLOSED
`USER GROUP
`
`
`
`DELVER PROTOCODATA
`UNT OF SECOND CLOSED
`USER GROUP
`
`24
`
`24'
`
`28
`
`END
`
`F.G. 6
`
`Ex.1008
`APPLE INC. / Page 5 of 65
`
`

`

`
`
`Ex.1008
`APPLE INC. / Page 6 of 65
`
`

`

`U.S. Patent
`
`Aug. 27, 1996
`
`Sheet 6 of 35
`
`5,550,816
`
`
`
`Ex.1008
`APPLE INC. / Page 7 of 65
`
`

`

`U.S. Patent
`
`Aug. 27, 1996
`
`Sheet 7 of 35
`
`5,550,816
`
`FIG.11
`
`
`
`C)224-
`
`Ex.1008
`APPLE INC. / Page 8 of 65
`
`

`

`U.S. Patent
`
`Aug. 27, 1996
`
`Sheet 8 of 35
`
`5,550,816
`
`
`
`
`
`Ex.1008
`APPLE INC. / Page 9 of 65
`
`

`

`U.S. Patent
`
`Aug. 27, 1996
`
`Sheet 9 of 35
`
`5,550,816
`
`
`
`:
`
`:
`
`c
`
`Ex.1008
`APPLE INC. / Page 10 of 65
`
`

`

`5,550,816
`
`
`
`FIG.14
`
`Ex.1008
`APPLE INC. / Page 11 of 65
`
`

`

`U.S. Patent
`
`Aug. 27, 1996
`
`Sheet 11 of 35
`
`5,550,816
`
`
`
`''''''''''''''--
`
`X, 10 || 'f7'9?7 ||
`
`– – – – – – – – – – – – – – – –) –
`
`|x£vori|
`
`| |
`
`|
`
`Ex.1008
`APPLE INC. / Page 12 of 65
`
`

`

`U.S. Patent
`
`Aug. 27, 1996
`
`Sheet 12 of 35
`
`5,550,816
`
`
`
`
`
`
`
`
`
`
`
`
`
`II
`
`Iy UNI
`
`
`
`
`
`
`
`
`
`C.
`C.
`C.
`NS Vitos
`--
`Q
`2 OO
`
`X
`CN ro
`st (i.
`co co
`N. N.
`
`-
`w
`CO
`N.
`
`Ex.1008
`APPLE INC. / Page 13 of 65
`
`

`

`
`
`=~ mmr = Sw
`- rr sw
`WM WW BA
`oT
`
`Ex.1008
`APPLE INC. / Page 14 of 65
`
`

`

`U.S. Patent
`
`Aug. 27, 1996
`
`Sheet 14 of 35
`
`5,550,816
`
`CASROOT
`
`EPE PP/1
`
`PP/2
`
`AppleTalk
`
`PP13
`
`DECnet
`
`PP/4
`
`AppleTalk PPort APPort EAppleTalk Port
`
`AppleTalk Port
`
`DECnetPOrt
`
`Frame Relay,
`SMOS or X.25
`
`
`
`VCP or PPP
`
`CASROOT
`
`aa-as
`
`on CAS Linkage
`
`umd
`
`move as . An
`
`Components covered by this FS
`-o- Subcomponent El
`Components NOT covered by this FS
`
`F.G. 18
`
`Ex.1008
`APPLE INC. / Page 15 of 65
`
`

`

`U.S. Patent
`
`Aug. 27, 1996
`
`Sheet 15 of 35
`
`5,550,816
`
`CASROOT
`
`Virtual Router? String (max: 16 VRs)
`
`ProtocolPort/String (max: 256 PPs)
`pPort
`DecnetPOrt
`pxPort
`AppletalkPort
`BridgePort
`
`ClusterBridge
`
`Bridging
`p
`
`Decnet
`pX
`Appletalk
`MemoryManagement
`Snmp
`
`PCf
`
`F.G. 19
`
`Ex.1008
`APPLE INC. / Page 16 of 65
`
`

`

`U.S. Patent
`
`Aug. 27, 1996
`
`Sheet 16 of 35
`
`5,550,816
`
`CASROOT
`
`PP/O
`
`PP/1
`
`PP/2
`
`PP/3
`
`BridgePort
`domain=0
`
`EBridgePort
`domain=0
`Epports
`
`BridgePort
`domain=
`Epports
`
`
`
`LAN
`Application
`
`ClusterBridge/O
`Application
`
`ClusterBridge/1
`Application
`
`BridgePort
`domain=
`
`LAN
`Application
`CASROOT
`
`empo am
`
`no us CAS Linkage
`
`P
`
`to
`
`Components covered by this FS
`-o- Subcomponent B Components NOT covered by this FS
`
`FG. 20
`
`Ex.1008
`APPLE INC. / Page 17 of 65
`
`

`

`U.S. Patent
`
`Aug. 27, 1996
`
`Sheet 17 of 35
`
`5,550,816
`
`CASROOT
`
`Appletalk
`
`PP/
`
`Appletalk
`
`PP12
`
`Decnet
`
`PP/3
`
`Eipports
`
`V
`
`\,
`
`V
`
`?
`
`f
`
`W
`
`Virtual link
`
`Elpports
`
`ago
`
`DecnetPort
`
`Oulum
`
`simi um CAS Linkage
`
`ow are up
`
`a
`
`Components covered by this FS
`-o- Subcomponent B
`Components NOT covered by this FS
`
`FG. 21
`
`Ex.1008
`APPLE INC. / Page 18 of 65
`
`

`

`U.S. Patent
`
`Aug. 27, 1996
`
`Sheet 18 of 35
`
`5,550,816
`
`
`
`CAS
`
`Virtual Router
`
`GCM
`
`LEGEND
`
`-- -D PEV Messages
`Virtual Router System Classes/Processes
`O Other Process
`
`Ex.1008
`APPLE INC. / Page 19 of 65
`
`

`

`U.S. Patent
`
`Aug. 27, 1996
`
`Sheet 19 of 35
`
`5,550,816
`
`CAS
`
`A1) CAS Create, and Provisioning messages
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`A5) Register VR Process ID
`
`
`
`A2) Create and Provisioning messages
`A4) ProvDOne
`A6) Protocol Registration
`
`Process
`(e.g., P)
`
`A3) ProvOone
`
`FG. 23
`
`B1) CAS Create, and Provisioning messages
`
`
`
`Media
`Application
`
`B3) Request for WR Process ID
`- - - -A5 - - -
`B4) WR Process ID
`
`B2) ProvDone B5) Media Registration
`
`- - Event. --> Event Dependency
`
`FG. 24
`
`Ex.1008
`APPLE INC. / Page 20 of 65
`
`

`

`U.S. Patent
`
`Aug. 27, 1996
`
`Sheet 20 of 35
`
`5,550,816
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`B5
`/ C1) Create Protocol Port
`
`Forwarding
`Agent
`
`C5) Register for if Entry space
`(if applicable)
`C4) Create Bind Table Manager
`
`
`
`
`
`C3) Create Protocol Port
`N
`C2) Call the Media FEHY
`Media ForwardingEventhandler
`C6) Update the Physical Port Info Structure
`
`- - Event. --> Event Dependency
`
`FG. 25
`
`Ex.1008
`APPLE INC. / Page 21 of 65
`
`

`

`U.S. Patent
`
`Aug. 27, 1996
`
`Sheet 21 of 35
`
`5,550,816
`
`
`
`
`
`
`
`
`
`D1) Media Availability
`- - - B5 - -
`
`
`
`
`
`D2) Bind Request
`
`Protocol
`Processes
`(e.g., IP)
`
`W
`/ D3) Bind Protocol Port
`
`
`
`
`
`
`
`
`
`
`
`
`
`Forwarding
`Agent
`
`D5) Register with LSM
`
`D6) Update the Bind Table Manager
`
`D5) Update the PP Forwarding Data
`
`N
`D4) Call the Protocol FEH
`Protocol ForwardingEventHandler
`
`FaprotocoPort
`
`- - Event. -o- Event Dependency
`
`FG. 26
`
`Ex.1008
`APPLE INC. / Page 22 of 65
`
`

`

`U.S. Patent
`
`Aug. 27, 1996
`
`Sheet 22 of 35
`
`5,550,816
`
`Dispatcher
`
`E1) Packet
`
`Source
`
`E2) Get pointer to inbound PP
`
`E3) Call DPO Method
`
`Forwarding
`Agent
`
`inbound Media OPO
`
`E4) Get Protocol Forwarding DPO from BTM
`
`E5) Call the Protocol DPO
`
`E7) Get outbound Media DPO
`E6) Local Cache Lookup
`
`Protocol Forwarding DPO
`
`Local Cache Manager
`
`BTM
`
`E8) Call Outbound Media DPO
`
`
`
`Outbound Media DPO
`
`E9) Transmit the Packet
`
`FIG. 27
`
`Ex.1008
`APPLE INC. / Page 23 of 65
`
`

`

`U.S. Patent
`
`Aug. 27, 1996
`
`Sheet 23 of 35
`
`5,550,816
`
`B1) CAS Create, and Provisioning messages
`
`
`
`Media
`Application
`
`B3) Request for WR Process ID
`- - - -A5 - - -
`B4) WR Process ID
`
`
`
`
`
`
`
`B2) ProvOOne B5) Media Registration (Set createProtocolPort Notification)
`
`- - Event. --> Event Dependency
`
`FG. 28
`
`Ex.1008
`APPLE INC. / Page 24 of 65
`
`

`

`U.S. Patent
`
`Aug. 27, 1996
`
`Sheet 24 of 35
`
`5,550,816
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`B5
`/ C1) Create Protocol Port
`
`Forwarding
`Agent
`
`C5) Register for if Entry space
`(if applicable)
`
`C4) Create Bind Table Manager
`
`
`
`C3) Create Protocol Port FaprotocoPort
`N
`C2) Call the Media FEH S
`Media ForwardingEventhandler
`C6) Update the Physical Port info Structure
`
`
`
`- - Event. -o- Event Dependency
`
`FG. 29
`
`Ex.1008
`APPLE INC. / Page 25 of 65
`
`

`

`U.S. Patent
`
`Aug. 27, 1996
`
`Sheet 25 of 35
`
`5,550,816
`
`
`
`
`
`D1) Media Availability
`- - - B5 - -
`
`
`
`
`
`D2) Bind Request
`
`Protocol
`Processes
`(e.g., iP)
`
`f
`/ D3) Bind Protocol Port
`
`
`
`Forwarding
`Agent
`
`D5) Register with LSM
`
`D6) Update the Bind Table Manager
`
`D5) Update the PP Forwarding Data
`
`FaprotoCOPort
`
`D4) Call the Protocol FEH
`Protocol ForwardingEventhandler
`
`- - Event. -o- Event Dependency
`
`F.G. 30
`
`Ex.1008
`APPLE INC. / Page 26 of 65
`
`

`

`U.S. Patent
`
`Aug. 27, 1996
`
`Sheet 26 of 35
`
`5,550,816
`
`Dispatcher
`
`E1) Packet
`
`Source
`
`E2) Get pointer to inbound PP
`
`E3) Call DPO Method
`
`Forwarding
`Agent
`
`inbound Media DPO
`
`FaP
`
`E4) Get Protocol Forwarding DPO from BTM
`
`
`
`E5) Call the Protocol DPO
`
`E7) Get outbound Media DPO
`E6) Local Cache Lookup
`
`
`
`Protocol Forwarding DPO
`
`TM
`
`Local Cache Manager
`E8) Call Outbound Media DPO
`
`Outbound Media DPO
`
`E9) Transmit the Packet
`
`FG. 31
`
`Ex.1008
`APPLE INC. / Page 27 of 65
`
`

`

`U.S. Patent
`
`Aug. 27, 1996
`
`Sheet 27 of 35
`
`5,550,816
`
`B1) CAS Create, and Provisioning messages
`
`
`
`
`
`
`
`B3) Request for WR Process ID
`- - - -A5 - - -
`Media
`Application B4) VR Process ID
`
`B2) ProvOone B5) Media Registration (Set bindProtocol Port Notification)
`
`- - Event. -o- Event Dependency
`
`FIG. 32
`
`Ex.1008
`APPLE INC. / Page 28 of 65
`
`

`

`U.S. Patent
`
`Aug. 27, 1996
`
`Sheet 28 of 35
`
`5,550,816
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`B5
`/ C1) Create Protocol Port
`
`Forwarding
`Agent
`
`C5) Register for if Entry space
`(if applicable)
`C4) Create Bind Table Manager
`
`
`
`
`
`C3) Create Protocol Port FaprotoCOPOrt
`N
`C2) Call the Media FEHQ
`Media ForwardingEventHandler
`C6) Update the Physical Port info Structure
`
`
`
`- - Event. -o- Event Dependency
`
`FG. 33
`
`Ex.1008
`APPLE INC. / Page 29 of 65
`
`

`

`U.S. Patent
`
`Aug. 27, 1996
`
`Sheet 29 of 35
`
`5,550,816
`
`
`
`
`
`
`
`D) Media Availability
`- - - B5 - -
`
`
`
`
`
`D2) Bind Request
`
`Protocol
`Processes
`(e.g., iP)
`
`/
`/ D3) Bind Protocol Port (The Bind Notification flag is set)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Forwarding
`Agent
`
`D5) Register with LSM
`
`D6) Update the Bind Table Manager
`
`D5) Update the PP Forwarding Data
`
`N
`D4) Call the Protocol FEH
`Protocol ForwardingEventhandler
`
`FaprotocoPOrt
`
`- - Event. -o- Event Dependency
`
`FG. 34
`
`Ex.1008
`APPLE INC. / Page 30 of 65
`
`

`

`U.S. Patent
`
`Aug. 27, 1996
`
`Sheet 30 of 35
`
`5,550,816
`
`Dispatcher
`
`E1) Packet
`
`Source
`
`E2) Get pointer to inbound PP
`
`E3) Call DPO Method
`
`Forwarding
`Agent
`
`Inbound Media DPO
`
`E4) Get Protocol Forwarding DPO from BTM
`
`E5) Call the Protocol DPO
`
`E7) Get outbound Media DPO
`E6) Local Cache Lookup
`
`Protocol Forwarding DPO
`
`Local Cache Manager
`
`BTM
`
`E8) Call Outbound Media DPO
`
`
`
`Outbound Media DPO
`
`
`
`E9) Transmit the Packet
`
`FG. 35
`
`Ex.1008
`APPLE INC. / Page 31 of 65
`
`

`

`U.S. Patent
`
`Aug. 27, 1996
`
`Sheet 31 of 35
`
`5,550,816
`
`Dispatcher
`
`E) Packet
`
`Source
`
`E2) Get pointer to inbound PP
`
`E3) Call DPO Method
`
`Forwarding
`Agent
`
`in bound Media DPO
`
`E4) Get Protocol Forwarding DPO from BTM
`
`E5) Call the Protocol DPO
`
`E7) Get outbound Media DPO
`E6) Local Cache Lookup
`
`Protocol Forwarding DPO
`
`Local Cache Manager
`
`E8) Call Outbound Media DPO
`
`
`
`
`
`Outbound Media DPO
`
`E9) Send the Packet to the appropriate LP
`
`FG. 36
`
`Ex.1008
`APPLE INC. / Page 32 of 65
`
`

`

`U.S. Patent
`
`Aug. 27, 1996
`
`Sheet 32 of 35
`
`5,550,816
`
`Dispatcher
`
`E10) Packe
`
`SOUrce
`
`E11) Get pointer to inbound PP
`
`E12) Call DPO Method
`
`Forwarding
`Agent
`
`Inbound Media DPO
`
`E13) Get Protocol Forwarding DPO from BTM
`
`E14) Call the Protocol DPO
`
`Protocol Forwarding DPO
`
`E16) Get outbound Media DPO
`E15) Local Cache Lookup
`
`FaPp
`
`Local Cache Manager
`
`E17) Call Outbound Media DPO
`
`
`
`Outbound Media DPO
`
`
`
`E18) Transmit the Packet
`
`FG. 37
`
`Ex.1008
`APPLE INC. / Page 33 of 65
`
`

`

`U.S. Patent
`
`Aug. 27, 1996
`
`Sheet 33 of 35
`
`5,550,816
`
`LP 1
`
`LCM - VR/O
`
`LCM - VR/
`
`A
`Cache
`lookup
`(VROI
`
`cache entry
`(outbound Port =
`WRio, PP?)
`
`A
`
`Cache
`lookup
`(VR/1)
`
`cache entry
`(outbound Port =
`VR/1, PP13)
`
`P Forwarder
`
`packet
`
`interface
`
`FIG 38
`
`Physical
`Interface
`
`LP 1
`
`LP2
`
`LCM - VR/O
`
`LCM - VR/
`
`A
`cache
`lookup
`(VR/O)
`
`cache entry
`(outbound Port =
`VR/O, PP/1)
`
`cache
`lookup
`(VR/1)
`
`cache entry
`(outbound Port =
`VR/1, PP/3)
`
`P Forwarder
`
`P Forwarder
`
`packet
`
`
`
`Virtual Link
`
`Physical
`Interface
`
`Physical
`Interface
`
`FG. 39
`
`Ex.1008
`APPLE INC. / Page 34 of 65
`
`

`

`U.S. Patent
`
`Aug. 27, 1996
`
`Sheet 34 of 35
`
`5,550,816
`
`LP
`
`LP2
`
`
`
`LCM - VR/1
`
`A
`cache
`lookup
`(VRIO)
`
`cache entry
`(outbound Port =
`VRO, PP/1)
`
`Cache
`lookup
`)
`(VR/1
`
`cache entry
`(outbound Port =
`VR/1, PP/3)
`
`P Forwarder
`
`P Forwarder
`
`
`
`Physical
`interface
`
`packet
`
`Virtual Link
`
`packet
`PP/2
`VR/
`
`LP3
`
`SBC Data Transfer
`
`V
`
`CM - VR/
`
`l
`
`OP Forwarde), I
`
`FIG. 40
`
`Physical
`Interface
`
`Ex.1008
`APPLE INC. / Page 35 of 65
`
`

`

`U.S. Patent
`
`Aug. 27, 1996
`
`Sheet 35 of 35
`
`5,550,816
`
`Dispatcher
`
`E) Packet
`
`Source
`
`E2) Get pointer to inbound PP
`
`E3) Call DPO Method
`
`Forwarding
`Agent
`
`Inbound Media DPO
`
`E4) Get Protocol Forwarding DPO from BTM
`
`E5) Call the Protocol DPO
`
`E7) Get outbound Media DPO
`E6) Local Cache Lookup
`
`
`
`Protocol Forwarding DPO
`
`Local Cache Manager
`
`E8) Call Outbound Media DPO
`
`
`
`Outbound Media DPO
`
`E9) Transmit the Packet
`
`F.G. 41
`
`Ex.1008
`APPLE INC. / Page 36 of 65
`
`

`

`1.
`METHOD AND APPARATUS FOR VIRTUAL
`SWITCHING
`
`5,550,816
`
`RELATED INVENTIONS
`The present invention is related to:
`Co-pending U.S. patent application Ser. No. 08/366,221,
`filed on Dec. 29, 1994, which is entitled "Method And
`Apparatus For Accelerated Packet Forwarding" by
`Mark Bakke et al.,
`Co-pending U.S. patent application Ser. No. 08/366,225,
`filed on Dec. 29, 1994, which is entitled "Method And
`Apparatus For Accelerated Packet Processing” by Geof
`Stone,
`Co-pending U.S. patent application Ser. No. 08/366.222,
`filed on Dec. 29, 1994, which is entitled "Method And
`Apparatus For Radix Decision Packet Processing” by
`Geof Stone,
`and which were all filed concurrently herewith and
`assigned to the assignee of the present invention.
`
`10
`
`15
`
`20
`
`FIELD OF THE INVENTION
`The present invention relates generally to data commu
`nication networks. More particularly, the present invention
`25
`relates to the operation of virtual switches within physical
`switching systems that direct the flow of protocol data units
`in the data communication networks.
`
`BACKGROUND OF THE INVENTION
`In a data communication network, a forwarding device
`(e.g., a data packet switch) directs protocol data units (e.g.,
`data packets) from one network node to another. These data
`packets may include voice, video, or data information as
`well as any combination thereof.
`To better understand how forwarding devices work within
`a data communication network, an analogy may be helpful.
`In many respects, data communication networks are similar
`to postal delivery systems, with pieces of mail, such as
`letters or packages, being comparable to the data packets
`which are transferred within a data communication network.
`In a postal delivery system, the pieces of mail may be input
`into the postal delivery system in a variety of ways. Once
`within the postal delivery system, all of the pieces of mail
`are collected and transported to nearby processing facilities
`where the pieces of mail are sorted for further processing.
`Although each piece of mail will have a unique delivery
`address, most of the pieces of mail are automatically sorted
`by a shorter zip code or some other type of routing code.
`Letters without zip codes must be sorted and processed by
`hand. Some postal delivery systems also have special forms
`of encoded delivery addresses, such as Post Office box
`numbers at a Post Office, which are not recognizable by
`other postal delivery systems such as Federal Express or
`United Parcel Service. Regardless of which particular postal
`delivery system the piece of mail is deposited into, once the
`mail has been sorted by destination it is routed through
`additional intermediary processing facilities until it arrives
`at the local indicated by the destination on the piece of mail.
`At this point, the zip code or routing code is no longer
`sufficient to deliver the piece of mail to the intended desti
`nation and the local delivery office must further decode the
`destination address in order to deliver the piece of mail to the
`intended recipient. In addition to processing pieces of mail
`for routing the mail to the correct destination, the pieces of
`mail may go on through several other processing steps. For
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`example, if the piece of mail is going out of the country, it
`must go through a customs operation in each country. If the
`national postal delivery system is being used to deliver the
`piece of mail then it must also be transferred from one
`national postal delivery system to another. In a private postal
`delivery system however, this transfer step would not be
`necessary. The pieces of mail may also be monitored or
`filtered for such things as mail fraud violation or shipment
`of hazardous materials.
`Data packets are manipulated in a data communication
`network in a manner similar to that by which pieces of mail
`are delivered in a postal delivery system. Data packets, for
`example, are generated by many different types of means
`and are placed onto a communication network. Typically, the
`data packets are concentrated into a forwarding device, such
`as a local bridge or router, and are then directed by size and
`destination over one or more media types (e.g., fiber optic)
`which are connected to further forwarding devices that could
`be other larger or smaller bridges or routers. These destina
`tion devices then deliver the data packet to its terminal end
`point (i.e., the end user). Along the way the data commu
`nication network may perform filtering and monitoring
`functions with respect to the data packets.
`Just like postal delivery systems have experienced ever
`increasing volumes of mail which must be delivered, the
`volume of protocol data units being transferred across
`computer networks continues to increase as experience is
`being gained with this new form of communication delivery
`system and as more and more applications, with more and
`more expansive communications requirements are being
`developed. In addition, quickly changing technology has
`made the underlying data transmission resources for com
`puter communication networks relatively inexpensive. Fiber
`optics, for example, offer data transfer rates in the gigabyte
`per Second range.
`One of the existing types of forwarding devices which
`offer the greatest potential to meet the increasing demand on
`throughput rates are packet switches. Several classes of
`packet switches exist. Each class differs substantially from
`the other class of devices, but all may be commonly referred
`to as packet switches or forwarding devices.
`A first class of packet switches is that commonly used in
`digital telephone exchanges. By analogy, these switches can
`perform the functions only of a dedicated mail truck which
`relays mail between post offices and drops mail pouches on
`a post office loading dock. These switches are intended only
`to transfer packets among the devices in a single station,
`such as a telephone exchange, and are not capable of
`performing any sorting operations. The format of the packet
`in these systems is chosen to make the hardware in the
`switch as simple as possible; and this usually means that the
`packets include fields designed for direct use by the hard
`ware. The capabilities of this class of switches (for example,
`in such areas as congestion control) are very limited in order
`to keep the hardware simple.
`A second class of packet switches is used in smaller or
`restricted computer networks, such as X.25 networks. By
`analogy, these switches are equivalent to a group of #10
`envelope sorters in the Post Office. These sorters handle and
`process this size envelope efficiently within the post office
`by performing limited sorting and routing functions, but can
`not by themselves deliver mail to its destination. In some
`sense, these switches are very different from the first class of
`packet switches described above, because several of this
`second class of packet switches can work together like
`several #10 envelope sorters can work at one time in the Post
`
`Ex.1008
`APPLE INC. / Page 37 of 65
`
`

`

`5,550,816
`
`10
`
`15
`
`20
`
`25
`
`30
`
`3
`Office. However, there is one substantial similarity in that
`this second class of switches can only handle one format of
`packets (i.e., the protocols). The formats handled by the
`second class of packet switches is much more complex than
`those in the first class. This greater complexity is necessary
`because the protocols are designed to work in less restricted
`environments, and because the packet switches must provide
`a greater range of services. While the formats interpreted by
`the first class of switches are chosen for easy implementa
`tion in hardware, the data packets handled by this second
`class of switches are generally intended to be interpreted by
`software (which can easily and economically handle the
`greater complexity) and provides the inherit benefit of
`incremental flexibility in the design of the packet switch.
`In a third class of packet switches, the packet protocols
`are intended to be used in very large data networks having
`many very dissimilar links (such as a mix of very high speed
`local area networks (LANs) and low speed long distance
`point to point lines). Examples of such protocols are the
`United States designed Transmission Control Protocol/In
`ternet Protocol (TCP/IP), and the International Standards
`Organization's Connectionless Network Protocol (CLNP)
`protocols.
`In addition, this third class of switches (commonly
`referred to as bridge/routers) often must handle multiple
`protocols simultaneously. This third class of switches is very
`similar to the mail processing devices used in the modern
`postal system. Just as there are many countries, there are
`many data packet protocols used in computer networks.
`While a single postal system was once thought to be
`sufficient to handle mail going anywhere in the world, today
`several competing systems like United Parcel Service, Fed
`eral Express, and the U.S. Postal Service exist to handle the
`special needs of mail going to every country, state, city,
`35
`town, and street in the world. Similarly, in computer con
`munication systems, the packet switches are more involved
`in the carrying of data, and must understand some of the
`details of each protocol to be able to correctly handle data
`packets which are being conveyed in that protocol. The
`routers in this third class of packet switches often have to
`make fairly complex changes to the data packets as they pass
`through the packet switch.
`It is this latter class of packet switches to which the
`following detailed description primarily relates. It will be
`appreciated however, that the detailed description of this
`invention can readily be applied to the first and second class
`of switches as well.
`In current conventional packet switch design, a pro
`grammed general purpose processor examines each data
`packet as it arrives over the network interface and then
`processes that packet. Packet processing requires assign
`ment of the data packet to an outbound network interface for
`transmission over the next communications link in the data
`path.
`Currently, most bridge/router implementations rely
`heavily on off-the-shelf microprocessors to perform the
`packet forwarding functions. The best implementations are
`able to sustain processing rates approaching 100,000 packets
`per second (PPS). When dealing with media such as Ether
`net or current telecommunications lines, this processing rate
`is more than adequate. When faster media such as the Fiber
`Distributed Data Interface (FDDI) are used, existing pro
`cessing rates may still be sufficient as long as there is only
`one such high packet rate interface present. When multiple
`high packet rate interfaces are used, 100,000 PPS become
`inadequate. Current software-based implementations for
`
`65
`
`40
`
`45
`
`50
`
`55
`
`60
`
`4
`bridges/routers are simply not capable of media-rate packet
`forwarding on emerging media such as asynchronous trans
`fer mode (ATM) or Optical Connection-12 Synchronous
`Optical Network (OC-12 SONET) which can accommodate
`communication rates up to 6 times the current 100 megabits
`per second limits to rates of 600 megabits per second. It
`should be noted that the ever increasing power of off-the
`shelf microprocessors might solve the throughput problem,
`but this is probably a vain hope. For example, a single
`OC-24 ATM interface can sustain nearly 3 million internet
`working protocol (IP) packets per second. This is over 30
`times the rates achieved by the current best software tech
`niques. If processing power doubles every year, the wait for
`sufficient processing power to make a software approach
`viable would be at least 4-5 years. In addition, the media
`capabilities will likely continue to increase over such a span
`of years. Additionally, any such processor will likely require
`large amounts of the fastest (most expensive) memory
`available to operate at full speed, resulting in an unaccept
`ably high system cost.
`Fortunately most individual packet switch customers will
`never require sustained packet transfer rates at these levels.
`However, the traditional approach of individual customers
`purchasing routers, bridges, modems, and leased phone lines
`is changing. A trend towards developing Metropolitan Area
`Networks (MANs) is beginning in the networking industry
`as an alternative to the traditional approach of individual
`customer local area networks (LANs) connected through
`customer owned leased telecommunication lines.
`The more successful entrants in this area are capitalizing
`on three trends:
`Fiber optic cable can be laid to most business and indus
`trial premises by organizations possessing rights of
`way; this cable can be used to carry 100 Megabits/
`second or more of customer traffic, a bandwidth that
`appears almost limitless to customers.
`The "demarkation point' is changing from a pair of
`copper wires to an Ethernet socket; the MAN vendor
`takes responsibility for the delivery of Ethernet packets
`between sites specified by the customer. The customer
`does not have to be concerned with the intricacies of
`bridges, routers, and modems, which permits market
`penetration into a far less sophisticated customer base.
`Most potential customers are not interested in a public
`network connection. They simply want to interconnect
`a number of buildings or divisions which constitute the
`customer's enterprise in a metropolitan area.
`These MAN vendors are dealing with "customers' in the
`truest sense of the word, where customer and MAN vendor
`are independent enterprises. The trends towards corporate
`decentralization are even producing analogous situations
`within large enterprises.
`Second, enterprises are becoming far more distributed
`than before, and the very definition of an "enterprise' is
`changing. Where in the 1980's all individuals involved in a
`program could be expected to reside in one or two well
`defined locations, a more modern "enterprise' may consist
`of individuals from several divisions, several corporations,
`consultants, roving sales and marketing people, and workers
`who want to telecommute at their convenience. At the same
`time, this modern enterprise needs to protect their informa
`tion from disclosure or sabotage from without the group
`while preserving a liberal access policy from within.
`A wide area "backbone' is a tremendous investment on
`the part of any large enterprise. Yet at the same time, host
`computers and small scale networks are becoming easier to
`
`Ex.1008
`APPLE INC. / Page 38 of 65
`
`

`

`5,550,816
`
`10
`
`15
`
`20
`
`5
`administer while the expertise to administer them becomes
`more widespread. At the same time, organizations with a
`bias towards decentralization are seeing departments and
`divisions owning "their hosts and "their networks that
`they want to plug into a wide area backbone in order to carry
`their traffic. This traffic typically consists of communications
`to other divisions; however, increasingly it will also consist
`of traffic within a division with widely scattered sites.
`All of this follows a known trend of increasing decen
`tralization in the workplace. Many years ago, Management
`Information System (MIS) computers and all the networks
`in the enterprise. Access policy (such as was needed then)
`could largely be done through system administration of the
`host computers.
`The advent of personal computers and affordable work
`stations meant that the networking administrators no longer
`owned all of the host computers anymore, yet these same
`MIS organizations are still charged with their traditional role
`of ensuring the integrity of the enterprise's data. This has led
`to the rise of routing and filtering functions within routers,
`making access control, a network, rather than a host prob
`lem.
`Now the networking industry is moving up one more
`level. Today, clients not only own their own hosts, they own
`their own networks and want to connect these networks on
`25
`a network to network basis. Yet at the same time, the need
`to preserve the integrity of data moving among client
`networks still exists. This trend is producing not just a
`"network", but a "network of networks', where the purpose
`of a backbone is to serve the needs and foibles of its
`constituent networks, not all of which may belong to the
`same enterprise.
`The concept of a "network of networks' is not new. In
`fact, this was one of the guiding philosophies which led to
`the original creation of the Internet. Unfortunately, the logic
`to support this has only been applied to Internet Protocol and
`more recently to the Open Systems Interconnection (OSI)
`model. IP has been designed to perform this trick once (at
`the Internet level) and is little help in organizing traffic
`within a single IP network. Furthermore, IP cannot cope with
`the notion that a single network may be scattered at different
`points throughout the Internet.
`Thus, a need exists for a way to provide equivalent
`protocols and management tools to those that exist today
`within a single network that will work in a "network of
`networks' paradigm.
`One part of a solution to this problem is the use of Closed
`User Groups. A Closed User Group is a potentially widely
`distrib