USOO7336621B2
`
`(12) United States Patent
`Bennett
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7,336,621 B2
`Feb. 26, 2008
`
`(54) METHOD AND APPARATUS FOR TESTING
`AN PNETWORK
`(75) Inventor: Jon Claude Russell Bennett, Sudbury,
`MA (US)
`
`(*) Notice:
`
`(73) Assignee: General Instrument Corporation,
`Horsham, PA (US)
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 848 days.
`(21) Appl. No.: 10/648,724
`
`(22) Filed:
`
`Aug. 25, 2003
`
`(65)
`
`Prior Publication Data
`US 2004/0090921 A1
`May 13, 2004
`O
`O
`Related U.S. Application Data
`(60) Provisional application No. 60/421,303, filed on Oct.
`25, 2002.
`
`(51) Int. Cl.
`(2006.01)
`H04L 2/26
`(2006.01)
`HO4L 12/28
`(52) U.S. Cl. ....................................... 370/252; 370/389
`
`(56)
`
`(58) Field of Classification Search ..................... None
`See application file for complete search history.
`References Cited
`U.S. PATENT DOCUMENTS
`6,978,223 B2 * 12/2005 Milliken ..................... TO2, 182
`2004/0062267 A1* 4/2004 Minami et al. ............. 370/463
`2005/00890 16 A1* 4/2005 Zhang et al. ............... 370,351
`OTHER PUBLICATIONS
`McGregor, IPMP draft-mcgregor-ipmp-00.txt, Feb. 2002.*
`* cited by examiner
`Primary Examiner Huy D. Vu
`Assistant Examiner—Clemence Han
`(74) Attorney, Agent, or Firm—Larry T. Cullen
`
`ABSTRACT
`(57)
`The practice and need for active network measurement is
`well established, however, current tools are not well suited
`to this task, mostly because the protocols which they employ
`have not been designed for measurement of the modern
`Internet. The IP Measurement Protocol (IPMP) is based on
`packet-probes, and is designed to allow routers to participate
`in measurements by the insertion of path information as the
`probe passes between a pair of hosts.
`
`16 Claims, 12 Drawing Sheets
`
`
`
`receiving an IPMP packet constructed by a
`measurement host, which IPMP packet includes
`instructions for a recipient of the IPMP packet
`
`examining a contents of the PMP packet for
`instructions before forwarding the PMP packet by a
`network device
`
`processing the IPMP packet in accordance with the
`instructions
`
`Cloudflare - Exhibit 1074, page 1
`
`

`

`U.S. Patent
`
`Feb. 26, 2008
`
`Sheet 1 of 12
`
`US 7,336,621 B2
`
`FIG 1
`
`
`
`measurement host constructs an IPMP request
`packet, in so doing sets all words from end of data
`field to end of echo request packet to zero; echo
`request packet includes instructions for recipient
`
`13
`
`14
`
`
`
`
`
`When iPhi Pecino reply packet airiv
`recomputed
`
`ls checksum correct?
`
`YE
`
`
`
`
`
`discard PMP
`echo reply packet
`
`
`
`Analyze echo reply
`packet for performance
`information
`
`Cloudflare - Exhibit 1074, page 2
`
`

`

`U.S. Patent
`
`Feb. 26, 2008
`
`Sheet 2 of 12
`
`US 7,336,621 B2
`
`FIG 2
`
`When a host receives a packet with the PMP
`packet option packet type field set to Echo Redirect
`Request, host acts as redirecting measurement host
`
`
`
`YES
`
`Does Echo
`Redirect Request packet include Redirect
`Options data section?
`
`NO
`return packet to original measurement host with
`Error Return section with error value indicating
`Missing Required Data Elements
`
`2
`
`22
`
`Does
`Host require authenticated
`edirect requests
`
`23
`YES
`
`24
`
`
`
`
`
`
`
`S
`
`Security Option
`aid
`NO
`return packet to origina
`measurement host With
`Error Return section
`indicating Security Option
`Relected
`
`
`
`
`
`
`
`s
`
`cho Redirect Reques
`packet include Redirect
`Security Option data
`section?
`
`return packet to origina
`measurement host with
`Error Return section
`indicating Security Option
`Recuired
`
`
`
`
`
`Construct New PMP
`Echo Request Packet
`(see FIG 3)
`
`Cloudflare - Exhibit 1074, page 3
`
`

