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, eg. by a suitable number of retries. A discovery time
`
`of say 500 s (comparable to the ARP time-out), and a polling rate of7 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
`
`LG v. Straight Path, IPR2015-00209
`Straight Path - Ex. 2015 - Page 579
`
`

`
`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.
`
`10
`
`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
`
`15
`
`20
`
`25
`
`30
`
`LG v. Straight Path, IPR2015-00209
`Straight Path - Ex. 2015 - Page 580
`
`

`
`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 subnet
`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, because
`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 standard system.
`
`LG v. Straight Path, IPR2015-00209
`Straight Path - Ex. 2015 - Page 581
`
`

`
`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
`
`information 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
`
`information 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:
`
`LG v. Straight Path, IPR2015-00209
`Straight Path - Ex. 2015 - Page 582
`
`

`
`24
`
`Fig. I 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. I shows a communication system with various typical features. The
`
`system consists of a Ievell network of3 routers Rl-R3 coupled by links LK12,
`LK23, and LK13 (the digits indicating the routers which each link couples
`
`together). This level I 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 LANl (with subnet
`address 32.17 .52) and LAN4 (with sub net address 32.17 .66) coupled to them;
`router R2 has 3 LAN interfaces, with LAN2 (with sub net 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. LANl and LAN2 are connected together in known manner
`
`through a bridge BRl, forming a single extended LAN with two subnet
`
`20
`
`addresses .
`
`. Hosts Hl-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 e1;1d 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
`
`LG v. Straight Path, IPR2015-00209
`Straight Path - Ex. 2015 - Page 583
`
`

`
`25
`
`Host H2. connection table
`
`Router connection:
`R1-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 Rl, 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 LANI, 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 R1, 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 Rl 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 Rl, for example,
`
`would maintain the following interface tables if it were a standard router.
`
`30
`
`LG v. Straight Path, IPR2015-00209
`Straight Path - Ex. 2015 - Page 584
`
`

