US 8,144,611 B2
`(10) Patent No:
`a2) United States Patent
`Agarwaletal.
`(45) Date of Patent:
`Mar.27, 2012
`
`
`US008144611B2
`
`(54) NETWORK COORDINATE SYSTEMS USING
`IP INFORMATION
`
`(75)
`
`Inventors: Sharad Agarwal, Seattle, WA (US);
`Jacob R. Loreh, Bellevue, WA (US)
`,
`;
`(73) Assignee: Microsoft Corporation, Redmond, WA
`(US)
`
`(*) Notice:
`
`Subject to any disclaimer, the term ofthis
`patent is extended or adjusted under 35
`US.C. 154(b) by 325 days.
`
`(21) Appl. No.: 12/368,844
`
`(22)
`
`Filed:
`
`Feb. 10, 2009
`
`(65)
`
`Prior Publication Data
`
`US 2010/0202298 Al
`
`Aug. 12, 2010
`
`(51)
`
`Int. Cl.
`(2006.01)
`HO4L 12/26
`(52) US. CR ccc 370/252; 370/255; 709/224
`(58) Field of Classification Search.......... 370/241-258;
`709/223—226, 24
`See application file for complete search history.
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`5,115,433 A
`5/1992 Baran
`Es
`7,174,382 B2
`2/2007 Ramanathan etal.
`rNa Bi x eee Madhyasthaetal _—- een
`
`1. 370/252
`2003/0007454 Al*
`1/2003 Shorey......
`
`. 709/224
`2003/0177183 Al*
`9/2003 Cabreraet al.
`
`9/2006 Sharmaetal....
`» 370/254
`2006/0209717 Al*
`3/2007 Haley etal. vvesssisvssenn 709/224
`2007/0050497 A1l*
`2007/0299794 Al
`12/2007 El-Damhougy
`2008/0304421 Al* 12/2008 Ramasubramanian
`etal. cesses 370/251
`6/2009 Winkler etal.
`......0... 709/224
`2009/0144411 Al*
`OTHER PUBLICATIONS
`
`Chan-Tinet al., “Accurate and Provably Secure Latency Estimation
`with Treeple”, NDSS, 2011, all pages.*
`
`Gummadiet al., “Reduced. State Routing in the Internet”, HotNets,
`2004,all pages.*
`Li-Wei Lehman,etal., A Decentralized Network Coordinate System
`for Robust Internet Distance http://ieeexplore.ieee.org/stamp/stamp.
`jsp?arnumber=1611675&isnumber=33849 Last accessed on Nov.
`18, 2008, 7 pages.
`Puneet Sharma,et al., Estimating Network Proximity and Latency
`http://www.hpl-hp.com/personal/Sung-Ju__Lee/abstracts/papers/
`ccr2006.pdf Last accessed on Nov. 18, 2008, 10 pages.
`Xiaohui Shi, A Method for Network Distance Prediction http://www.
`apng.org/9thcamp/Papers/Shi.pdf Last accessed on Nov. 18, 2008, 2
`pages.
`Ananth Rao,et al., Geographic Routing without Location Informa-
`tion http://delivery.acm.org/10.1145/940000/938996/p96-rao pdf?
`key1=938996&key2=856800722 1 &coll=>GUIDE&dI=GUIDE&
`CFID=11029802&CFTOKEN=806640 12 Last accessed on Nov.18,
`2008,13 pages.
`Harsha V. Madhyastha, et al., A Structural Approach to Latency
`Prediction http://www.imconf.net/imc-2006/papers/p9-madhyastha.
`pdf Last accessed on Nov. 18, 2008, 6 pages.
`Impact of BGP Dynamics on Intra-Domain Traffic. http://research.
`microsoft.com/~sagarwal/sigmetrics04.pdf.
`David Anderson,et al., Resilient Overlay Networkshttp://nms.|cs.
`mit.edu/papers/ron-sosp2001 .pdf. Last accessed. on Nov. 20, 2008,
`15 pages.
`Manuel Costa, et al., PIC: Practical Internet Coordinates for Distance
`Estimation —_http://research.microsoft.com/~antr/MS/PIC-ICDCS.
`pdf. Last accessed on Nov. 20, 2008, 10 pages.
`
`(Continued)
`
`Primary Examiner — Jeffrey M Rutkowski
`(74) Attorney, Agent, or Firm — Lee & Hayes, PLLC
`
`(57)
`ABSTRACT
`Systems and methods that improve predictions of network
`latency in network coordinate systems (NCS) based on com-
`bining Internet topology information therewith. Topology
`information can be incorporated into the NCS by system/
`:
`:
`sage
`methodologies represented by geographic bootstrapping;
`autonomous system (AS) correction; history prioritization;
`symmetric updates or a combination thereof. Such can
`improvelatency estimation between nodes whenusinga vir-
`tual coordinate system based on latency measurements
`between nodes.
`
`610
`
`DETERMINE AUTONOMOUSSYSTEM FOR.
`PAIR OF NODES
`
`
`
`16 Claims, 11 Drawing Sheets
`
`“en
`
`Data Co Exhibit 1049
`Data Co Exhibit 1049
`Data Co v. Bright Data
`
`Data Co v. Bright Data
`
`
`630
`|
`iS AUTONOMOU:
`
`
`SYSTEM IDENTICAL
`FORNODES?
`
`
`
`
`4 640
`MODIFY LATENCY NUMBERS BASED ON
`PREDETERMINED FUNCTION
`
`650
`
`‘MITIGATE OVER ESTIMATION OF LATENCY
`IN AUTONOMOUS SYSTEMS
`
`
`
`

`