`

`U.S. Patent
`
`Feb. 26, 2008
`
`Sheet 3 of 12
`
`US 7,336,621 B2
`
`
`
`FIG 3
`
`Copy fields from Redirect Options data section
`element of original packet into header
`
`Insert Redirection Host dentification Data data
`Section element, if needed
`
`Copy Measurement Host identification Data data
`section element, if present, in original packet into
`new packet
`
`Copy Source Address and Port from original packet
`into an Original Sender data section element
`
`Set PMP packet Options, Packet Type field to
`Redirected Echo Request
`
`zero remainder of packet
`
`set Path Pointer
`
`compute PMP packet checksum
`
`-34
`
`35
`
`36
`
`37
`
`38
`
`Cloudflare - Exhibit 1074, page 4
`
`

`

`U.S. Patent
`
`Feb. 26, 2008
`
`Sheet 4 of 12
`
`US 7,336,621 B2
`
`FIG 4
`
`Start
`
`40
`When a host receives a packet with the PMP
`packet option packet type field with a value
`indicating a Redirected Echo Reply packet, the host
`acts as a redirecting measurement host
`
`
`
`NO
`
`Does
`host require authenticated redirect
`requests?
`ed
`
`YES
`
`4.
`
`42
`
`
`
`NO
`
`zero out any path
`records E. and
`hR E.
`ost wil Error Return
`section indicating
`Security Option Required
`NO
`
`Redirected Echo
`Reply packet include
`Redirect Security Option
`data
`Section
`
`YES
`
`43
`
`YES
`
`Does
`Redirected Echo Rep
`packet include Original
`Sender
`data section
`
`44
`
`is
`Security Option
`aid?
`
`49a
`
`return packet to echo
`host with an Error Return
`section indicating
`Security Option Rejected
`
`Copy Original Sender
`AddressPort to
`Destination Address and
`Port fields of header
`
`return packet to echo host
`with error value indicating
`Missing Required Data
`Sements
`
`et (PMP packet option Packet Type field to wa?ue indicating an Echo Redirec
`Reply packet
`
`Set PMP packet option Record Path Record field to 0
`
`
`
`Set TTL based on PMP packet option Reverse Path TT
`field
`
`C stop
`
`49c
`
`49
`
`d
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Cloudflare - Exhibit 1074, page 5
`
`

`

`U.S. Patent
`
`Feb. 26, 2008
`
`Sheet 5 of 12
`
`US 7,336,621 B2
`
`FIG 5
`
`On receipt of the IPMP Echo Request packet the
`echoing system constructs the echo reply packet
`from the echo request packet by:
`
`
`
`51
`
`52
`
`55
`
`57
`
`is Checksum Walid?
`
`5.3a
`
`ls PMP
`packet option Toggle Record
`Path set to 17
`
`O
`N
`
`O
`ls
`PMP packet option Swap Faux N
`Ports set to 1
`YES
`
`56
`
`NO
`
`ls
`the Packet Type field set
`to O2
`YES
`
`s
`the Packet Type field set
`to 4?
`
`
`
`schedule the packet for
`forwarding taking
`account of the Faux P
`type field if appropriate.
`
`59c
`
`59a
`
`
`
`53)
`
`53C
`
`55.
`
`57
`
`58b.
`
`
`
`
`
`
`
`
`
`59
`
`
`
`data section with value
`indicating Bad Checksum,
`may require moving any
`path records already
`Dresent or drop the packet.
`
`-
`optionary a
`p
`o
`
`
`
`toggle value of Record
`Path Record field of
`PMP packet options
`
`-
`
`swap the values of the
`Faux Sourcel Destination
`Port fields
`
`Set the Packet Type field
`to
`
`et the Packet Type field
`
`set TTL according to
`Reverse Path TTL option
`
`calculate the PMP
`packet checksum
`
`Cloudflare - Exhibit 1074, page 6
`
`

`

`U.S. Patent
`
`Feb. 26, 2008
`
`Sheet 6 of 12
`
`US 7,336,621 B2
`
`FIG 6
`
`receiving an IPMP packet constructed by a
`measurement host, which IPMP packet includes
`instructions for a recipient of the IPMP packet
`
`examining a contents of the PMP packet for
`instructions before forwarding the PMP packet by a
`network device
`
`
`
`
`
`
`
`
`
`processing the PMP packet in accordance with the
`instructions
`
`61
`
`62
`
`6 3.
`
`Cloudflare - Exhibit 1074, page 7
`
`

`

`U.S. Patent
`
`Feb. 26, 2008
`
`Sheet 7 of 12
`
`US 7,336,621 B2
`
`FIG 7
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`transmitting from a measurement host to a first remote
`network device an IPMP packet requesting a
`measurement test of a link between the first remote
`network device and a second remote network device
`
`receiving by the first remote network device the PMP
`measurement test request packet;
`
`performing a measurement test of the link between the
`first remote network device and the second remote
`network device by sending an IPMP redirected echo
`request packet to the second remote network device
`from the first remote network device
`
`receiving an IPMP redirected echo request packet by
`the second reinete network device, which includes
`instructions for a recipient of the IPMP redirected echo
`request packet, and creating an IPMP echo reply
`packet and including related information in the PMP
`echo reply packet based on the instructions in the PMP
`redirected echo request packet
`
`
`
`processing an IPMP echo reply packet received by the
`first remote network device
`
`forwarding information included in the PMP echo reply
`packet to the measurement host
`
`71
`
`72
`
`73
`
`74
`
`75
`
`76
`
`Cloudflare - Exhibit 1074, page 8
`
`

`

`U.S. Patent
`
`Feb. 26, 2008
`
`Sheet 8 of 12
`
`US 7,336,621 B2
`
`FIG 8
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`receiving by a first remote network device an IPMP
`packet, which includes an address of a measurement
`host device as a source address, an address of a first
`remote network device as a destination address, a flag
`indicating the PMP packet is a redirection request
`packet, and a predetermined field with an address of a
`second remote network device as a redirection address
`to which the PMP packet is to be redirected
`
`81
`
`relabeling by the first remote network device, upon
`receipt of the PMP packet and before forwarding the
`IPMP packet, the source address of the PMP packet
`with the address of the first remote network device
`
`82
`
`relabeling by the first remote network device, upon
`
`M
`
`IPMP packet, the destination address of the PMP
`packet with the address of the second remote network
`device
`
`83
`
`responding to the relabeled PMP packet by the second
`network device by sending a reply IPMP packet to the
`first remote network device by exchanging the source
`address of the received PMP packet and the
`destination address of the received PMP packet in the
`reply IPMP packet
`
`by the first remote
`receiving the reply
`network device and relabeling a destination address of
`the reply IPMP packet with the address of the
`measurement host device before forwarding the reply
`PMP packet to the measurement host device
`
`85
`
`Cloudflare - Exhibit 1074, page 9
`
`

`

`U.S. Patent
`
`Feb. 26, 2008
`
`Sheet 9 of 12
`
`US 7,336,621 B2
`
`FIG 9
`
`
`
`encapsulating the IPMP packet in an IP datagram
`and a predetermined link layer protocol and sending
`the PMP packet into the network from the
`measurement host
`
`
`
`
`
`Oy a
`decrementing the start time to live value
`recipient device of the PMP packet
`
`
`
`forward packet to a next
`network device
`
`YES
`
`decrementing the time to live value by the recipient
`device of the PMP packet
`
`
`
`initiating one or more predetermined actions at one
`or more subsequent recipients of the IPMP packet
`
`
`
`91
`
`92
`
`93
`
`97
`
`98
`
`Cloudflare - Exhibit 1074, page 10
`
`

`

`U.S. Patent
`
`Feb. 26, 2008
`
`Sheet 10 of 12
`
`US 7,336,621 B2
`
`creating an IPMP packet by a measurement host
`
`
`
`
`
`
`
`
`
`
`
`including an instruction in the PMP packet to a
`recipient to process data included in a
`predetermined field in the PMP packet as a data
`packet
`
`encapsulating the PMP packet in an IP datagram
`and a predetermined link layer protocol and sending
`the PMP packet into the network from the
`measurement host
`
`identifying the IPMP packet upon receipt by a
`recipient network device and examining a contents
`of the PMP packet for instructions before forwarding
`the PMP packet by the recipient network device
`
`101
`
`102
`
`103
`
`OA
`
`
`
`106
`
`
`
`processing a contents of the
`predetermined field of the PMP
`packet as a data packet
`
`Does
`recipient's address
`match destination
`address?
`
`105
`
`processing the PMP packet as a measurement
`packet
`
`
`
`Cloudflare - Exhibit 1074, page 11
`
`

`

`U.S. Patent
`
`Feb. 26, 2008
`
`Sheet 11 of 12
`
`US 7,336,621 B2
`
`creating an IPMP packet by a measurement host
`
`including in the PMP packet instructions for a
`recipient of the PMP packet, which instructions
`includes an instruction to a recipient to process the
`PMP packet in accordance with an actual packet
`type and an actual port number included in a first
`and second predetermined location, respectively,
`rather than a faux packet type and a faux port
`number that are included in the actual packet type
`and actual port number fields, respectively
`
`identification indicating the IPMP packet is a faux
`packet type
`
`inserting in a port number field in the IPMP packet a
`faux port number, inserting in a first predetermined
`field in the PMP packet an actual packet type, and
`inserting in a second predetermined field in the
`PMP packet an actual port number
`
`encapsulating the PMP packet in an IP datagram
`and a predetermined link layer protocol and sending
`the PMP packet into the network from the
`measurement host.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`111
`
`12
`
`113
`
`114
`
`115
`
`Cloudflare - Exhibit 1074, page 12
`
`

`

`U.S. Patent
`
`Feb. 26, 2008
`
`Sheet 12 of 12
`
`US 7,336,621 B2
`
`121
`
`Measurement Host
`
`Network. A
`
`
`
`23
`
`
`
`125
`
`Prs. .
`.
`.
`at EY
`126 - Second Remote Device
`
`Firewal or NAT
`
`Cloudflare - Exhibit 1074, page 13
`
`

`

`1.
`METHOD AND APPARATUS FOR TESTING
`AN PNETWORK
`
`US 7,336,621 B2
`
`STATEMENT OF RELATED APPLICATIONS
`
`10
`
`15
`
`30
`
`35
`
`This application claims the benefit of priority to U.S.
`Provisional Patent Application No. 60/421,303, filed Oct.
`25, 2002, entitled “IP Measurement Protocol.”
`This application is also related to copending U.S. patent
`application Ser. No. 10/648,552, entitled “Method For
`Monitoring Performance Of Network Using IP Measure
`ment Protocol Packets.” filed concurrently herewith by the
`same inventor and assigned to the same assignee, which
`application is hereby incorporated by reference as if
`repeated herein in its entirety, including the drawings.
`This application is also related to copending U.S. patent
`application Ser. No. 10/648,622, entitled “Method For Per
`forming Remote Testing Of Network Using IP Measurement
`Protocol Packets, filed concurrently herewith by the same
`inventor and assigned to the same assignee, which applica
`tion is hereby incorporated by reference as if repeated herein
`in its entirety, including the drawings.
`This application is also related to copending U.S. patent
`application Ser. No. 10/648,690, entitled “Method For
`25
`Enabling Initiation Of Testing Of Network Using IP Mea
`surement Protocol Packets.” filed concurrently herewith by
`same inventor and assigned to the same assignee, which
`application is hereby incorporated by reference as if
`repeated herein in its entirety, including the drawings.
`This application is also related to copending U.S. patent
`application Ser. No. 10/648,682, entitled “Method For Con
`verting An IP Measurement Protocol To A Data Packet,”
`filed concurrently herewith by the same inventor and
`assigned to the same assignee, which application is hereby
`incorporated by reference as if repeated herein in its entirety,
`including the drawings.
`This application is also related to copending U.S. patent
`application Ser. No. 10/648,549, entitled “Method For
`Enabling Non-Predetermined Testing Of Network Using IP
`Measurement Protocol Packets, filed concurrently herewith
`by the same inventor and assigned to the same assignee,
`which application is hereby incorporated by reference as if
`repeated herein in its entirety, including the drawings.
`This application is also related to copending U.S. patent
`application Ser. No. 10/648,866, entitled “Method For Using
`Different Packet Type And Port Options Values. In An IP
`Measurement Protocol Packet From Those Used To Process
`The Packet, filed concurrently herewith by the same inven
`tor and assigned to the same assignee, which application is
`hereby incorporated by reference as if repeated herein in its
`entirety, including the drawings.
`This application is also related to copending U.S. patent
`application Ser. No. 10/694,632, entitled “Use Of Synchro
`nized Clocks To Provide Input And Output Time Stamps For
`Performance Measurement Of Traffic Within A Communi
`cations System, filed by at least one of the same inventors
`and assigned to the same assignee, which application is
`hereby incorporated by reference as if repeated herein in its
`entirety, including the drawings.
`
`40
`
`45
`
`50
`
`55
`
`60
`
`FIELD OF THE INVENTION
`
`The present invention is directed to methods and appa
`ratuses for transmitting packet data over computer networks,
`and more particularly to a method and apparatus for trans
`
`65
`
`2
`mitting packet data over a public computer network using
`Internet Protocol, as well as monitoring and testing these
`computer networks.
`
`BACKGROUND
`
`A previous method for sending test packets over a com
`puter network was mostly designed for use in an academic
`setting. As such, this method did not provide for centralized
`monitoring and did not provide mechanisms to Support use
`in a commercial environment. An Existing Internet Protocol
`Measurement Protocol (IPMP) involved having hosts and
`routers place timestamps in packets as they were forwarded,
`but did not provide a sufficiently rich set of methods for
`controlling the recording of timestamps or for providing
`information about the timestamps that would be needed in a
`commercial network.
`The present invention is therefore directed to the problem
`of developing a method and apparatus for enabling routers
`and other network devices to provide measurement infor
`mation to permit proper characterization of a computer
`network.
`
`SUMMARY OF THE INVENTION
`
`The present invention solves these and other problems by
`providing inter alia a method for monitoring propagation
`delays and other properties of paths in Internet Protocol (IP)
`networks. One embodiment of this method includes an
`Internet Protocol Measurement Protocol (IPMP) as aug
`mented and revised herein.
`One exemplary embodiment of the IP Measurement Pro
`tocol (IPMP) of the present invention provides several
`powerful capabilities, including:
`1. Redirection capability, which provides the capability to
`send a packet from a central location to a second host,
`and have that second host re-direct or transmit a
`measurement packet to a third host, receive the reply
`packet and forward the result to the first host.
`2. A Start Time to Live capability, which prevents mea
`surements from being taken until the Time to Live
`(TTL) counter reaches a certain value, which allows for
`measurement of very long paths or use of very short
`packets, in which it is not possible to fit all the
`measurement records into a single measurement
`packet.
`3. The Information Request Proxy, which allows assign
`ment of certain information request tasks to a third
`party. The original IPMP required that Information
`Request packets (which were used to get additional
`information) had to be sent to the same location that
`inserted the measurement records. Many ISPs might
`not want users talking to their routers (or some devices
`may not have addressable IP addresses as they share a
`common IP address with one or more other devices, or
`exist behind firewalls, etc.) so this aspect of the present
`invention provides for designation of an Information
`Proxy that can respond for such devices, and the ability
`to place the proxy's address along with the routers
`address into the timestamp.
`4. Timestamp qualifying information capability in the
`timestamp. The present invention provides additional
`information about how and where the timestamp was
`inserted, along with information about the clock source
`to allow the timestamp to be used without having to
`make any Information Requests. This capability makes
`
`Cloudflare - Exhibit 1074, page 14
`
`

`

`US 7,336,621 B2
`
`10
`
`15
`
`3
`the IPMP more useful for certain applications and
`protocols that do not need to send extra messages to be
`able to use the results.
`5. No timestamp mode capability, which allows for sim
`ply collecting IP addresses without timestamps, e.g.,
`allows the IPMP to be used in place of Traceroute
`(http://www.freesoft.org/CIE/Topics/54.htm,
`http://
`www.nwfusion.com/archive/1999b/0712gear
`head.html) as a more efficient way of finding out of
`about the path between two points.
`According to another aspect of the present invention,
`while the embodiments of the various inventions herein are
`described for Internet Protocol version 4 (IPv4), the embodi
`ments of the various inventions herein are equally applicable
`to Internet Protocol version 6 (IPv6), which has a different
`format for the packet header. The same may be true for
`subsequent versions of Internet Protocol as well.
`According to another aspect of the present invention, one
`embodiment of the IP Measurement Protocol provides that
`a regular data packet be replaced with an IPMP packet,
`which includes in one of the data sections extensions the
`data that would have been in the regular protocol packet,
`plus a flag that says “take this data out and process this data
`as if this data had been the only contents of a non-IPMP
`packet, where the faux ports and packet type were the real
`ports and packet type.” As such, a router or other similar
`device would then process the packet accordingly.
`According to still another aspect of the present invention,
`one embodiment of the IP Measurement Protocol provides
`that instead of using a different packet type, the protocol
`may be carried in Internet Protocol version six (IPv6) header
`extensions. This embodiment takes advantage of certain
`provisions in IPv6 for inserting optional features into
`“header extensions” between the header and the data portion
`of the packet.
`According to yet another aspect of the present invention,
`one embodiment of an IP Measurement Protocol provides a
`more explicit method of requesting information from routers
`along a path traversed by a packet rather than a single flag
`that says: “give me everything.” According to this embodi
`ment, the protocol provides a larger field, or extendable
`field, that permits one to request particular information items
`explicitly.
`Other aspects of the present invention will be apparent to
`those reviewing the following drawings in light of the
`specification.
`
`4
`result of an IPMP redirection request packet from a mea
`Surement host, according to still another aspect of the
`present invention.
`FIG. 5 depicts an exemplary embodiment of a method for
`responding to an IPMP echo request packet, which itself was
`created as a result of an IPMP redirection request packet
`from a measurement host, according to yet another aspect of
`the present invention.
`FIG. 6 shows an exemplary embodiment of a process for
`employing packets sent using the Internet Measurement
`Protocol of the present invention for measuring performance
`of particular links in a network according to still another
`aspect of the present invention.
`FIG. 7 shows an exemplary embodiment of a method for
`performing a remote test of a link between a first remote
`network device and a second remote network device by a
`measurement host according to still another aspect of the
`present invention.
`FIG.8 shows another exemplary embodiment of a method
`for performing a remote test of a link between two remote
`network devices from a measurement host device according
`to yet another aspect of the present invention.
`FIG. 9 shows an exemplary embodiment of a method for
`using the Start Time to Live capability according to yet
`another aspect of the present invention.
`FIG. 10 shows an exemplary embodiment of a process for
`using the IP Measurement Protocol to transmit regular data
`packets according to still another aspect of the present
`invention.
`FIG. 11 shows an exemplary embodiment of a method for
`creating an IPMP packet with a faux port according to yet
`another aspect of the present invention.
`FIG. 12 shows an exemplary embodiment of an apparatus
`for sending and receiving Internet Protocol Measurement
`Protocol (IPMP) packets for measuring performance of
`various links in a computer network, Such as a link between
`a first remote network device and a second remote network
`device, according to still another aspect of the present
`invention.
`
`DETAILED DESCRIPTION
`
`It is worthy to note that any reference herein to “one
`embodiment' or “an embodiment’ means that a particular
`feature, structure, or characteristic described in connection
`with the embodiment is included in at least one embodiment
`of the invention. The appearances of the phrase “in one
`embodiment in various places in the specification are not
`necessarily all referring to the same embodiment.
`One application of the present invention is for perfor
`mance measurement of traffic through the Motorola Broad
`band Service Router (BSR) 64000.
`The present invention can be used to demonstrate to
`Multiple System Operators (MSOs) that BSR delivers prom
`ised Quality of Service (QoS) guarantees. MSOs can use to
`show to subscribers that the MSOS network has delivered
`promised QoS guarantees. This capability allows a hardware
`developer and its customers to prove they are delivering
`advanced services, not just making marketing claims.
`One additional capability includes the ability to redirect
`the packet multiple times, for example, to be able to send it
`out through a firewall and have the packet or echo come
`back through the firewall. FIG. 12 shows an exemplary
`embodiment 120 of an apparatus for sending and receiving
`Internet Protocol Measurement Protocol (IPMP) packets for
`measuring performance of various links in a computer
`network, such as a link between a first remote network
`
`25
`
`30
`
`35
`
`40
`
`45
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 depicts an exemplary embodiment of a method for
`performing a measurement of a remote host by using an
`Internet Protocol Measurement Protocol (IPMP) packet
`according to one aspect of the present invention.
`FIG. 2 depicts an exemplary embodiment of a method for
`responding to an IPMP redirection request packet sent from
`a measurement host according to another aspect of the
`present invention.
`FIG.3 depicts an exemplary embodiment of a method for
`constructing an IPMP echo request packet as part of a
`response to an IPMP redirection request packet from a
`measurement host according to yet another aspect of the
`present invention.
`FIG. 4 depicts an exemplary embodiment of a method for
`responding to an IPMP echo reply packet sent in response to
`an IPMP echo request packet, which itself was created as a
`
`50
`
`55
`
`60
`
`65
`
`Cloudflare - Exhibit 1074, page 15
`
`

`

