(12) United States Patent
`Pearce et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 6,556,574 B1
`Apr. 29, 2003
`
`USOO6556574B1
`
`(54)
`
`DUPLICATE IGNORE DELAYTIMER FOR
`ARP LIKE PROTOCOLMESSAGES USING
`ARE PROTOCOL
`
`(75) Inventors: Bernie Paul Pearce, Cary, NC (US);
`Nitin Karkhanis, San Francisco, CA
`(US); Richard Livingston, Hollister,
`CA (US)
`(73) Assignee: Cisco Technology, Inc., San Jose, CA
`(US)
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`Notice:
`
`(21)
`(22)
`(51)
`(52)
`
`(58)
`
`(56)
`
`Appl. No.: 09/283,124
`Filed:
`Mar. 31, 1999
`Int. Cl." ............................. H04L 12/56; H04J 3/16
`U.S. Cl. ....................... 370/401; 370/403; 370/469;
`709/242
`Field of Search ................................. 370/231, 235,
`370/248, 351,386, 389, 392, 401, 402,
`403, 410, 469, 466, 467, 474; 709/242;
`379/221.01, 265.03
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`5,805,594 A * 9/1998 Kotchey et al. ............ 370/401
`5,844.902 A * 12/1998 Perlman ...........
`... 370/401
`6,272,112 B1
`8/2001 Orita .......................... 370/243
`OTHER PUBLICATIONS
`Perlman, Radia, Interconnections, Bridges and Routers,
`1992, pp. 1-8; 31-33; 99-125 and 149–164.
`Tanenbaum, Andrew, Computer Networks, Third Edition,
`Prentice Hall, 1996, pp. 28–34 and 420–242.
`
`Comer, Douglas E., Computer Networks and Internets,
`Prentice Hall, 1997, Chapter 18, pp. 239-249.
`Comer, Douglas E., Internetworking with TCP/IP, vol. 1,
`Third Edition, Prentice Hall, 1995, pp. 89-107.
`Comer, E and Stevens, David L., Internetworking with
`TCP/IP, vol. 2, Design Implementation, and Internal, Pren
`tice Hall, 1991, pp. 37-58.
`RFC 791.
`RFC 793.
`RFC-1122.
`Lewis, Chris, Cisco TCP/IP Routing Professional Refer
`ence, McGraw Hill, 1998, pp. 188–205.
`International Business Business Corporation, Token-Ring
`Network, MAC Frame Format, Chapter 2, pp. 2-1, 2-12.
`* cited by examiner
`Primary Examiner Huy D. Vu
`ASSistant Examiner-Duc Ho
`(74) Attorney, Agent, or Firm-Cesari and McKenna, LLP
`(57)
`ABSTRACT
`A router transmits an ARP Explorer request packet onto a
`subnetwork in order to learn the route (RIF information)
`from the router to an end Station. The end Station receives a
`plurality of ARP Explorer request packets from the router
`because of multiple paths in an SRB network, and the end
`Station transmits an ARP Explorer response packet in
`response to each ARP Explorer request packet received. The
`invention adopts the path of the first ARP Explorer response
`packet received by the router from the end station for the
`RIF information from the router to the end station, and uses
`a “duplicate ignore” timer in order to avoid freezing this
`route into the router tables. The timer begins running upon
`receipt of the first ARP Explorer response packet, and
`expires after an “update time interval”. No further ARP
`Explorer response packet is processed until after expiration
`of the update time interval.
`
`16 Claims, 12 Drawing Sheets
`
`
`
`
`
`
`
`
`
`106
`
`108
`
`802.5
`RING 12
`
`1 34
`
`
`
`2
`BRIDGE
`BR9
`
`802.5
`RING 13
`
`2
`BRIDGE
`BR 10
`
`802.5
`RING 14.
`
`L2
`BRIDGE
`BR5
`
`2
`BRIDGE
`BR8
`
`2
`BRIDGE
`BR11
`
`24 ROUTER
`L3
`
`802.5
`RING 11
`
`126
`
`132
`
`134
`
`136
`
`802.5
`RING 15
`
`
`
`2
`BRIDGE
`BR 12
`
`
`
`802.5
`RING 16
`
`Ex.1008
`CISCO SYSTEMS, INC. / Page 1 of 32
`
`

`