`US 8,144,611 B2
`
`Page 2
`
`OTHER PUBLICATIONS
`
`Frank Dabek, et al., Vivaldi:A Decentralized Network Coordinate
`System http://pdos.csail.mit.edu/papers/vivaldi:sigcomm/paper.pdf.
`Last accessed on Nov. 20, 2008, 12 pages.
`Frank Dabek, et al., Designing a DHT for low latency and high
`throughput —http://pdos.csail.mit.edu/papers/dhash:nsdi/paper.pdf.
`Last accessed on Nov. 20, 2008, 14 pages.
`Marcel Dischinger, et al., Characterizing residential broadbandnet-
`works. http://www.imconf.net/imc-2007/papers/ime137.pdf Last
`accessed on Nov. 20, 2008, 14 pages.
`P. Francis, et al., A global Internet host distance estimation service
`http://idmaps.ececs.umich.edu/papers/ton0l.pdf Last accessed on
`Nov. 20, 2008, 14 pages.
`Michael J. Freedman,et al., Geographic locality of IP prefixes. http://
`www.usenix.org/event/imc05/tech/full__papers/freedman/freed-
`man.pdf Last accessed on Nov. 20, 2008, 6 pages.
`Michael J. Freedman,et al., OASIS: Anycast for any service. http://
`www.coralcdn.org/docs/oasis-nsdi06.pdf Last accessed on Nov. 20,
`2008, 14 pages.
`Saikat Guha, et al., Characterization and measurement of TCPtra-
`versal through NATs and firewalls. http://nutss.gforge.cis.cornell.
`edu/pub/imc05-tepnat/ Last accessed on Nov. 20, 2008, 21 pages.
`Ivan Herman,et al., Graph visualization and navigation in informa-
`tion
`visualization:
`a
`survey
` http://homepages.cwi.nl/~ivan/
`AboutMe/Publications/StarGraphVisulnInfoVis.pdf. Last accessed
`on Nov. 20, 2008, 21 pages.
`Jonathan Ledlie,et al., Network coordinates in the wild http://www.
`eecs.harvard.edu/~syrah/nc/wild06-tr.pdf. Last accessed on Nov.20,
`2008, 14 pages.
`Youngki Lee, et al., Measurement and estimation of network QoS
`among peer Xbox 360 gameplayers http://icme2007.org/~padhye/
`publications/xbox08.pdf Last accessed on Nov. 20, 2008, 10 pages.
`Cristian Lumezanu, et al., PeerWise discovery and negotiation of
`faster paths http://conferences.sigcomm.org/hotnets/2007/papers/
`hotnets6-final1 17.pdf Last accessed on Nov. 20, 2008, 6 pages.
`Harsha V. Madhyastha, et al., iPlane: An information plane for dis-
`tributed. services. http://iplane.cs.washington.edu/osdi06.pdf Last
`accessed on Nov. 20, 2008, 14 pages.
`Maxmind. Geolocation and online fraud prevention from Max-Mind
`http://www.maxmind.com/. Last accessed on Nov. 20, 2008, | page.
`David Moore,et al., Where in the world is netgeo.caida.org? http://
`www.caida.org/publications/papers/2000/inet_netgeo/inet_netgeo.
`html Last accessed on Nov. 20, 2008, 14 pages.
`Donald R. Morrison, Patricia—practical algorithm to retrieve infor-
`mation coded in alphanumeric. http://delivery.acm.org/10.1145/
`330000/321481/p514-morrison.pdf?key1=32 148 1 &key2=
`276171722 1&coll=GUIDE&dI=GUIDE&CFID=1 1832998&
`CFTOKEN=86703012 Last accessed on Nov. 20, 2008, 21 pages.
`
`T.S. Eugene Ng, et al., Predicting Internet network distance with
`coordinates-based approaches http://www.cs.rice.edu/~eugeneng/
`papers/INFOCOM02.pdf Last accessed on Nov. 20, 2008, 10 pages.
`Venkata N. Padmanabhan, et al., An investigation of geographic
`mapping techniques for Internet hosts. http://research.microsoft.
`com/~padmanab/papers/sigcomm2001.pdf Last accessed on Nov.
`20, 2008, 13 pages.
`Marcelo Pias, et al., Lighthouses for scalable distributed. location.
`http://research.microsoft.com/~tharris/papers/2003-iptps.pdf Last
`accessed on Nov.20, 2008, 13 pages.
`RaviPrasad,et al., Effects of interrupt coalescence on network mea-
`surements. http://www.pam2004.org/papers/265.pdf Last accessed
`on Nov.20, 2008, 10 pages.
`Sylvia Ratnasamy, et al., Topologically-aware overlay construction
`and
`server
`selection.
`_http://berkeley.intel-research .net/sylvia/
`infocom02.pdf Last accessed on Nov. 20, 2008, 10 pages.
`Jennifer Rexford,et al., BGP routing stability ofpopular destinations
`hitp://www.cs.princeton.edu/~jrex/papers/imw02.pdf Last accessed.
`on Nov.20, 2008, 6 pages.
`J. Rosenberg,et al., STUN—simple traversal of user datagram pro-
`tocol (UDP) through network addresstranslators (NATs) http://www.
`rfc-archive.org/getrfc.php?rfe=3489 Last accessed on Nov. 20, 2008,
`34 pages.
`Route Views Project. University of Oregon. http://www.routeviews.
`org/ Last accessed on Nov. 20, 2008, 5 pages.
`Yuval Shavitt, et al., Big-Bang Simulation for embedding network
`distances in Euclidean space http://www.ieee-infocom.org/2003/pa-
`pers/47_02.PDF Last accessed on Nov. 20, 2008, 11 pages.
`Micah Sherr,et al., Veracity: A fully decentralized service for secur-
`ing
`network
`coordinate
`systems.
`http://www.cs.toronto.edu/
`iptps2008/final/36 pdf Last accessed on Nov. 20, 2008, 6 pages.
`Bernard Wong,et al., Meridian: A lightweight network location
`service without virtual coordinates. http://conferences.sigcomm.org/
`sigcomm/2005/paper-WonSli.pdfLast accessed on Nov.20, 2008, 12
`pages.
`Golan Yona, et al., ProtoMap: automatic classification of protein
`sequences and hierarchy of protein families http://ai.stanford.
`edu/~serafim/CS374_2004/Papers/Yona_ProtoMap.pdf
`Last
`accessed. on Nov. 20, 2008, 19 pages.
`David John Zage, et al., On the accuracy of decentralized virtual
`coordinate systems in adversarial networks http://www.cs.purdue.
`edu/homes/zagedj/docs/ccs050-zage.pdf Last accessed on Nov. 20,
`2008, 11 pages.
`Han Zheng. et al., Internet routing policies and round-trip times
`http://www.pamconf.org/2005/PDF/343 1024 | pdf Last accessed on
`Nov.20, 2008, 14 pages.
`Gil Zigelman,et al., Texture mapping using surface flattening via
`multi-dimensional
`scaling. —_http://www.cs.technion.ac.il/users/
`wwwb/cgi-bin/tr-get.cgi/2000/CIS/CIS-2000-01.pdf Last accessed
`on Nov.20, 2008, 9 pages.
`
`* cited by examiner
`
`

`

