`
`18
`
`For the router network to be able to route messages correctly, each
`
`the hosts. This knowledge is
`router must know the whereabouts of all
`distributed amongst the different routers using LSPs. However, before the a
`
`5
`
`router can distribute information about the location of a host, it must become
`
`aware of the existence of the host.
`
`In the standard system, each router is aware of the subnets attached to
`
`it (this knowledge may, for example, be entered manually). A router need not
`lObe explicitly aware of the existence of the hosts attached to the LAN.
`If a .
`
`message for a host on the LAN is received, the router can send out an ARP
`
`request, and the ARP response confirms the existence of the host on the LAN.
`(If there is no ARP response, then it is assumed that the host does not exist.)
`
`As discussed above, in the standard system the router in fact maintains
`an interface table for the various hosts on the LAN, so that it can forward
`future messages to them without having to obtain their MAC identifiers by ARP
`
`requests. The interface table is built up partly from ARP requests sent out by
`the router, and partly by ARP requests sent out from the hosts.
`
`A standard router preferably maintains this table actively, by polling the
`
`hosts at suitable intervals. The poll message is simply an ARP request to the
`host. An ARP response confirms the existence of the host; if there is no ARP
`response, the host no longer exists.
`
`In the present system, the modified router maintains its interface tables
`in broadly the same way as do standard routers. The present router, however,
`
`necessarily constructs its interface tables entirely automatically, whereas in a
`standard router the subnet addresses may be entered manually.
`
`15
`
`20
`
`25
`
`30
`
`SONY EXHIBIT 1003- Page 577
`
`ReexamFH_000577
`
`
`
`19
`
`The present routers listen promiscuously for ARP requests from hosts
`
`(for a reason discussed later), and may listen similarly to other messages. This
`
`listening helps the routers to maintain their interface tables. The routers will
`
`therefore automatically learn of the existence of hosts which are involved in
`
`5
`
`message transmission. However, it is possible that when a host is moved from
`
`one router to another, some other host may want to send a message to it before
`
`it has itself tried to send any messages.
`
`(In the standard IP system, hosts do
`
`not advertise themselves; the identity between the subnet address and the top
`
`part of the host address means that the location of a host is inherent in the
`
`10
`
`system.)
`
`Another way in which the routers can automatically discover the
`
`existence of hosts is for the hosts to announce their existence when they are
`
`first turned on, with the routers listening for such messages. However, this
`
`15
`
`requires the hosts to issue suitable identification messages when first turned on;
`
`this may require modification of some hosts, and some types of host may not
`
`be modifiable.
`
`Some mechanism must therefore be provided for the router network to
`
`20
`
`discover the existence of silent hosts. Since changes cannot be imposed on the
`
`hosts themselves,
`
`the standard routers must therefore be modified,
`
`in the
`
`present system, so that they can discover the existence of such silent hosts.
`
`There are two ways in which this can be done, which maybe termed active and
`
`passive.
`
`(It may be noted that in standard routers, the subnet addresses may
`
`25
`
`be passed round automatically but will normally be set manually.
`
`In the
`
`present system,
`
`the subnet addresses are not of such importance, and the
`
`modified routers must determine all host addresses automatically.)
`
`With the active technique, the routers actively search for hosts. Each
`
`30
`
`router has to be modified to perform polling. For this, the routers in the level
`
`SONY EXHIBIT 1003- Page 578
`
`ReexamFH_000578
`
`
`
`20
`
`1 area are informed (eg. manually) of the address space of the hosts in that
`
`area. Each router then polls each of its interfaces in tum; that is, for each
`
`interface in tum it sends out a series of ARP requests, working through the host
`
`address space address by address.
`
`It will therefore elicit responses from all
`
`5
`
`hosts attached to it.
`
`This polling is of course distinct from the polling, mentioned above,
`
`which standard routers perform. The standard router polling is not through the
`
`host address space, but through the actual addresses of hosts which are already
`
`10
`
`recorded in the routers' tables, to confirm their existence.
`
`Provided that the host address space is manageably small, this is the
`
`preferred mechanism. This polling automatically takes care of the normal
`
`maintenance of the interface tables. Since the router network can only route
`
`15
`
`messages to hosts which it knows about,
`
`it is important
`
`to confirm the
`
`disappearance of a host, ego by a suitable number of retries. A discovery time
`
`of say 500 s (comparable to the ARP time-ouO, and a polling rate of? polls per
`
`second will accommodate an address space of 4000 hosts, which is much larger
`
`than most practical LANs.
`
`20
`
`The polling message density can be reduced if a router does not poll for
`
`addresses which it knows to be attached to other of its interfaces, or to other
`
`routers. However, a router needs to poll for hosts which are attached to it to
`
`confirm their existence, just as with a standard router; also, polling for hosts
`
`25
`
`which are listed in its tables as being attached to other routers accelerates their
`
`discovery if they are moved.
`
`Instead of polling by ARP requests, a router could poll by sending a
`
`suitable broadcast message, asking the hosts to report
`
`their existence.
`
`30
`
`However, this has two disadvantages. One is that it requires the hosts to return
`
`SONY EXHIBIT 1003- Page 579
`
`ReexamFH_000579
`
`
`
`21
`
`suitable identification messages in response to the broadcast enquiry; this may
`require modification of some hosts, and some types of host may not be
`modifiable. The other is that the response messages from the hosts will
`temporarily produce a very high message density, which may for example
`
`5
`
`overwhelm the router.
`
`With the preferred mechanism of ARP polling, the polling intensity can
`
`be reduced by partitioning the host address space so that certain segments of it
`will only contain hosts which will announce their presence when first turned
`on. It will then not be necessary to poll through those address space segments.
`
`A possible refinement of ARP polling is that if a router discovers that
`a host has disappeared, that host address can be distributed to all routers, with
`all routers then sending out ARP requests at higher than normal polling
`frequency for that host for some convenient period of time. (The router which
`has lost the host should be included in this, because the host may be migrating
`to another of its interfaces.) This will result in rapid detection of the migrating
`host if it is reconnected into the network.
`
`With the passive technique for routers to discover the existence of silent
`hosts, they only search for a host when there is a message for that host. If the
`router network receives a message for a host which it (the router network) does
`not recognize, then the message is passed around the routers, and each router
`polls each of its interfaces with an ARP request.
`
`This requires a more complex router network organization, to ensure that
`the message is distributed to all routers, but it may reduce the amount of
`polling, as the occurrence of messages to silent hosts will usually be relatively
`uncommon. The message may be distributed rapidly to all routers, with all the
`routers then polling their LANs; this may impose a significant transient load on
`
`10
`
`15
`
`20
`
`25
`
`30
`
`SONY EXHIBIT 1003- Page 580
`
`ReexamFH_000580
`
`
`
`22
`
`the system. Alternatively, each router in turn may poll its interfaces for the
`
`destination host, and forward the message on to the next router only if it fails
`to find the destination host on any of its interfaces; this may result in a large
`delay.
`
`.-
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`Host to host communication
`In the standard system, there are 4 mechanisms for a source host to send
`a message to a destination host. First, if the destination has the same suhnet
`address as the source, if the source does not know the destination's MAC
`identifier it will send an ARP request to the destination; otherwise (second), it
`sends the message direct to the destination using the MAC identifier. Third,
`if the destination is on a different subnet, the source sends the message to a
`router. Fourth, if the destination is on a different subnet but the same extended
`LAN as the source,
`the source can send direct to the destination's MAC
`identifier as a result of a redirect message from a router.
`
`these modes of message
`The present system must maintain all
`transmission as far as the hosts are concerned; in particular, it must cope with
`all possible combinations of source and destination subnet addresses and LAN
`locations. The source and destination may be on the same or different LANs,
`and may have the same or different subnet addresses.
`
`If the source and destination are on the same LAN and have the same
`subnet address, then if the source knows the destination's MAC identifier it will
`send the message direct
`to the destination using the MAC identifier.
`
`Otherwise, the source will send an ARP request to the destination and, hecause
`the two are on the same LAN, it will get an ARP response and then send the
`message using the MAC identifier returned in the ARP response. This is the
`same as in the staitdard system.
`
`SONY EXHIBIT 1003- Page 581
`
`ReexamFH_000581
`
`
`
`23
`
`If the source and destination are on different LANs and have different
`
`subnet addresses, the source will send the message to a router, which will
`
`forward it to the router to which the destination is attached. This is broadly
`
`similar to the standard system (though the router uses the more detailed routing
`
`5
`
`infonnation of the present system).
`
`If the source and destination are on the same LAN but have different
`
`subnet addresses, the source will send the message to a router; this will return
`
`a redirect message to the source, which will then send the message direct to the
`
`10
`
`destination using the destination's MAC address. This is broadly similar to the
`
`standard system (though again the router uses the more detailed routing
`
`infonnation of the present system).
`
`If the source and destination are on different LANs but have the same
`
`15
`
`subnet address, then the source will send an ARP request to the destination,
`
`expecting to receive an ARP response with the destination's MAC identifier.
`
`The router on the source LAN must listen for such ARP requests and return
`
`ARP responses (this is the promiscuous listening for ARP requests mentioned
`
`above). On hearing an ARP request on an interface, the router must check its
`
`20
`
`link tables and its interface tables for its other interfaces for the destination.
`
`If the destination is in those tables, it is in fact on a different LAN from the
`
`source. However, the source is expecting an ARP response. The router must
`
`.therefore return a proxy ARP response - ie, it must return an ARP response on
`
`behalf of the destination. This proxy ARP response will of course contain the
`
`25
`
`router's MAC identifier. The source will then send the message to the router,
`
`which must then forward it through the router network.
`
`Specific Embodiment
`
`A communication system embodying the invention will now be
`
`30
`
`described, by way of example, with reference to the drawings, in which:
`
`SONY EXHIBIT 1003- Page 582
`
`ReexamFH_000582
`
`
`
`24
`
`Fig. 1 is a general block diagram of the system; and
`
`. ?
`
`Fig. 2 is a highly simplified block diagram of a modified router (ie. the
`
`present router).
`
`5
`
`Fig. 1 shows a communication system with various typical features. The
`system consists ofa level 1 network of3 routers RI-R3 coupled by links LKI2,
`LK23, and LK13 (the digits indicating the routers which each link couples
`
`together). This level 1 network forms part of a level 2 system (the rest of
`
`which is shown merely as a cloud L-2), and is coupled to the rest of the level
`
`10
`
`2 network by links shown as zig-zag lines.
`
`15
`
`Router Rl has 2 physical LAN interfaces, with LANI (with suimet
`address 32.17.52) and LAN4 (with subnet address 32.17.66) coupled to them;
`router R2 has 3 LAN interfaces, with LAN2 (with subnet address 32.17.55),
`LAN3 (with subnet address 32.20.132), and LAN6 (with subnet address
`32.20.154) connected to them; and router R3 has 2 LAN interfaces, with LAN5
`
`(with subnet address 32.27.24) and LAN7 (with subnet address 32.17.102)
`
`connected to them. LANI and LAN2 are connected together in known manner
`
`through a bridge BRl, forming a single extended LAN with two subnet
`
`20
`
`addresses.
`
`. Hosts HI-Hll are coupled to the various LANs as shown. Each host
`
`has an address consisting of 4 bytes.
`
`In the standard system, each host's
`
`address will be the address of its LAN plus a final byte added to the eJ;ld of the
`
`25
`
`subnet address, as shown for hosts H2 (address 32.17.52.32), H3 (address
`
`32.17.52.5), H5 (address 32.17.55.129), and H8 (address 32.17.66.188).
`
`Each host maintains a connection table for its connections. HostH2, for
`example, will maintain the following table:
`
`30
`
`SONY EXHIBIT 1003- Page 583
`
`ReexamFH_000583
`
`
`
`25
`
`Host H2, connection table
`
`Router connection:
`RI-MAC
`
`Host list:
`32.17,52.5 (H3)
`32,17.55,129 (H5)
`
`H3-MAC
`H5-MAC
`
`5
`
`10
`
`This table has two parts, a router connection and a host list. The router
`
`connection part is a single entry, the MAC of router RI, which the host uses
`
`for sending messages to hosts which are not on its own extended LAN, The
`
`second part lists the hosts which H2 has recently sent messages to, together
`
`15
`
`with the MAC identifiers which it uses to send messages to those hosts.
`
`Communication with H3 is direct, over LANl, so messages to that host are
`
`sent to that host's MAC identifier. Communication with H8 is via the router
`
`network, so messages to that host are sent to router Rl, using that router's
`MAC identifier. Communication with H5 is also direct; H2 has learnt H5's
`20 MAC identifier as the result of a redirect message from router RI or R2 at
`some time in the past.
`
`The host maintains this table as a cache with time-out, so that entries
`
`which have not been used for more than a certain time are deleted. New
`
`25
`
`entries are added as communication with new hosts is desired, by using the
`
`ARP requests as discussed above.
`
`Each router maintains interface and link tables, Router RI, for example,
`
`would maintain the following interface tables if it were a standard router,
`
`30
`
`SONY EXHIBIT 1003- Page 584
`
`ReexamFH_000584
`
`
`
`Router R1 {standard fomil. interface tables
`
`26
`
`1F1 (interface)
`32.17.52 (subnet address)
`5
`H3-MAC
`32
`H2-MAC
`
`32.17.55 (subnet address)
`129 H5-MAC
`
`IF2 (interface)
`32.17.66 (subnet address)
`188 H8-MAC
`
`Each interface table is divided into a separate section for each logical
`subnet address of the (possibly extended) LAN attached to that interface. Each
`section records the subnet address and then lists the hosts on the LAN with that
`subnet address. Each host entry consists of the host's address and its MAC
`identifier. The host's address is recorded as only the final byte, since the first
`3 bytes of the address are the address of its subnet. The first interface table
`has two sections because the two LANs LAN1 and LAN2, with different subnet
`addresses, are both connected to that physical interface (via the bridge BRI in
`the case of LAN2).
`
`5
`
`10
`
`15
`
`20
`
`25
`
`The routers also maintain link tables for their links to other routers. In
`
`the standard system, each router passes the addresses of the LANs to which it
`is coupled to the other routers in the level I network, and those other routers
`
`30
`
`hold that information in their link tables. Thus if router RI were standard, it
`
`would maintain two link tables as follows.
`
`SONY EXHIBIT 1003- Page 585
`
`ReexamFH_000585
`
`
`
`Router Rl (standard form), link tables
`
`27
`
`LKI2:
`
`LKI3:
`
`5
`
`10
`
`32.20.154
`32.20.132
`
`(LAN6)
`(LAN3)
`
`32.27.24
`32.17.102
`
`(LAN5)
`(LAN7)
`
`The entries in each table are the addresses of the LANs which can be
`
`reached through the associated link. If link LK13 did not exist, then the link
`
`15
`
`table LK12 would contain the addresses 32.27.24 and 32.17.102 (as well as
`
`32.17.154 and 32.20.132), because the message route for those addresses
`
`would then be via router R2.
`
`Each subnet address in the link tables can be regarded as a compressed
`
`20
`
`version of the set of host addresses on that LAN. This can be represented
`
`more fully by writing the subnet addresses as 32.17.154.xx., etc, where the
`
`final byte is masked off by a mask.
`
`For the coupling to the rest of the level 2 system, the routers provide
`
`25
`
`further compressed addresses over the zig-zag links to region L-2. In this case,
`
`the level 2 addresses will be simply the single value 32.000lxx.xx.xx.xx (where
`
`the second byte is written in binary). Similarly, the routers R2 and R3 will
`
`. maintain level 2 connection tables (with further compressed entries) for
`
`addresses in the L-2 region. Also, router Rl will maintain these region L-2
`
`30
`
`addresses (preferably in the same compressed form) in its link tables LKl2 and
`
`LKI3, so that messages from hosts on its LANs to the L-2 region can be
`
`correctly routed. (This is why the tables LK12 and LK13 are shown as having
`
`further entries beyond the 2 shown explicitly for each.)
`
`SONY EXHIBIT 1003- Page 586
`
`ReexamFH_000586
`
`
`
`28
`
`In the present system, the routers are modified from the standard form
`
`to maintain the level I connection information within the interface and link
`. tables in uncompressed form. Thus the interface table for interface IFI for
`
`router RI will contain:
`
`5
`
`10
`
`Router RI (modified form), interface table IFI
`
`IFI:
`
`32.17.52.5
`32.17.52.32
`32.17.55.129
`32.20.154.34
`
`H3-MAC
`H2-MAC
`H5-MAC
`HI-MAC
`
`15
`
`Switching, for convenience, to router R3 to discuss the link tables, this
`
`would contain the following link table for link LK13 in the standard form:
`
`Router R3 (standard form). link table LKI3
`
`20
`
`LK13:
`
`32.17.52
`32.17.55
`32.17.66
`
`(LANI)
`(LAN2)
`(LAN4)
`
`25
`
`30
`
`For the modified form of router R3, this link table will contain all the entries
`for router RI's interface tables, in the same form as in those interlace tables,
`instead ofjust the compressed or subnet addresses. Thus router R3 will contain
`
`the following link table for link LK13 in the modified form:
`
`SONY EXHIBIT 1003- Page 587
`
`ReexamFH_000587
`
`
`
`Router R3 (modified form), link table LKl3
`
`29
`
`LK13:
`
`5
`
`32.17.52.5
`32.17.52.32
`32.17.55.129
`32.17.66.188
`
`H3-MAC
`H2-MAC
`H5-MAC
`H8-MAC
`
`10
`
`The connection information relating to connections to the level 2 area
`
`L-2 is unchanged from the standard form.
`
`With the host addresses discussed up to now, the operation of the system
`
`with the present (modified)
`
`routers is substantially unchanged from the
`
`15
`
`operation with standard routers. Suppose, however, that host HI was originally
`
`on LAN6 (address 32.20.154), and was given the address 32.20.154.34 while
`
`it was on that LAN. Suppose also that it is desirable to transfer that host to
`
`LAN1 as shown.
`
`20
`
`In the standard system, it would not be possible for any messages to
`
`reach HI, because its address does not match LANI's address. For HI to be
`logically connected to the system, either its address would have to be changed
`
`to match that of LANI (so that it would effectively be a new host), or LANI
`
`and LAN6 would have to be coupled together by a bridge (so that HI could
`
`25
`
`still be reached by router R2), or some form of address conversion would have
`
`to be provided.
`
`In the present system, however, messages can reach HI. This is because
`
`all the routers' tables (ie. both link and interface tables) contain the individual.
`
`30
`
`addresses of all hosts (of the level I area) in full; they do not now contain the
`
`subnet addresses as such.
`
`SONY EXHIBIT 1003- Page 588
`
`ReexamFH_000588
`
`
`
`30
`
`Thus router Rl will contain the address 32.20.154.34 in its interface
`
`table for interface IFI, so that it can forward a message for HI reaching it.
`
`from another router (or from another of its interfaces). Similarly, the link
`
`tables of R2 and R3 will contain the address 32.20.154.34 in full, so that any
`
`5
`
`message for HI reaching either of those routers can be forwarded to router Rl
`
`(assuming that for some reason, messages are not passed to it from router R2
`
`through the extended LAN network of the 2 LANs LAN2 and LANI).
`
`In the standard system, router R2 would contain the address 32.20.154
`
`10
`
`of LAN6 in one of its interface tables, and would capture all messages to any
`
`host with that as the first 3 bytes of its address.
`
`In the present system,
`
`however, router R2 contains only the addresses of the individual hosts attached
`to it, not the subnet address as such. It will therefore not capture any messages
`
`to host HI, ie. to address 32.20.154.34, and will therefore not interfere with
`
`15
`
`the correct routing of messages to that host.
`
`Fig. I also shows a second host, host H9, which has migrated, in this
`
`case from LANI to LAN4. Router Rl's interface table for interface IF2
`
`contains the address (32.17.52.47) of this host, and routers R2 and R3 contain
`
`20
`
`this address in their link tables LK12 and LK13, so that messages to this host
`
`from LANs attached to R2 and R3 will reach it as desired.
`
`There is however a complication if a host such as H2 on H9's original
`
`or "home" subnet wants to send a message to it. H2 finds that its own subnet
`
`25
`
`address is the same as H9's subnet address, and therefore sends an ARP request
`
`to H9 on LANI (hosts' behaviour is unchanged from in the standard system).
`
`As discussed above, the present routers listen to all ARP requests from
`
`hosts on their interfaces, to detect ARP requests for migrated hosts. When a
`
`30
`
`router detects an ARP request, it checks the address of the destination host
`
`SONY EXHIBIT 1003- Page 589
`
`ReexamFH_000589
`
`
`
`31
`
`against the contents of its tables (both the interface tables and the link tables).
`If the destination host is on the same interface as the source host, the router
`ignores the ARP request (the destination host will respond to the ARP request
`with an ARP response and message transmission will proceed normally). But
`if the destination is not on the same interface as the source, the router responds
`
`with a proxy ARP response which includes its own MAC identifier. The
`
`source will then send the message to the router, and the router then forwards
`the message to the actual location of the destination.
`
`Thus router Rl will detect the ARP request from host H2 for host H9,
`find that host H9 is not on interface IFl, and return a proxy ARP response to
`H2. H2 will then send the message to the router, which will pass it to interface
`IF2 so that it reaches H9.
`
`Ifhost H2 has previously been in communication with host H9 over their
`original common LAN, H2 will of course still have H9's MAC address in its
`connection table, and will continue to use that MAC address when trying to
`send messages to H9; and when H9 migrates, H2 will find that H9 has
`apparently disappeared. H2 will thereupon flush its connection table (or at least
`the entry for H9), and attempt to re-open communication with H9 by sending
`an ARP request. Router Rl will return a proxy ARP response to this, as just
`
`discussed, and communication with H9 will therefore be re-established.
`
`5
`
`10
`
`15
`
`20
`
`Fig. 2 shows the general logical organization of the preferred form of
`modified (present) router, which we may take as router Rl.
`
`25
`
`There is a plurality of link registers 10, one per link, for receiving
`messages (including LSPs) coming in over links from other -routers and for
`holding messages to be transmitted over those links. There is a plurality of
`
`30
`
`interface registers 11, one per interface, for receiving messages coming in over
`
`SONY EXHIBIT 1003- Page 590
`
`ReexamFH_000590
`
`
`
`32
`
`the router's interfaces and for holding messages to be transmitted over those
`
`interfaces. There is a plurality of link table stores 12, one per link, for storing
`
`the link tables discussed above. There is a plurality of interface table stores 13,
`
`one per interface, for storing the interface tables discussed above. The link and
`
`5
`
`interface registers 10 and 11 are coupled to switching circuitry 15.
`
`Each of the link: registers 10 and interface registers 11 has a header
`
`section lOA, IIA respectively for containing header information including, for
`
`example, the source and destination addresses and (in the case of messages in
`
`10
`
`the interface registers) MAC identifiers. When a message is received in one
`
`of these registers, its destination address is compared by a comparator 14 with
`
`the addresses in the link and interface tables and moved from its initial register
`
`to the appropriate register for output, ie. from a link register to another link:
`
`register, from a link register to an interface register, or from an interface
`
`IS
`
`register to an interface register.
`
`In addition, if the message is moved into an
`
`interface register, the MAC identifier of the destination is copied over line 16
`
`from the interface table into the header section of the interface register.
`
`(In practice, the messages may be stored in a common memory, with
`
`20
`
`pointers being used to identify different memory areas as the different registers,
`
`and the movement of a message from one register to another being achieved by
`
`changing the pointers. Also, the headers may be processed separately from the
`
`bodies of the messages.)
`
`25
`
`The interface registers 11 are also coupled to an ARP unit 30. All ARP
`
`~.
`
`requests on the LANs attached to the interfaces are received by the router, ie.
`
`are written into the interface registers 11. When an ARP request is so
`
`received, comparator 14 compares the host destination address in its header
`
`with the host addresses in the link tables 12 and the interface tables 13.
`
`30
`
`SONY EXHIBIT 1003- Page 591
`
`ReexamFH_000591
`
`
`
`33
`
`If the destination is not in the interface table for the interface on which
`the ARP request was received, ie. is in some other interface table, or in a link
`
`table, then the comparator 14 sends a signal to the ARP unit 30, which then
`
`converts the ARP request in the interface register to a proxy ARP response.
`
`This ARP response includes the router's address and MAC identifier, which are
`stored in a router address and MAC identifier store 17 and are copied into the
`header into of the interface register for return to the host as the ARP response.
`
`If the destination is in the interface table for the interface on which the
`
`ARP request was received, then the router makes no response. However, for
`all ARP requests which it receives, the router checks whether the source is
`listed in the interface table for the interface on which the ARP request was
`received. If it is not, then it updates its tables by adding the source's address
`
`to the appropriate interface table and deleting it from any other tables which it
`is in. In addition, the host's address (ie. the full address) is passed (over line
`21) to an LSP processor 20.
`
`A polling unit 25 is also coupled, through the switching circuitry 15, to
`the header sections llA of the interface registers 1I. The polling unit 25
`perfonns two functions, under the control of a timer 26 to which it is coupled.
`
`First, the polling unit is coupled to the interface tables 13, and selects
`
`each entry in the interface tables in turn for verification. For this, the address
`of each end-station in tum is copied into the appropriate one of the interface
`registers 11 and sent out as an ARP request. The MAC identifier in the
`
`response is passed back to the interface table and compared therein with the
`stored MAC identifier, to verify the entry. If verification fails (after a suitable
`
`number of retries), the table entry is deleted and the address of the deleted host
`is passed to the LSP processor 20.
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`SONY EXHIBIT 1003- Page 592
`
`ReexamFH_000592
`
`
`
`34
`
`Second, the polling unit is also coupled to an address space store 27,
`
`which is set to contain the address space of the (levell) system. Under control
`
`of the timer 26, the polling unit 25 works sequentially through all addresses of
`
`the address space. Addresses which are already in the interface tables are
`
`5
`
`filtered out. The remaining addresses are passed, in sequence, to each of the
`
`interface registers for sending out an ARP request, to see whether a host with
`
`that address exists. If it does, then the address and MAC identifier in the ARP
`response are passed to the appropriate interface table and to the LSP processor
`
`20.
`
`10
`
`15
`
`Turning now to the LSP processor 20, this receives the addresses of
`
`hosts newly discovered by the router and of hosts which dis.appear from the
`router's interfaces.
`It constructs LSP options containing these addresses,
`
`assembles them into LSPs, and passes them. to the set of link registers 10 for
`transmission to other routers. This processor 20 also processes LSP options
`received by the link registers 10 from other routers, updating the entries in the
`
`corresponding link table 12 by adding and/or deleting entries appropriately.
`The LSP processor 20 is coupled to an LSP option memory 22 in which LSP
`
`this memory
`options of the new type discussed above are constructed;
`comprises a header section 22A, an address section 22B for the addresses of the
`
`20
`
`LSP, and a general information section 22C. This memory is used to assemble
`
`LSP options of the new type which are to be sent out by the router, and to
`store incoming new type options received from other routers ready for analysis
`and transfer of their contents into the link tables 12.
`
`25
`
`In the system shown in Fig. 1, each router is coupled to every other
`
`router.
`
`In general, however, this will not always be so. LSP options must
`
`therefore be forwarded throughout the level 1 area. The LSP processor is
`
`responsible for this; it causes an incoming LSP option to be copied to all other
`
`30
`
`link registers 10 for forwarding (as parts of LSPs) to other routers. Various
`
`SONY EXHIBIT 1003- Page 593
`
`ReexamFH_000593
`
`
`
`35
`
`techniques can be used to prevent the unlimited circulation and multiplication
`of LSP infonnation.
`
`SONY EXHIBIT 1003- Page 594
`
`ReexamFH_000594
`
`
`
`36
`
`Claims
`
`1.
`
`A digital communication system comprising a network of routers linked
`
`together by links and having interfaces with local area networks (LANs)
`
`5
`
`coupled to them, and operating under a protocol under which each LAN has a
`
`subnet address, and each host on a LAN has the subnet address as the high(cid:173)
`
`order part of its own address, each router containing a set of interfacelLAN
`
`tables listing the low-order address portions of the addresses of the hosts
`
`attached to the LAN plus the MAC (medium access control) identifiers of those
`
`10
`
`hosts, and a set of link tables listing the subnet addresses of the LANs
`
`reachable through those links, wherein:
`
`both the interface tables and the link tables in the routers contain the full
`
`addresses of all hosts reachable through those interfaces and links;
`
`the routers contain means for detecting ARP (address resolution protocol)
`
`15
`
`requests from a source host for a destination host having the same subnet
`
`address as the source host but not on the same interface, and returning a proxy
`
`ARP response giving the router's identification; and
`
`the routers contain means for interrogating the interfaces for unknown
`
`hosts.
`
`20
`
`2.
`
`A digital communication system according to claim 1 wherein the means
`
`for interrogating the interfaces comprises polling means.
`
`3.
`
`A digital communication syst~m according to claim 2 wherein the polling
`
`25
`
`means include timing means causing the polling means to perform polling for
`
`~
`
`unknown hosts.
`
`4.
`
`A digital communication system according to claim 3 wherein each
`
`router contains an address space.store settable to contain the address space of
`
`30
`
`the system.
`
`SONY EXHIBIT 1003- Page 595
`
`ReexamFH_000595
`
`
`
`37
`
`5.
`
`A digital communication system according to claim 2 wherein the polling
`
`means of a router poll for unknown hosts is in response to the router receiving
`
`a message for an unknown destination host, and the message is passed through
`
`the network of routers until the destination host is located.
`
`5
`
`6.
`
`A digital communication system according to any previous claim wherein
`
`each router contains an LSP option memory for assembling, storing, and
`
`analyzing LSP options, the LSP option memory comprising a header section,
`
`an address section capable of storing a plurality of addresses, and a general
`
`10
`
`section.
`
`7.
`
`A method of ope