`US. Patent
`
`w,
`
`2
`
`6
`
`1B
`
`
`me$58mmmwmmmmmVNFsn:oz:mogmm2022mogmma022moemmm023wemwe28S38S2%E38mE;m._
`
`
`
`
`3mgNozE59%o023moemmm023mogmmv02E2:m28a28a28S38
`
`owvwmmNmmm«E
`
`DE
`
`r.o:EMNmmPmmmozEmogmmN02269%F02ENe38S38S28
`
`2:
`
`w:o:E3N:Eo:
`
`4nM,w0—“—
`
`$3:6,9%:mm9%mamme022mogmmEoza59%362$98%2023mogmma02mwe3%a£832%5£8a38
`
`CISCO SYSTEMS, INC. / Page 2 of 32
`
`EX.1008
`
`Ex.1008
`CISCO SYSTEMS, INC. / Page 2 of 32
`
`
`

`

`U.S. Patent
`
`Apr. 29, 2003
`
`Sheet 2 of 12
`
`US 6,556,574 B1
`
`20
`4
`
`202
`
`206
`
`254
`
`APPLICATION
`
`APPLICATION - 250
`
`
`
`252
`
`
`
`244
`
`234 -
`
`
`
`
`
`
`
`
`
`
`
`PRESENTATION
`AND SESSION
`
`TRANSPORT
`
`
`
`
`
`DATALINK
`(LEVEL2)
`MAC
`
`246 N
`PACKETS
`(RELIABLE
`COMMUNI
`236-CATION)
`NETWORK
`PACKETS
`(LEVEL3)
`(DATA-
`GRAMS)
`BEST EFFORT
`COMMUNICATION
`(UNRELIABLE)
`FRAMES
`
`INTERCONNECTION
`DEVICE
`
`
`
`240
`
`230
`210
`
`LEVEL3SWITCH
`(ROUTER)
`BASED ON
`IPADDRESS
`
`INTERNETIP
`(LEVEL3)
`
`
`
`DATA LINK
`(LEVEL2)
`MAC
`
`220
`
`LEVEL2 SWITCH
`(BRIDGE)
`PHYSICAL (MAC)
`ADDRESS
`
`219
`
`PHYSICAL
`
`PHYSICAL
`
`215
`
`OS, ORIEEE
`7 LEVEL
`COMMUNICATIONS
`MODEL
`
`INTERNET
`COMMUNICATIONS
`MODEL
`
`FIG. 2
`
`Ex.1008
`CISCO SYSTEMS, INC. / Page 3 of 32
`
`

`

`U.S. Patent
`
`Apr. 29, 2003
`
`Sheet 3 of 12
`
`US 6,556,574 B1
`
`302
`
`
`
`304
`
`306
`
`300
`308
`
`320
`
`322
`
`MAC
`LEADING se
`FIELDS
`
`e
`
`RF
`
`89.5
`
`MAC
`TRALING
`FIELDS
`
`RIBITSET 10
`IEEE 802.5: LEVEL 2 MAC FRAME FIELDS
`FIG. 3
`
`400
`
`402
`
`404
`
`406
`
`408
`
`DSAP SSAP CTRL DATA
`
`IEEE 802.2 LLC FELDS
`FIG. 4
`
`500
`
`502 504
`
`506
`
`508
`
`510
`
`512
`
`CTRL OU
`
`PROTOCOL
`(TYPE)
`
`DATA
`
`IEEE 802.2 LLC FELDS USING SNAP SAP OPTION
`FIG. 5
`
`Ex.1008
`CISCO SYSTEMS, INC. / Page 4 of 32
`
`

`

`U.S. Patent
`
`Apr. 29, 2003
`
`Sheet 4 of 12
`
`US 6,556,574 B1
`
`600
`
`604 TOKENRING MAC DESTINATION ADDRESS FIELD
`
`1st BYTE
`
`2nd BYTE 3rd BYTE 4th BYTE 5th BYTE 6th BYTE
`
`BITS
`|GU/LXXX XXX BITS O-7 BITS O-7 BITS O-7 BITS O-7 BITS O-7
`
`UNIVERSAL | LOCAL BIT-60
`INDIVIDUAL1 GROUP BIT-802
`FIG. 6A
`
`620
`
`
`
`624
`1st BYTE
`
`TOKENRING MAC SOURCE ADDRESS FIELD
`
`2nd BYTE 3rd BYTE 4th BYTE 5th BYTE 6th BYTE
`
`BITS
`RIU/LXXX XXX BITS O-7 BITS O-7 BITS O-7 BITS O-7 BITS O-7
`
`UNIVERSAL | LOCAL BIT-62s
`ROUTING INFORMATION, RLLBIT-22
`F.G. 6B
`
`Ex.1008
`CISCO SYSTEMS, INC. / Page 5 of 32
`
`