`U.S. Patent
`
`Mar.27, 2012
`
`Sheet 1 of 11
`
`US 8,144,611 B2
`
`001
`
`/*
`
`col
`
`
`
`eeeeeee
`
`ONITAGOWADOTOOL
`
`WHLSAS
`
`ALVNIGHOO9D
`
`NOLLVNWOLNV WHLSAS
` NOILVZILIaOrdd
`SHOMLAN —
`
`
`
`SHIVdd)OPaLAIWANAS
`
`AYOLSIA
`
`JIHdVuaDOdo
`
`NOILOHAAOODWALLSA
`
`DNiddVals.LOO
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Mar. 27, 2012
`
`Sheet 2 of 11
`
`US 8,144,611 B2
`
`J200
`
`RTT
`
`30 ms
`
`B ee
`6wo!
`
`s
`
`ay
`
`A ”
`
`®
`wo!
`
`(Prior Art)
`Fig. 2
`
`

`

`U.S. Patent
`
`Mar.27, 2012
`
`Sheet 3 of 11
`
`US 8,144,611 B2
`
`00¢€ZA
`
`OI’Se?
`
`covesosea3‘ae007
`
`octe
`
`cogse°
`
`iene
`
`a0aoae*
`
`OO0T
`
`008
`
`009
`
`OOP
`
`
`
`
`
`000cI0000100080009000P0007
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Mar. 27, 2012
`
`Sheet 4 of 11
`
`US 8,144,611 B2
`
`
`
`
`
`ONIddVULSLOO”OIHdVaDOAD
`
`
`
`/®LNANOdWODNOILOIGHad
`
`OIV
`
`(surddew
`
`WALYAANOONOLLVOOT
`
`ALVNIGCYOOD
`
`WHLSAS
`
`AAOMLAN OV
`
`HSaddAda
`
`ONIddVAN
`
`
`
`

`

`US 8,144,611 B2
`
`SSI
`
`U.S. Patent
`
`Sheet 5 of 11
`
`Mar.27, 2012
`
`svexsveTHIN«<LSVTwaa4YWhaATIN8a0aTINws‘wy
`
`

`

`U.S. Patent
`
`Mar. 27, 2012
`
`Sheet 6 of 11
`
`US 8,144,611 B2
`
`x 600
`
`610
`
`DETERMINE AUTONOMOUSSYSTEM FOR
`
`PAIR OF NODES
`
`620
`
`SYSTEM IDENTICAL
`
`FOR NODES?
`
`
`IS AUTONOMOUS
`
`YES
`
`Lo 640
`PREDETERMINED FUNCTION
`
`MODIFY LATENCY NUMBERS BASED ON
`
`650
`
`MITIGATE OVER ESTIMATION OF LATENCY
`
`IN AUTONOMOUSSYSTEMS
`
`Fig. 6
`
`

`

`U.S. Patent
`
`Mar. 27, 2012
`
`Sheet 7 of 11
`
`US 8,144,611 B2
`
`io
`
`710
`
`STORE HISTORY OF RTT
`
`LATENCY PREDICTION
`
`ACCESS STORE TO OBTAIN PRIOR PROBES
`
`& LEVERAGE STORED HISTORY FOR
`
`730
`
`DIRECTLY USE RESULTS INSTEAD OF
`
`DISTANCES
`
`PREDICTIONS BASED ON COORDINATE
`
`740
`
`IMPLEMENTIP INFORMATION THUS
`
`LEVERAGED AS PART OF NCS
`
`Fig. 7
`
`

`

`U.S. Patent
`
`Mar. 27, 2012
`
`Sheet 8 of 11
`
`US 8,144,611 B2
`
`a 800
`
`810
`
`RTT FROM NODE A TO NODE BIS
`MEASURED
`
`MEASUREMENT RESULT
`
`NODEA NOTIFIES NODE B OF
`
`830
`
`NODE A UPDATES COORDINATES
`
`840
`
`NODE B UPDATES COORDINATES
`
`Fig. 8
`
`

`

`U.S. Patent
`
`Mar. 27, 2012
`
`Sheet 9 of 11
`
`US 8,144,611 B2
`
`J 900
`
`INFERENCE
`
`COMPONENT
`
`PREDICTION COMPONENT
`
`|
`
`| | |
`
`| | F
`
`NETWORK
`
`COORDINATE
`SYSTEM
`
`TOPOLOGY
`
`MODELING
`SYSTEM
`
`ig. 9
`
`

`

`U.S. Patent
`
`Mar. 27, 2012
`
`Sheet 10 of 11
`
`US 8,144,611 B2
`
`potean, 1028
`
`eana (1030
`!
`i Applications }
`JO peuKa, 1032
`|} Modules}
`
`Lecweerenereecnnt!
`
`Processing
`Unit
`
`Output
`Device(s)
`
`1040
`
`Input
`Device(s)
`
`1036
`
`Communication i
`Connection(s)
`
`Network
`
`Interface
`
`1048
`
`
`
`Remote
`Computer(s)
`
`Memory
`Storage
`
`1046
`
`Fig. 10
`
`

`

`U.S. Patent
`
`Mar. 27, 2012
`
`Sheet 11 of 11
`
`US 8,144,611 B2
`
`JL 1100
`
`
`
`CLIENT(S)
`
`1110
`
`1130
`
`SERVER(S)
`
`
`
`
`CLIENT
`
`DATA
`
`
`STORE(S)
` COMMUNICATION
`
`SERVER
`DATA
`STORE(S)
`
`FRAMEWORK
`
`Fig. 11
`
`

`

`US 8,144,611 B2
`
`1
`NETWORK COORDINATE SYSTEMS USING
`IP INFORMATION
`
`BACKGROUND
`
`Technological advances in computer hardware, software,
`and networking have led to increased demandfor electronic
`information exchange. Such electronic communication can
`provide split-second, reliable data transfer between essen-
`tially any two locations throughout the world. Many indus-
`tries and consumers are leveraging such technology to
`improve efficiency and decrease cost through web-based
`(e.g., on-line) services.
`For example, modern game-play devices have developed
`capabilities of powerful computers as more-advanced inte-
`grated circuit technology has becomeincorporated into such
`game-play devices. Additionally, gaming has progressed to
`an online arena, where players can connect their gaming
`systems with other players via an online server, and commu-
`nicate, coordinate, and interface with other remote players
`while playing a game.
`Within such online arenas, network communication falls
`into either a client-server architecture (i.e., users communi-
`cate with a large, well-provisioned, dedicated server) or a
`peer-to-peer (P2P) architecture (i.e., users communicate with
`each other directly or via a peer). Peer-to-peer architectures
`and networking environments have grown considerably in
`population and use. In a peer-to-peer environment, many
`applications require selection of another peer in a network
`that can provide services via a network connection, such as
`serving as the central coordinator for a multiplayer game. As
`such, one can referto the peerthat is searching for services as
`a “client” and to a potential peer that can provide these ser-
`vicesas a “host.” Additionally, in a peer-to-peer networkthere
`exist particular services, such as multiplayer game play, in
`which one or more “clients” connectto each other via a “host”
`
`intermediary, where both host andclient are peers, rather than
`a dedicated, well-provisioned, centrally-located server. An
`individual peer can act as both a “host” and a “client” for
`different connections. In particular, effective selection or
`matchmaking of a client to a host based on network path
`quality (NPQ) can affect connectivity there between. Put
`differently, good network connectivity between a client anda
`matched host can enable optimal use of a peer-to-peer net-
`working environment. NPQ can be any one or combination of
`attributes such as round trip time (RTT), upstream capacity,
`downstream capacity, one-way delays, etc.
`Moreover, rapid estimation of round-trip time between
`machines remainscritical for many distributed applications.
`In particular, content distribution systems needto find a best
`server for a content seeker. Likewise, distributed hash tables
`require selection of close machinesfor routing table entries
`and lookups. In multiplayer online games, players seek to
`cluster themselves so that players in the same session have
`low latency to each other. Similarly, users of Voice over
`Internet Protocol
`(VoIP) systems are highly sensitive to
`latency, and hencebetter server and peer selection can have a
`tremendous impact.
`Twoparticular approaches to latency prediction are net-
`work coordinate systems (NCS) and Internet topology mod-
`eling. An NCS assigns each node a coordinate in a virtual
`metric space, such that the distance between two nodes’ coor-
`dinates is a reasonable approximation of the round-trip time
`between them. Alternatively, the Internet topology modeling
`constructs a rough graph of the Internet so it can predict the
`latency between a given pair of nodes. Each of these
`approaches has limitations. An NCS constructs its world
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`modelpurely based on distances observed between nodes and
`does not incorporate information about how the Internetis
`actually structured. The model thus winds up too loosely
`coupled to the reality of how the Internet works. Topology
`modeling, on the other hand, relies on a graphthattakes effort
`to construct. It is thus typically incomplete (especially with
`respect to home machines) and it cannot rapidly evolve to
`reflect changes.
`
`SUMMARY
`
`The following presents a simplified summary in order to
`provide a basic understanding of some aspects described
`herein. This summary is not an extensive overview of the
`claimed subject matter.Itis intended to neither identify key or
`critical elements of the claimed subject matter nor delineate
`the scope thereof. Its sole purposeis to present some concepts
`in a simplified form as a prelude to the more detailed descrip-
`tion that is presented later.
`The subject innovation improves prediction of network
`latency in network coordinate systems (NCS). It augments an
`NCS by employing geographic bootstrapping, autonomous
`system correction (AS), history prioritization, symmetric
`updates, or a combination thereof. NCSes use observations of
`latency measurements among a substantially large number of
`nodesto build virtual coordinates for mimicking the latency
`therebetween. Moreover, such virtual coordinates can be
`employed to determine whatthe latency between other nodes
`is likely to be. The subject innovation maintains existing
`advantages associated with the NCS, such as being amenable
`to de-centralized implementation systems, being responsive
`to changing Internet conditions, and being inclusive of mea-
`surements from all participating nodes.
`In one aspect, geographic bootstrapping can represent ini-
`tializing a node’s virtual coordinate based on its approximate
`physical location (e.g., a geographical location on Earth,
`using techniques where distances between nodes can be used
`to approximate round trip time,) instead of at an arbitrary
`default origin point. Such an approach mergesthe benefits of
`NCS and geographic prediction and can produce a better
`result. Unlike a traditional NCS that begins with random
`initial conditions, the subject innovation initializes coordi-
`nates in approximately correct relative positions and so con-
`verges to a state with greater predictive power and higher
`confidence. Likewise, and unlike geographic prediction that
`producesstatic results, the subject innovation permits virtual
`nodelocations to vary dynamically based on round-trip time
`(RTT) observations. As such, the subject innovation can
`recoverfrom errors in geographic location, adapt to changing
`network conditions, and handle nodesthat diverge from typi-
`cal models relating distance to latency.
`In a related aspect, NCSes typically give each node an
`extra-dimensional coordinate referred to as its height. As
`such, it can model the componentoflatency due to having to
`traverse a path to a network core within the AS before pro-
`ceeding toward any particular destination outside the AS. In
`the autonomous system (AS) correction technique, each node
`determines what AS it belongs to, and then can employ a
`formula to substantially increase the accuracy of its RTT
`predictions. Put differently, a network coordinate system
`typically assigns to each node an extra coordinate referred to
`as a height, which represents the overhead of reaching this
`node from the core ofthe Internet. The subject innovation can
`detect when both end points are in the same AS, and incor-
`porate a predetermined formula to substantially increase
`accuracy of latency predictions.
`
`

`