`US 7,336,621 B2
`
`5
`device 123 and a second remote network device 126. The
`measurement host 121 sends an IPMP packet to the first
`remote network device 123 via network A 122. The first
`network device in turn sends an IPMP packet to the second
`remote network device 126 via network B 124. The second
`remote network device 126 may be behind a firewall 125 or
`a network address translation device.
`A measurement host 121 includes at least a processor and
`a memory. The processor prepares the IPMP packets as
`described above and forwards them to remote devices over
`a first network 122, of which remote devices the processor
`is attempting to determine the performance.
`Furthermore, the present invention includes a computer
`readable media having instructions encoded thereon to cause
`a network device. Such as a server, router, hub, terminal, or
`processor to perform the methods and processes described
`herein.
`Another additional feature adds security option fields for
`allowing the IPMP packets to pass through firewalls by
`putting in a security option that the firewall could use to
`authenticate the packet before allowing the packet to pass
`the same way that the redirecting host does.
`
`IP Measurement Protocol (IMP)
`
`5
`
`10
`
`15
`
`25
`
`6
`Measurement Protocol of the present invention for measur
`ing performance of particular links in a network. Each
`recipient of an IPMP packet upon receiving an IPMP packet
`constructed by a measurement host, which IPMP packet
`includes instructions for a recipient of the IPMP packet
`(element 61) examines a contents of the IPMP packet for
`instructions for the recipient before forwarding the IPMP
`packet (element 62), and then processes the IPMP packet in
`accordance with the instructions, if any (element 63).
`The protocol has been designed so measurement packets
`can be processed with about the same level of computation
`as IP packet forwarding. The protocol is intended to allow
`for easy implementation in hardware/firmware so as to
`provide for highly accurate measurements. It should be
`noted that only the TTL and Timestamp fields in the Path
`Records are dynamic, all the other fields are likely to be the
`same for all the Path Records inserted at a particular
`Stamping location.
`The IPMP has a number of options to allow it to measure
`a number of different properties of the links and devices on
`a path between two endpoints. It is intended that it should be
`practical to process IPMP packets in the same forwarding
`path as normal (non-IPMP) packets without any (significant)
`performance impact. To achieve this it is anticipated that a
`device will pre-compute all but one or two of the compo
`nents of the path record and insert Some combination of
`these components based on the options field of the packet.
`The option fields of the IPMP request packet are defined
`with the objective of allowing a forwarding device to
`determine what, if any, path records should be inserted with
`the minimum amount of logic complexity.
`Remote Measurement
`There are many applications of the IP Measurement
`Protocol where it is sufficient to be able to perform mea
`Surements only on paths originating with the measurement
`host. However, there are also applications, protocols and
`users/operators that would be served by being able to
`measure the properties along paths that originate at hosts
`other than their own.
`Some straightforward examples of Such non-local mea
`surement would be ISP operators wishing to monitor their
`customer's link quality to be able to demonstrate they have
`provided an agreed upon level of service. While the same
`customer may wish to have a third party organization
`perform the same monitoring to provide the customer with
`the same assurances, particularly if their traffic crosses
`multiple provider networks.
`An example of an application/protocol use for non-local
`monitoring might be client copy multicast trees. The source
`of the multicast tree could measure path properties not only
`between the source and the receivers but also from receiver
`to receiver and reform the tree based on the measured
`properties of the paths between the different receivers.
`To avoid hosts having to run many different client/server
`processes for each different entity that wishes to perform
`remote measurement, and to provide a common security
`framework IPMP provides a mechanism to support a remote
`measurement function.
`To make it possible to perform measurements, from a
`remote location, of paths that do not start or end at that
`location, the IPMP provides a mechanism for allowing
`redirection of the IPMP packet. This mechanism provides
`hooks to support methods for authenticating IPMP packets
`to prevent the unauthorized use of the redirection function.
`FIG. 7 shows an exemplary embodiment of a method 70
`for performing a remote test of a link between a first remote
`
`Introduction
`The practice and need for active network measurement is
`well established, however, current tools are not well suited
`to this task, mostly because the protocols which they employ
`have not been designed for measurement of the modern
`Internet.
`ICMP for example, is widely used for measurement
`despite its well-known limitations for this task. These limi
`tations include it being treated differently than other IP
`protocols at routers and hosts. ICMP has also received bad
`press from denial of service attacks and because of the
`number of sites generating monitoring traffic. As a conse
`quence some ISPs disable ICMP even though this potentially
`causes poor performance and does not comply with
`RFC 1009.
`The protocol of the present invention operates as an echo
`protocol allowing packet loss, path length, route, RTT and in
`Some cases, one-way delay measurements to be taken.
`Packets are generated by a measurement host and returned
`by an echoing router or host, known as an echoing system
`herein. The translation of router time stamps to real-time
`time stamps is Supported through a separate information
`request and reply exchange between the measurement sys
`tem and systems that insert time stamps into the echo request
`or reply.
`Current packet probing techniques are not Suited to mea
`Suring packet delay at the router level. Routers often make
`bad measurement targets because they a