`

`U.S. Patent
`
`Apr. 29, 2003
`
`Sheet 5 of 12
`
`US 6,556,574 B1
`
`
`
`650
`ETHERNET MACADDRESSFIELD(DAORSA)
`1st OCTET N 2nd OCTET 3rd OCTET 4th OCTET 5th OCTET 6th OCTET
`BITS
`1-6, 1/0, 1/O
`
`BITS 1-8 BITS 1-8 BITS 1-8 BITS 1-8 BITS 1-8
`
`GROUPINDIVIDUAL BIT-658
`(MULTICAST BIT)
`GLOBALLOCAL BIT - 654
`F.G. 6C
`
`Ex.1008
`CISCO SYSTEMS, INC. / Page 6 of 32
`
`

`

`U.S. Patent
`
`Apr. 29, 2003
`
`Sheet 6 of 12
`
`US 6,556,574 B1
`
`702
`
`704
`
`700
`RIFFIELD
`
`706
`
`TYPE
`
`LENGTH
`
`DIRECTION
`
`708
`
`710
`
`LARGEST
`FRAME
`
`ROUTE
`
`FIG. 7
`
`Ex.1008
`CISCO SYSTEMS, INC. / Page 7 of 32
`
`

`

`U.S. Patent
`
`Apr. 29, 2003
`
`Sheet 7 of 12
`
`US 6,556,574 B1
`
`802-0
`
`
`
`04
`8
`
`4.
`
`806
`
`8
`
`808
`
`800
`
`16
`
`81
`O 24
`
`19
`
`31
`
`VERS HLEN SEE 5* TOTAL LENGTH
`822- IDENTIFICATION FLAGS 83 FRAGMENT OFFSET
`832
`TIME
`/
`TIVE
`PROTOCOL
`HEADER CHECKSUM
`SOURCE PADDRESS
`
`842
`
`1
`
`826
`836
`
`852
`862
`
`872
`
`DESTINATION PADDRESS
`IPOPTIONS (IF ANY)
`
`PADDING - 864
`
`Ex.1008
`CISCO SYSTEMS, INC. / Page 8 of 32
`
`

`

`U.S. Patent
`
`Apr. 29, 2003
`
`Sheet 8 of 12
`
`US 6,556,574 B1
`
`900
`ARP TABLE
`
`
`
`Ex.1008
`CISCO SYSTEMS, INC. / Page 9 of 32
`
`

`

`U.S. Patent
`
`Apr. 29, 2003
`
`Sheet 9 of 12
`
`US 6,556,574 B1
`
`10,000
`ARP TABLE
`
`902
`
`904
`
`906
`
`908
`
`910
`
`P
`RF
`MAC
`ADDRESS INFORMATION ADDRESS
`
`CREATION
`TIME
`
`OTHER
`INFORMATION
`
`
`
`
`
`
`
`ESP1,
`ROUTE
`ESP2,
`ROUTE
`ESP3,
`ROUTE
`
`ESPn,
`ROUTE
`
`10,002
`
`10,004
`
`10,006
`
`10,008
`
`10,010
`
`Ex.1008
`CISCO SYSTEMS, INC. / Page 10 of 32
`
`

`

`U.S. Patent
`
`Apr. 29, 2003
`
`Sheet 10 of 12
`
`US 6,556,574 B1
`
`11,000
`
`
`
`11,014
`
`11,062
`
`11,072
`
`11,075
`
`Ex.1008
`CISCO SYSTEMS, INC. / Page 11 of 32
`
`

`

`U.S. Patent
`
`Apr. 29, 2003
`
`Sheet 11 of 12
`
`US 6,556,574 B1
`
`
`
`
`
`CJELOEIBO | EXIOWd
`
`Ex.1008
`CISCO SYSTEMS, INC. / Page 12 of 32
`
`