`US 8,144,611 B2
`
`3
`innovation
`Likewise, a further aspect of the subject
`employshistory prioritization to improve prediction of net-
`work latency in network coordinate systems (NCS). As such,
`using the network latency learned from prior probes between
`the samepair of nodes can produce superior results as com-
`pared to predictions based on coordinate distances between
`that pair of nodes.
`A further aspect of the subject innovation is symmetric
`updates, which work as follows. When a node samples the
`RTTto another node,a typical NCSupdates only the probing
`node’s coordinates. The subject innovation updates coordi-
`nates of both nodes to substantially improve the predictive
`accuracy ofthe system. Such approachis readily applicable in
`systems that can afford a modest increase in network traffic
`and that have mutually trusting nodes. Put differently, in a
`network coordinate system, when a node probes another
`node, that other node can further update its own coordinates.
`Updating coordinates of both nodes substantially improves
`prediction accuracy.
`In a related methodology, initially geographic location of
`nodes on earth can be determined(e.g., by looking up an IP
`address in a database andobtainingthe associated geographic
`location). Subsequently, the location onthe earth’s surface in
`termsoflatitude and longitude can be converted into a point
`in virtual 3-D space and translated into a 3-D coordinate.
`Such coordinates can then be employed in a networked coor-
`dinate system.
`Likewise, for autonomous systems, initially for a node a
`determination is made regarding which autonomous system
`(AS) such nodeis located therein,(e.g., by determining who
`ownsthe node in a public registry). In one aspect, once two
`nodes have decided which AS they belong to, a subsequent
`determination is made as to whether such AS numbersare the
`
`same. If such numbers are not identical the methodology
`ends, and no further action is taken as the process is not
`applied thereto. Alternatively, ifthe numbersare identical the
`latency numbers can be modified between the two latency
`nodes, wherein a function of two heights (e.g., 20% of the
`total) can be subtracted from the latency estimate. Such an
`approach can mitigate inaccuracies resulting from overesti-
`mation of latencies within autonomoussystemsin the under-
`lying coordinate system.
`Accordingto a further aspect, symmetry ofthe Internet can
`be exploited as an additional network topology feature. Con-
`sider a pair of nodes, node A (e.g., a sender node) and node B
`(e.g., a receiver node). Whenever node A measures a
`roundtrip to node B, it should subsequently notify B of the
`result so that both A and B can update their respective coor-
`dinates appropriately.
`To the accomplishmentof the foregoing and related ends,
`certain illustrative aspects of the claimed subject matter are
`described herein in connection with the following description
`and the annexed drawings. These aspects are indicative of
`various waysin whichthe subject matter maybe practiced,all
`of which are intended to be within the scope of the claimed
`subject matter. Other advantages and novel features may
`become apparent from the following detailed description
`when considered in conjunction with the drawings.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 illustrates a block diagram for network latency
`prediction according to an aspect of the subject innovation.
`FIG. 2 illustrates a prior art system of latency prediction
`and update algorithm.
`
`20
`
`40
`
`45
`
`60
`
`4
`FIG.3 illustrates an exemplary correlation between dis-
`tances and roundtrip time.
`FIG.4 illustrates a prediction component based on geo-
`graphic bootstrapping according to an aspect of the subject
`innovation.
`
`FIG.5 illustrates a simple model of two autonomoussys-
`tems (AS) with broadband machinesonthe Internet.
`FIG.6 illustrates a related methodology for AS correction
`when combining topology modeling with a network coordi-
`nate system, in accordance with an aspect of the subject
`innovation.
`FIG.7 illustrates a related methodology of leveraging IP
`address information for combininghistory prioritization with
`an NCS.
`
`FIG.8 illustrates a methodology ofupdating coordinates of
`both nodes according to an aspect of the subject innovation.
`FIG.9 illustrates an inference componentthat can facilitate
`combining topology information with an NCSaccording to
`an aspect of the subject innovation.
`FIG. 10 is a schematic block diagram of a sample-comput-
`ing environment that can be employed aspart of combining
`network topology with an NCSin accordance with an aspect
`of the subject innovation.
`FIG. 11 illustrates an exemplary environment for imple-
`menting various aspects of the subject innovation.
`
`DETAILED DESCRIPTION
`
`The various aspects of the subject innovation are now
`described with reference to the annexed drawings, wherein
`like numerals refer to like or corresponding elements
`throughout. It should be understood, however, that the draw-
`ings and detailed description relating thereto are not intended
`to limit the claimed subject matter to the particular form
`disclosed. Rather, the intention is to cover all modifications,
`equivalents and alternatives falling within the spirit and scope
`of the claimed subject matter.
`FIG. 1 illustrates a block diagram 100 for a prediction
`component101 that predicts network latency according to an
`aspect of the subject innovation. Such prediction component
`101 improves prediction in network latency of network coor-
`dinate system (NCS) 103 based on combining features of
`network topology 105 with the NCS 103. In particular, the
`prediction component 101 can employ one or more features/
`methodologies of: geographic bootstrapping 112; autono-
`mous system correction (AS) 114; history prioritization 116;
`symmetric updates 118; or a combination thereof, as
`explained in detail below. As such, by exploiting and/or incor-
`porating local IP information such as IP address into network
`coordinate systems, the latency between nodes can be better
`estimated.
`The NCS 111 maintains the location of nodesin a virtual
`
`coordinate space. In a decentralized implementation, each
`nodekeepstrack of the single location associated with itself.
`Moreover, by combining the topology modeling system 113
`with the NCS 111, topology information can then be incor-
`porated as part of such NCS 111. Furthermore, advantages
`associated with the NCS 111, such as being amenable to
`de-centralized implementation systems, being responsive to
`changing internet conditions, being inclusive of measure-
`ments from all participating nodes, and being adaptive, can be
`maintained.
`Aswill be explained in more detail infra, the geographic
`bootstrapping feature 112 can representinitializing a node’s
`virtual coordinate based on its approximate physical location
`(e.g., a geographical location on Earth) instead of employing
`an arbitrary default origin point. Such an approach mergesthe
`
`