`
`Router R1 (standard fonnl. interface tables
`
`26
`
`IF1 (interface)
`32.17.52 (subnet address)
`H3-MAC
`5
`32 H2-MAC
`
`32.17.55 (sub net address)
`129 H5-MAC
`
`IF2 (interface)
`32.17.66 (sub net 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 1 network, and those other routers
`
`30
`
`hold that information in their link tables. Thus if router R1 were standard, it
`
`would maintain two link tables as follows.
`
`LG v. Straight Path, IPR2015-00209
`Straight Path - Ex. 2015 - Page 585
`
`

`
`Router Rl (standard form). link tables
`
`27
`
`LK12:
`32.20.154
`32.20.132
`
`(LAN6)
`(LAN3)
`
`LK13:
`32.27.24
`32.17.102
`
`(LAN5)
`(LAN7)
`
`5
`
`10
`
`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.0001xx.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 LK12 and
`
`LK13, 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.)
`
`LG v. Straight Path, IPR2015-00209
`Straight Path - Ex. 2015 - Page 586
`
`

`
`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 Rl will contain:
`
`5
`
`10
`
`Router Rl (modified form). interface table IFl
`
`IFl:
`
`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
`
`LK13:
`32.17.52
`32.17.55
`32.17.66
`
`(LAN I)
`(LAN2)
`(LAN4)
`
`For the modified form of router R3, this link table will contain all the entries
`for router Rl 's interface tables, in the same form as in those interlace tables,
`instead of just the compressed or subnet addresses. Thus router R3 will contain
`
`the following link table for link LK13 in the modified form:
`
`20
`
`25
`
`30
`
`LG v. Straight Path, IPR2015-00209
`Straight Path - Ex. 2015 - Page 587
`
`

`
`Router R3 (modified form). link table LKI3
`
`29
`
`5
`
`LK13:
`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 H1 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
`
`LAN 1 as shown.
`
`20
`
`In the standard system, it would not be possible for any messages to
`
`reach HI, because its address does not match LAN1's address. For H1 to be
`logically connected to the system, either its address would have to be changed
`
`to match that of LANl (so that it would effectively be a new host), or LANI
`
`and LAN6 would have to be coupled together by a bridge (so that Hl 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 Hl. This is because
`
`all the routers' tables (ie. both link and interface tables) contain the individual .
`
`30
`
`addresses of all hosts (of the level 1 area) in full; they do not now contain the
`
`subnet addresses as such.
`
`LG v. Straight Path, IPR2015-00209
`Straight Path - Ex. 2015 - Page 588
`
`

`
`30
`
`Thus router Rl will contain the address 32.20.154.34 in its interface
`
`table for interface IFl, so that it can forward a message for Hl 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 H1 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 LANl).
`
`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. 1 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 LAN1 (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
`
`LG v. Straight Path, IPR2015-00209
`Straight Path - Ex. 2015 - Page 589
`
`

`
`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 R1 will detect the ARP request from host H2 for host H9,
`find that host H9 is not on interface IFI, 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.
`
`If host 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 wiii 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
`25 modified (present) router, which we may take as router Rl.
`
`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
`
`LG v. Straight Path, IPR2015-00209
`Straight Path - Ex. 2015 - Page 590
`
`

`
`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, llA 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
`
`LG v. Straight Path, IPR2015-00209
`Straight Path - Ex. 2015 - Page 591
`
`

`
`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.
`5 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
`
`10 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 11. 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.
`
`15
`
`20
`
`25
`
`30
`
`LG v. Straight Path, IPR2015-00209
`Straight Path - Ex. 2015 - Page 592
`
`

`
`34
`
`Second, the polling unit is also coupled to an address space store 27,
`
`which is set to contain the address space of the (Ievell) 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
`
`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,
`
`15
`
`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
`
`options of the new type discussed above are constructed; this memory
`
`20
`
`comprises a header section 22A, an address section 22B for the addresses of the
`
`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
`
`LG v. Straight Path, IPR2015-00209
`Straight Path - Ex. 2015 - Page 593
`
`

`
`35
`
`techniques can be used to prevent the unlimited circulation and multiplication
`of LSP infonnation.
`
`LG v. Straight Path, IPR2015-00209
`Straight Path - Ex. 2015 - Page 594
`
`

`
`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 interface/LAN
`
`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.
`
`LG v. Straight Path, IPR2015-00209
`Straight Path - Ex. 2015 - Page 595
`
`

`
`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 operating a digital communication system comprising a
`
`network of routers linked together by links and having interfaces with local area
`
`networks (LANs) coupled to them, said method including the steps of:
`
`15
`
`operating the system 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;
`
`providing each router with a set of interface/LAN tables listing the low(cid:173)
`
`order address portions of the addresses of the hosts attached to the LAN plus
`
`20
`
`the MAC (medium access control) identifiers of those hosts, and a set of link
`
`tables listing the subnet addresses of the LANs reachable through those links;
`
`providing both the interface tables and the link tables in the routers with
`
`the full addresses of all hosts reachable through those interfaces and links;
`
`each router, upon detection of ARP (address resolution protocol) requests
`
`25
`
`from a source host for a destination host having the same subnet address as
`
`the
`
`source host but not on the same interface, returning a proxy ARP response
`
`giving the router's identification; and
`
`providing each router with means for interrogating the interfaces for
`
`unknown hosts.
`
`30
`
`LG v. Straight Path, IPR2015-00209
`Straight Path - Ex. 2015 - Page 596
`
`

`
`38
`
`The method of claim 7 including the step of locating unknown hosts by
`8.
`a router by routine systematic polling of predetermined address space.
`
`5
`
`The method of claim 8 including the step of reserving a second
`9.
`predetermined address space for self-announcing hosts which address space is
`not systematically polled by a router.
`
`10. The method of claim 7 including the step of initiating a poll for an
`unknown host in response to a router receiving a message for said unknown
`destination host, and passing the message through the network of routers until
`the destination host is located.
`
`10
`
`-,
`
`LG v. Straight Path, IPR2015-00209
`Straight Path - Ex. 2015 - Page 597
`
`

`
`o 9
`'Oatents Act 1977
`Examiner's report to the Comptroller under Section 17
`(fhe Search report)
`
`Relevant Technical Fields
`
`(i) UK Cl(Ed.M)
`
`,H4P (PPA, PPG)
`
`(ii) lnt Cl (Ed.5)
`
`H04L 12/46, 12/66
`
`Databases (see below)
`(i) UK Patent Office collections of GB, EP, WO and US patent
`specifications.
`
`(ii) ONLINE DATABASES: WPI, INSPEC
`
`Categories of documents
`
`Application number
`GB 9322910.2
`
`Search Examiner
`MRJ P COULES
`
`Date of completion of Search
`7 DECEMBER 1994
`
`Documents considered relevant
`following a search in respect of
`Claims:-
`1-10
`
`X:
`
`Y:
`
`A:
`
`Document indicating lack of novelty or of inventive step.
`
`P:
`
`Document indicating lack of inventive step if combined with
`one or more other documents of the same category.
`
`Document indicating technological background and/or state
`of the art.
`
`