`

`U.S. Patent
`
`Apr. 29, 2003
`
`Sheet 12 of 12
`
`US 6,556,574 B1
`
`13,004
`13,002
`
`13,006
`13,008
`
`13,000
`
`ROUTER
`
`13,010
`
`I/O PORT
`CIRCUITS
`
`
`
`13,012
`13,013
`
`PACKET FORMAT
`CIRCUITS
`
`BUFFERS
`
`
`
`CUT THROUGH
`LOGIC CIRCUITS
`FAST CACHE
`TABLE
`
`13,016
`13,017
`
`
`
`
`
`13,022
`
`13,014
`
`
`
`PROCESSOR E. 13,018
`
`ARP TABLE
`
`13,020
`
`Ex.1008
`CISCO SYSTEMS, INC. / Page 13 of 32
`
`

`

`1
`DUPLICATE IGNORE DELAYTIMER FOR
`ARP LIKE PROTOCOLMESSAGES USING
`ARE PROTOCOL
`
`This Patent Application is related to a patent application
`filed by Pearce, et al. titled “MAC Address Extension to
`Maintain Router Information in Source Routed Computer
`Networks', on even date with this patent application, and
`having Ser. No. 09/283,125.
`
`FIELD OF THE INVENTION
`This invention relates to operation of routers in computer
`networks, and more particularly to maintenance of tables of
`Route Information Field information (RIF information) used
`in Source Routing Bridge subnets (SRB Subnets).
`
`15
`
`BACKGROUND
`A computer network comprises, in the Simplest instance,
`a plurality of computers connected together by a communi
`cations media So that the computers can exchange messages.
`The computers are usually referred to as “stations'.
`In an exemplary embodiment, the communications media
`is arranged as a continuous ring and the Stations are attached
`to the ring. This embodiment is referred to as a “token ring”
`local area network. The Stations pass a Special control
`message referred to as a "token' around the ring from one
`Station to the next, and the Station which holds the token
`transmits its messages onto the ring. When it is finished, the
`Station transferS the token to the next Station on the ring.
`In an alternative exemplary embodiment, a local area
`network may implement the Ethernet protocol, or the closely
`related IEEE 802.3 Standard protocol. In an Ethernet system
`all terminals are connected to a common bus. Any Station
`can transmit when it determines that the bus is free, and if
`a collision of packets is detected on the bus, then the Stations
`quit transmitting and back off for a “backoff time interval”,
`and then try again. Other alternative network hardware
`technologies comprise FDDI token ring, ATM networks, etc.
`The present discussion will focus particularly on token
`ring local area networks and their interconnection into larger
`networks.
`A more complex token ring computer network comprises
`Several token rings connected together by Specialized Sta
`tions referred to as “bridges'. A message originating at a
`Source Station on one token ring can reach a destination
`Station on another token ring by passing through one or more
`bridges, where the Specialized job of the bridges is to
`forward messages from one token ring to another. In an
`exemplary embodiment, there may be a plurality of bridges
`between a first token ring and a Second token ring. And the
`path which the message takes from a Source Station on a
`Source token ring may pass through Several intermediate
`token rings, before reaching the destination Station on the
`destination token ring. Further, with a plurality of bridges
`between each pair of a plurality of token rings, there are
`many paths through token rings and bridges which the
`message can take from the Source Station and the destination
`Station.
`In an exemplary embodiment of computer networks,
`referred to as “source route bridge (SRB) networks”, the
`Source Station puts a Specification of the path into the
`message. The Specification is placed in the Route Informa
`tion Field, the RIF, of the message. The RIF determines the
`path that the message is to follow through the bridges and
`token rings as it travels from the Source Station to the
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,556,574 B1
`
`2
`destination station. The RIF is placed by the source station
`into a header of the message. The bridges read the header
`and forward the message in accordance with the RIF Speci
`fication.
`A router is another Specialized Station which enables
`joining many computer networks together. For example, a
`router can join Several computer networks formed from
`token rings and bridges. Also a router can join a token ring
`network to an Ethernet network, an FDDI network, etc., a
`telephone line or a telephone like line, etc. to form a Wide
`Area Network (WAN). The parts of a WAN may be widely
`Separated, and joined by the telephone like line.
`Routers are used to implement hierarchical addressing.
`Hierarchical addressing commonly uses a two level address
`ing method. A first level corresponds to Layer 2 of the OSI
`communications model, and a Second level corresponds to
`Layer 3 of the OSI communications model. Hierarchical
`addressing permits Layer 3 to be independent of the com
`munications media. The OSI model Layer 2 depends upon
`the communications media, the Layer 2 hardware technol
`ogy (Such as token ring, Ethernet, etc.), and other Layer 1
`and Layer 2 details. Accordingly, a programmer can write
`code to implement Layer 3 functions without having con
`cern for media dependent details which are handled by
`Layer 2 functions.
`Hierarchical addressing is important in the construction of
`large networks, for example networks having many thou
`Sands of Stations, by permitting a Single computer to main
`tain a table of network addresses without having to keep a
`table giving the physical address of each individual com
`puter on an entire network (for example, the Internet). A
`packet is sent to a router on the designated destination
`network, and that router keeps a table of the Layer 2 address
`of computers on the destination network. Without hierarchi
`cal addressing each router would have to keep tables of the
`Layer 2 addresses of all computers on the entire network,
`rather than Simply keeping a network address referring to the
`computers on that particular network, and there are many
`fewer networks than there are computers. Radia Perlman
`treats hierarchical addressing in her book Interconnections,
`Bridges and Routers, published by Addison Wesley Pub
`lishing Company, in 1992, all disclosures of which are
`incorporated herein by reference, particularly in Chapter 6,
`pages 149-164.
`Commonly used terminology refers to a Small local area
`network as a “Subnet'. For example, a plurality of token
`rings joined by bridges is a Subnet. Also an Ethernet with one
`bus, or with Several buSSes joined by bridges, is a Subnet. A
`“network' then refers to several Subnets joined by a router.
`Arouter or a bridge can be connected to a telephone type line
`and join Subnets in distant cities. For example, a bridge may
`forward frames using Data Link Switching to interconnect
`subnets in distant cities. A “wide area network” (WAN)
`refers to Subnets joined by routers or bridges, with the
`Subnets typically being widely separated, for example, in
`different cities.
`Each Station has a physical address, also referred to as the
`MAC address, and the physical address is the OSI model
`Layer 2 address. The Layer 2 address is also referred to as
`the "Link Address'. Also, each Station is assigned a Layer3
`address or network address. For example, in the TCP/IP
`protocol the Layer 3 (network) address is referred to as the
`Internet Protocol address, or IP address. The two levels of
`hierarchical addressing, the Layer 2 address and Layer 3
`address, are typically used in the OSI model to implement
`Subnets and networks.
`
`Ex.1008
`CISCO SYSTEMS, INC. / Page 14 of 32
`
`