`

`US 8,144,611 B2
`
`5
`benefits ofNCSes and geographic prediction and can produce
`better results. Unlike a traditional NCS, which begins with
`random initial conditions, the subject innovation initializes
`coordinates in approximately correctrelative positions and so
`convergesto a state with greater predictive powerand higher
`confidence. Likewise, and unlike geographic prediction that
`producesstatic results, the subject innovation permits virtual
`node locations to vary dynamically based on round-trip time
`(RIT) observations. As such, the subject innovation can
`recover from errors in geographic location, adapt to changing
`network conditions, and handle nodes that diverge from the
`typical model relating distance to latency.
`Similarly, the autonomous system correction 114 works as
`follows. An NCStypically gives each node an extra-dimen-
`sional coordinate referredto as its height. Such can model the
`component of latency due to having to traverse a path to a
`network core within the AS before proceeding toward any
`particular destination outside the AS. Moreover,if each node
`recognizes what ASit belongsto, it can employ a formula to
`substantially increase the accuracy of its RTT predictions.
`Additionally, history prioritization 116 enables employing
`prior probes(e.g., older results) directly. Such can produce
`superior results as compared to predictions based on coordi-
`nate distances.
`
`Likewise, in a network coordinate system, when a node
`probes another node,it can use the symmetric update feature
`118, wherein it notifies the other node ofthe resulting RTT so
`that node can update its own coordinates. This can substan-
`tially improve prediction accuracy. As such, any one of the
`features 112, 114, 116, 118 enable the NCS 111 to incorpo-
`rate topology information and make its modelbetter represent
`the Internet—andtherebysignificantly improvesits accuracy.
`In so doing, one neverthelessretainsall the positive features
`ofan NCS, namelythat it is decentralized, scalable, inclusive,
`and adaptive.
`Exemplary Conventional System
`To provide a more accurate understanding of the subject
`innovation, FIG.2 illustrates a conventional network coordi-
`nate system 200 referred to as Vivaldi. In general, Vivaldi
`represents an NCS, wherein each machineis assigned a coor-
`dinate in a virtual metric space, such that the distance between
`two machines’ coordinates is a substantially reasonable
`approximation of the round-trip time between them. Each
`node can independently maintain its coordinates, updating
`them as appropriate wheneverit observes a round-trip time to
`another node.
`Asillustrated in FIG. 2, during act (1) node A sends a
`messageto node B. During act (2) node B responds, and node
`A measures the RTT. Then,in act (3), ifthe distance between
`their virtual coordinates is too low/high, node A applies a
`virtual force to its coordinate, moving it away from/toward
`B’s. The conventional update algorithm associated with
`Vivaldi, includes
`
`wesw4/(wztWe)
`
`> =
`€—|[X- ¥ all-Lin/lap
`
`we—Cew,€(1-c.w.)W'4
`
`+ =
`+ =
`es
`X gS X gtCWel|X 4-¥ pll-Lap)u(% p-¥ 4)
`
`run after node A learns the RTT 1,, to node B. Here, Xwis
`the virtual location of node N, w,, is the uncertainty of node
`N’s coordinates, u(y) is the unit vectorin the direction of y,
`and c, and c, are algorithmic constants.
`
`wa
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`50
`
`55
`
`60
`
`6
`Likewise, we can adaptthe Vivaldi update algorithm to use
`spherical coordinates instead, by using the following formu-
`las:
`
`r—1 come — xal| — Lae) /lle4 ~ xl
`d—cos![cos(¢,)cos(dg) + sin(@4)sin(og cos(Ag —A,4)] —
`sin(pg sin(h4 )sin(Ag — Aq)
`yetan|
`cos(¢4) — cos(d)cos(dp)
`ba —cos! [cos(rd)cos(#g) + sin(rd)sin(d, )cos(y)]
`sin(dg)sin(rd)sin(y)
`cos(rd) — cos(p,)cos(Pg) |
`p—tar|
`Ag—Ag-B
`
`Here, Xyrepresents the coordinates for node N,consisting of
`¢, the latitudinal distance in radians between node N andthe
`North Pole, and 4,,, the longitude in radians of node N. The
`formulas show how to compute r, the ratio between the
`desired and current distance between nodes A and B; d, the
`current distance in radians between them ythe angle from the
`North Pole to B to A (which remains the same as A moves);
`and ( the angle from B to the North Pole to A’s new location,
`for example.
`In the conventional system initially Node A sends a mes-
`sage to nodeB, either as part of normal applicationtraffic or
`for explicit coordinate maintenance. The time whenthe reply
`from node B arrives reveals the RTT to node A. If such RTT
`is different from the distance between the two nodes’ virtual
`
`coordinates, node A updates its virtual coordinate accord-
`ingly. To do so, it applies a virtual force to its coordinate,
`either toward B’s if the RTT was unexpectedly small or away
`from B’s if it was unexpectedly large. In addition to its coor-
`dinates, each node also maintains an estimate of the uncer-
`tainty of these coordinates, which is a weighted movingaver-
`age of the error observed between expected RTTs and
`observed RTTs. When coordinates improve such that dis-
`tances better predict observed RTTs, uncertainty will
`decrease. Such uncertainty can be employed to determine
`how strong a force to apply is when updating coordinates; the
`greater node A’s uncertainty the stronger the force will be,
`and the lower node B’s uncertainty the strongerthe force will
`be.
`
`When a nodejoins the system,it initializes its coordinates
`to all zero,e.g., the origin, and its uncertainty to 100%. Due to
`acomercasein the equations described above, a node’s initial
`coordinates can be “bumped” to random valuesin the range
`[0, 1).
`Based on empirical research, Vivaldi’s developers recom-
`mendusing coordinates in a four-dimensional space, plus an
`extra non-Euclidean dimension known as the height. The
`distance between two coordinates with height h1 and h2 is the
`distance between their four-dimensional coordinates plus
`h1+h2. As such, the height represents the extra latency that a
`machine experiences on all its paths. Pyxida, an implemen-
`tation ofVivaldi, incorporates other modificationsto the basic
`algorithm based on experience with its real-world operation.
`For instance, to manage variability of individual RTT mea-
`surements, it keeps track of the last four latencies to each
`other node, and bases calculations on the 25th quantile ofthis
`sample. It also has the option to apply gravity, a small addi-
`tional force that pulls coordinates gently toward the origin
`with each update, to combat systematic drift.
`
`

`

`US 8,144,611 B2
`
`7
`
`Geography Location
`One aspect of the subject innovation employs geography
`information, wherein it has been observedthat th