`

`US 6,556,574 B1
`
`15
`
`25
`
`3
`The physical address is written into a Semi-permanent
`memory device when the Station is manufactured, and is
`referred to as the “burned in address. However, the physical
`address may be changed by the owner of the Station, by
`overriding the burned in address with a locally administered
`address, referred to as a LAA address.
`On a Subnet, a message is addressed to both the physical
`address and the Network address of the destination station.
`A bridge simply forwards the message. In the SRB network
`embodiment, where the message carries RIF information,
`the bridge obeys the instructions in the RIF of the message
`and forwards the message only along the path Specified by
`the RIF.
`However, when the Source Station and the destination
`Station are on different Subnets, the message is addressed to
`the physical address of a router and the Network address of
`the destination Station. The addressed router is a Station on
`the Subnet of the Source Station. The router recognizes its
`physical address in the message, reads the Network address
`of the destination Station from the header of the message,
`and then makes a decision as to how to route the message So
`that it goes to the destination Station. The router writes a new
`header into the packet message before forwarding it onto the
`next SRB Subnet The new header contains a new RIF. The
`new RIF directs the message through the token rings and
`bridges of the new SRB Subnet. Alternatively, the new
`Subnet may an Ethernet LAN, and in this case the router
`builds an Ethernet packet.
`In making its decision, the router uses tables which
`correlate a physical address with a Network address. Also,
`for SRB subnets, the physical address is correlated with RIF
`information using a RIF table. The router must first,
`however, execute a protocol in order to populate its tables.
`Also, stations on the SRB subnet must know the physical
`address, the Network address, and the RIF information for a
`destination Station. Thus each Station must also go through
`protocols in order to populate its address tables.
`There are a number of protocols used on computer
`networks for transferring messages from a Source Station,
`through intermediate bridges and routers, to a destination
`station. Names of various protocols comprise: TCP/IP,
`Apollo, Appletalk, CLNS, DECnet, IPX, Vines, XNS, SNA,
`and others. The TCP/IP protocol is often used to provide
`reliable message transport between Layer 3 entities. Under
`TCP/IP, commonly used protocols and messages for
`Stations, including routers, to populate their tables include an
`Address Resolution Protocol (ARP) message; and, an All
`Routes Explorer (ARE) message. These two concepts, ARP
`and ARE messages, will be explained Separately, although
`50
`they are often combined in one packet, referred to as an
`“ARP Explorer" packet. Protocols other than TCP/IP will be
`discussed hereinbelow.
`An ARP message is used by a first Station to learn the
`physical address needed to reach a Second Station where the
`fists station already knows the Network address of the
`Second station. Often, a source station will know the Net
`work address of an intended destination Station, but will not
`know the physical address needed to reach the destination
`Station. Also, the Source Station will not know, and does not
`need to know, the media over which a packet must travel to
`reach the intended destination Station.
`In the event that both the first and second stations are on
`the same Subnet, the needed physical address will be the
`physical address of the Second Station. However, in the event
`that the first and Second Stations are on different Subnets, the
`necessary physical address will be the physical address of a
`
`4
`router. Both the Subnet of the first station and the remote
`Second Station may be the same type of media, for example
`SRB Subnets, or for a further example both may be on
`Ethernets. Alternatively one subnet may be an SRB subnet
`and the other a different media technology, for example
`Ethernet. Once the first station learns both the Network
`address and the physical address to place in a message, it
`caches this information in a table referred to as the “ARP
`table'. Protocols other than TCP/IP use “ARP like tables to
`provide a binding between a Station's physical address and
`network address.
`The example in which both the source subnet and the
`destination Subnet are SRB Subnets, is next described. Once
`the Source Station learns the proper physical address to reach
`the Second Station, the Source Station uses ARE messages in
`order to learn a route. The Source Station places the Network
`address and physical address in the ARE message. The ARE
`message traverses all routes from the Source Station to the
`Second Station whose physical address is written into the
`message (either the intended destination Station or the physi
`cal address of a router).
`In a commonly used embodiment one packet, the “ARP
`Explorer packet”, is used with the ARP functionality in
`Layer3 fields of the packet, and the ARE functionality in the
`Layer 2 fields, as described in more detail hereinbelow. The
`ARP Explorer packet is referred to as a “packet” because it
`is a message between Layer 3 functions in a Source Station
`and in a destination Station.
`Both the ARP message and the ARE message are for
`warded by bridges. However, both the ARP message and the
`ARE message are confined to the Subnet of their Source
`station, and are not routed by a router. Also, the ARP
`Explorer packet is forwarded by bridges but is not routed by
`routers, and So is confined to the Subnet of its Source Station.
`The ARE message protocol gives a Source Station the
`route to use to reach the Station whose physical address
`(router or destination station) is needed to reach the desti
`nation Station. The route information is then Stored in the
`station in a RIF table. The RIF information must be updated
`frequently, as bridges may become congested, bridges may
`fail, telephone lines may be cut, etc.
`Hereinafter the TCP/IP terminology will be used, and the
`Network address will be referred to as the IP address. When
`the ARP and ARE protocols are combined in one packet,
`referred to as an ARP Explorer packet, then Layer 3 in the
`packet controls the ARP functionality and Layer 2 controls
`the ARE functionality. The ARP Explorer packet is trans
`mitted onto a SRB Subnet by a source station, and the source
`station may be either a router or an end station. The ARP
`Explorer packet is confined to the SRB Subnet as it is not
`routed by a router. The ARP Explorer packet is forwarded by
`all of the bridges in the SRB subnet because of the ARE
`functionality. A route is built up in the RIF field of the ARP
`Explorer packet as it is forwarded by various bridges onto
`various token rings. The ARP Explorer packet is examined
`by all end Stations receiving it by a Layer 3 function to
`determine if the IP address in the ARP inquiry field matches
`the receiving station's IP address. In the event that the
`receiving station finds a match between the IP address in the
`ARP inquiry field of the ARP Explorer packet and the
`receiving Station's IP address, the receiving Station transmits
`a response packet to the Source Station. The response packet
`is directed back to the Source Station along the route built up
`in the RIF field of the ARP Explorer packet, but in reverse
`order.
`Build up of the route in the RIF field of the ARP Explorer
`packet is next discussed in greater detail. The ARE function
`
`35
`
`40
`
`45
`
`55
`
`60
`
`65
`
`Ex.1008
`CISCO SYSTEMS, INC. / Page 15 of 32
`
`

`

`US 6,556,574 B1
`
`15
`
`25
`
`35
`
`40
`
`S
`in the ARP Explorer packet has the property that when it
`reaches a bridge on a first token ring, a copy of the ARP
`Explorer packet is both forwarded by the bridge to the next
`token ring, and a copy continues around the first token ring.
`AS it is forwarded by a bridge, the ring number of the ring
`it is going to, along with the bridge number of the forward
`ing bridge, is written into the RIF of the ARP Explorer
`packet. The RIF information is built up on a “bridge by
`bridge' basis as pairs of ring number and bridge number, as
`the ARP Explorer packet is forwarded throughout the Sub
`net. Further, if the copy of the ARP Explorer packet con
`tinuing around the first token ring is received by a Second
`bridge, again a copy is forwarded by the bridge to a token
`ring (either another token ring or the same “next token ring
`if more than one bridge joins the first token ring and the
`“next token ring), and also a copy continues around the first
`token ring. As a result, the destination Station receives a
`plurality of copies of the ARP Explorer packet. And each
`copy specifies, in the RIF of the ARP Explorer packet, the
`path taken by that copy through the Subnet.
`Upon receipt of each copy of the ARP Explorer packet,
`the destination station having the IP address which is in the
`IP inquiry field of the ARP Explorer packet then resets a
`“direction bit” in the ARP Explorer packet and re-transmits
`it onto the Subnet as an "ARP Explorer response' message.
`The “direction bit is an indicator in the header of the
`message which specifies whether the path of the RIF is to be
`traversed from left to right, which takes the message from
`the Source Station to the destination Station, or from right to
`left which takes the ARP Explorer response message back to
`the source station. Each copy of the ARP Explorer packet
`received by the destination station is thereby converted into
`an ARP Explorer response message which is received by the
`Source Station. Each ARP Explorer response message
`received by the Source Station Specifies a different path
`through the Subnet to the destination Station. The Source
`Station then chooses one of the routes to populate its RIF
`table. One method of choosing the route from the duplicates
`is to choose the route in the RIF field of the first received
`ARP Explorer response packet. The Source Station then uses
`the RIF value until an event occurs requiring updating of the
`RIF table: for example, the expiration of a time interval and
`the transmission of another ARP Explorer packet; or for
`example, when the Source Station is a router, the receipt of
`a packet to be routed to that destination Station.
`Traditionally, a router may update its ARP table and RIF
`table upon receipt of an ARP Explorer packet transmitted by
`an end Station. Upon receipt of the ARP Explorer packet, the
`router transmits an ARP Explorer response message to the
`end Station, just like any other Station. Also, the router reads
`the RIF information from the ARP Explorer packet and uses
`it to update its ARP table and RIF table entries.
`Another commonly used technique for updating RIF
`information is for a station to listen to message traffic, and
`to copy RIF information, physical address, and IP address
`combinations from all messages, and use this information to
`simply overwrite older entries in its ARP table and its RIF
`table. Particularly, Some routers have been designed to listen
`to message traffic, and to use REF information, physical
`address, and IP address combinations read from every
`message which the router routes, in order to update the entry
`in the router's ARP table and RIF table. Update is accom
`plished by overwriting the current entry in the table.
`In the event that a router receives a message having the
`physical address of the router and the IP address of a station
`which is not on the Subnet from which the message arrives,
`then the router makes decisions. First the router checks its
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`ARP table to learn if the IP address is in its ARP table by
`using the IP address as an index into the ARP table. If the IP
`address is indeed in the ARP table, the router now knows the
`proper Subnet to route the message to, and knows the proper
`physical address to put in the message (the proper physical
`address may again be either the destination Station or
`another router). Next, the router checks its RIF table, by
`using the Layer 2 address as an indeX into the table, in order
`to determine if the physical address is in the RIF table, and
`if it is, the router simply writes the RIF information into the
`RIF of the message and routes the message on its way.
`However, in the event that the needed information is not in
`either the ARP table or the RIF table, the router must
`transmit an ARP Explorer packet in order to build an entry
`in its ARP and RIF tables.
`In the related patent application mentioned above, a new
`and novel table which extends the physical address to
`include the RIF information for use in a router is disclosed.
`This extension of the physical address permits the ARP table
`to keep both the correlation between the physical address
`and the IP address, as well as the RIF information needed by
`the router to route a message to the destination Station. With
`this new extended ARP table the problem of receipt of
`multiple copies of the ARP Explorer response packet
`remains.
`There is needed a mechanism whereby a router can update
`its RIF entry for a destination Station on a token ring network
`using the new combined ARP and RIF table, use a protocol
`which gives a “best route (for example a fastest route), and
`update the RIF entry on a timely basis.
`SUMMARY OF THE INVENTION
`A router transmits an ARP Explorer request packet onto a
`Subnetwork in order to learn the route (RIF information)
`from the router to a destination end Station. The end Station
`receives a plurality of ARP Explorer request packets from
`the router because of multiple paths in an SRB network, and
`the end Station transmits an ARP Explorer response packet
`in response to each ARP Explorer request packet received.
`The invention adopts the path of the first ARP Explorer
`response packet received by the router from the end Station
`for the RIF information from the router to the end station,
`and uses a “duplicate ignore” timer in order to avoid freezing
`this route into the router tables. The timer begins running
`upon receipt of the first ARP Explorer response packet, and
`expires after an “update time interval”. No further ARP
`Explorer response packet is processed until after expiration
`of the update time interval. All duplicate ARP Explorer
`response packets are expected to arrive during the update
`time interval. Therefore the routing information is not
`updated by a Second ARP Explorer response packet until
`after all duplicate ARP Explorer response packets have been
`received and rejected. Use of the update time interval
`chooses the fastest path, as the first ARP Explorer response
`packet to be received by the router is probably generated by
`the first ARP Explorer request packet received by the
`intended destination end Station, and probably traveled
`along the fastest path from the router to the intended
`destination end Station. Expiration of the duplicate ignore
`timer allows later issued ARP Explorer request packets to
`dynamically update the RIF information as conditions on the
`network change, after expiration of the duplicate ignore
`timer. The RIF information will be updated after the router
`executes a Subsequent ARP Explorer request protocol, and
`receives the first of the duplicate ARP Explorer response
`packets, with the duplicate ignore timer permitting only the
`first received ARP Explorer response packet to update the
`RIF information in the router.
`
`Ex.1008
`CISCO SYSTEMS, INC. / Page 16 of 32
`
`

`

`7
`A router receives an ARP Explorer request packet trans
`mitted onto a subnetwork by an end station. The router
`receives a plurality of ARP Explorer request packets from
`the end station because of multiple paths in an SRB network.
`The invention adopts the path of the first ARP Explorer
`request packet received by the router from the end Station for
`the RIF information from the router to the end station, and
`uses a “duplicate ignore” timer in order to avoid freezing this
`route into the router tables
`Other and further aspects of the present invention will
`become apparent during the course of the following descrip
`tion and by reference to the accompanying drawings.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`Referring now to the drawings, in which like numerals
`represent like parts in the Several views:
`FIG. 1 is a block diagram of a computer network in
`accordance with the invention.
`FIG. 2 is a block diagram of communications protocols
`and interconnecting devices.
`FIG. 3 is a block diagram of a MAC frame.
`FIG. 4 is a block diagram of IEEE 802.2 LLC fields.
`FIG. 5 is a block diagram of IEEE 802.2 LLC fields
`including SNAP SAP fields.
`FIG. 6A-FIG. 6C are block diagrams of a MAC address
`field.
`FIG. 7 is a block diagram of a RIF field.
`FIG. 8 is a block diagram of an IP Layer 3 header.
`FIG. 9 is a block diagram of an ARP table in a router in
`accordance with the invention.
`FIG. 10 is a detailed block diagram of an ARP table in a
`router in accordance with the invention.
`FIG. 11 is a block diagram of a SRB subnet.
`FIG. 12 is a timing diagram in accordance with the
`invention.
`FIG. 13 is a hardware functional block diagram of a
`rOuter.
`
`15
`
`25
`
`35
`
`40
`
`DETAILED DESCRIPTION
`
`FIRST EXEMPLARY EMBODIMENT
`The First Exemplary Embodiment describes the invention
`as used in a TCP/IP communications model. Further exem
`plary embodiments describe the invention as used in other
`communication protocols, for example in the protocols
`Apollo, Appletaak, CLNS, DECnet, IPX, Vines, XNS, SNA,
`and others.
`
`45
`
`50
`
`INTRODUCTION
`Operational functions of a computer network are com
`monly Separa