idnits 2.17.1 draft-zhang-alto-traceroute-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** It looks like you're using RFC 3978 boilerplate. You should update this to the boilerplate described in the IETF Trust License Policy document (see https://trustee.ietf.org/license-info), which is required now. -- Found old boilerplate from RFC 3978, Section 5.1 on line 16. -- Found old boilerplate from RFC 3978, Section 5.5, updated by RFC 4748 on line 387. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 364. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 371. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 377. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** There are 2 instances of too long lines in the document, the longest one being 1 character in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust Copyright Line does not match the current year == Line 280 has weird spacing: '...address of...' -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (October 23, 2008) is 5665 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- No issues found here. Summary: 2 errors (**), 0 flaws (~~), 2 warnings (==), 7 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Network Working Group Liufei. Wen 2 Internet Draft Huawei Technologies 3 Intended status: Informational Yunfei.Zhang 4 Expires: April 23, 2009 China Mobile 5 October 23, 2008 7 P2P Traffic Localization by Traceroute and 2-Means Classification 8 draft-zhang-alto-traceroute-01.txt 10 Status of this Memo 12 By submitting this Internet-Draft, each author represents that 13 any applicable patent or other IPR claims of which he or she is 14 aware have been or will be disclosed, and any of which he or she 15 becomes aware will be disclosed, in accordance with Section 6 of 16 BCP 79. 18 Internet-Drafts are working documents of the Internet Engineering 19 Task Force (IETF), its areas, and its working groups. Note that 20 other groups may also distribute working documents as Internet-Drafts. 22 Internet-Drafts are draft documents valid for a maximum of six months 23 and may be updated, replaced, or obsoleted by other documents at any 24 time. It is inappropriate to use Internet-Drafts as reference 25 material or to cite them other than as "work in progress." 27 The list of current Internet-Drafts can be accessed at 28 http://www.ietf.org/ietf/1id-abstracts.txt 30 The list of Internet-Draft Shadow Directories can be accessed at 31 http://www.ietf.org/shadow.html 33 This Internet-Draft will expire on Feb 23, 2009. 35 Copyright Notice 37 Copyright (C) The IETF Trust (2008). 39 Abstract 41 Most P2P system performance suffers from the mismatch between the 42 randomly constructed overlays topology and the underlying physical 43 network topology, causing a large burden in the ISP and a long RTT 44 time. This document describes how DHT overlay peers can interact with 45 the routers by traceroute to get the path information, and execute 2- 46 Means Classification, thereafter peers leverage the DHT itself to 47 build efficient "closer" cluster. This scheme only requires the 48 infrastructure to enable traceroute queries. 50 Table of Contents 52 1. Introduction................................................2 53 1.1. Terminology............................................3 54 2. Overview....................................................3 55 3. Traceroute and Clustering....................................4 56 3.1. Peer Traceroute.........................................4 57 3.2. 2-Means Classification..................................5 58 3.3. Form the Cluster........................................6 59 3.4. Update.................................................6 60 4. Enhancement Examples.........................................7 61 4.1. Find the proximate candidates...........................7 62 4.2. More Efficient Overlay Routing..........................7 63 4.3. Placement of Cache......................................7 64 5. Security Considerations......................................7 65 6. IANA Considerations.........................................7 66 7. Conclusions.................................................8 67 8. References..................................................9 68 8.1. Normative References....................................9 69 8.2. Informative References..................................9 70 Author's Addresses.............................................9 71 Intellectual Property Statement.................................9 72 Disclaimer of Validity........................................10 74 1. Introduction 76 This document describes how DHT overlay peers get the topology 77 information and reduce the mismatch by traceroute and 2-Means 78 classification. In particular, an assumption is made about the 79 infrastructure routers support peers' traceroute requests, no matter 80 what specific means(ICMP traceroute or TCP traceroute).This operation 81 is reasonable for ISP in its network when it builds up a P2P overlay 82 and provides measurement services for themselves or for clients which 83 are defined in P2P SIP[3]. 85 In a P2P system, each end node provides services to other 86 participating nodes as well as receives services from them. An 87 attractive feature of P2P is that peers do not need to directly 88 interact with the underlying physical network, providing many new 89 opportunities for user-level development and applications. 90 Nevertheless, the mechanism for a peer to randomly choose logical 91 neighbors, without any knowledge about the physical topology, causes 92 a serious topology mismatch between the P2P overlay networks and the 93 physical networks. 95 The mismatch between physical topologies and logical overlays is a 96 major factor that delays the lookup response time, which is 97 determined by the product of the routing hops and the link latencies. 98 Mismatch problem also causes a large volume of redundant traffic in 99 inter-domain between the every ISP. These has constituted the 100 motivation to the topology-aware P2P, which implies to mitigate such 101 drawbacks. 103 The purpose of this document is to specify a way to efficient 104 topology matching technique. The DHT overlay peers' Traceroute result 105 are used to get "near" clusters and Edge Gateway by execute 2-Means 106 classification. This information will be put into the DHT. Two peers 107 will be considered as to hava a close neighbor relationship, if they 108 have at least one coomon router among their "near" clusters and Edge 109 Gateways. 111 1.1. Terminology 113 In this document, the key words "MUST", "MUST NOT", "REQUIRED", 114 "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT 115 RECOMMENDED", "MAY", and "OPTIONAL" are to be interpreted as 116 described RFC 2119 [1]. 118 This section defines some key concepts using in this document. 120 DHT - distributed hash table (DHT). 122 DHT Overlay : An overlay network is a computer network which is 123 built on top of another network. The peer-to-peer networks are 124 overlay networks because they run on top of the Internet. And the 125 peer-to-peer network which builds with DHT is DHT Overlay. 127 2-means classification: k-means classification is an algorithm to 128 classify objects based on their attributes into K number of group.2- 129 means classification algorithm is a special example of k-means 130 classification algorithm with k=2. 132 2. Overview 134 Usually, to solve the mismatch problem, it needs three steps, first 135 to estimate the physical network distance between two overlay peers 136 through network probing or prediction. then, based on this proximity 137 information , to cluster "near" peers, so as to let peers can find a 138 better candidate than the randomly chosen result. At last, such 139 results are utilized to optimize P2P alogrithm. The "near" peers are 140 the preferential choice in P2P lookup and maintenance, and these will 141 impel the access and traffic localization and reduce delay. 143 +-------------------------------------------------------------+ 144 | | | | 145 | Measure& | Clustering | Impelled local | 146 | Predict | | access pattern | 147 | | | | 148 +-------------------------------------------------------------+ 150 Figure 1 Basic Steps of P2P Traffic Localization 152 In this document, an efficient topology matching technique is 153 specified. First, before a peer joining the P2P networks, it randomly 154 picks an Internet IP address and probes it using the traceroute tools. 155 According to the measured data, the peer tracks the return 156 information to a vector data. Then 2-means classification algorithm 157 is used to classify the Internet routers into "near" and "remote" 158 routers. Finally, peer chooses the router with maximum Hops item in 159 "near" set as a the Edge Gateway. The peer registers into the DHT 160 overlays with the Edge Gateway the Key, then do same to the "near" 161 set. Through shared vector cluster information such as "near" routers 162 cluster and Edge Gateway, two peers were considered as a close 163 neighbor relationship when their "near" routers cluster both had a 164 same router's IP address at least and then gathered together to form 165 a "close" peer clusters. 167 3. Traceroute and Clustering 169 3.1. Peer Traceroute 171 As a rapid developed network, the Internet presents two kinds of 172 basic characteristic. On one hand, with many end user hosts randomly 173 join and leave the network, the topology of Internet is dynamic and 174 variable, but the routers constitute a much more stable 175 infrastructure topology. On the other hand, regarding Internet as a 176 graph (V=routers, E=direct link between routers), we found that the 177 edges between ASes constitutes a very small portion among the total 178 edges, and usually the delay between ISP routers is more large than 179 the delay between routers in the same AS domains. A peer need 180 randomly picked an Internet IP address and probed it using the 181 traceroute tools. The peer tracked the return information to a 182 vector data, with the data structure . 184 5ms 10ms 100ms 6ms 150ms 20ms 8ms 185 R1--R2---R3----------R4--R5----------R6---R7--R8 187 Fig.2 The Traceroute Result 189 Fig.2 is an example of path information by R1 traceroute to R8. As is 190 clear from Fig.2, between the R3 and R4, R5 and R6, there are some 191 huge latency leaps than the others. It possibly means that traceroute 192 message across the different AS domains or different ISP ranges. 194 3.2. 2-Means Classification 196 When the overlay peer gets the traceroute result through randomly 197 probe, a 2-means classification algorithm is used to classify the 198 Internet routers based on the Latency attribute in these traceroute 199 result. The 2-means classification algorithm includes four steps as 200 following[2]: 202 step1. Peer chooses the minimum latency item and maximum latency 203 item in whole vectors as centroids for two initialization 204 sets "first" and "second". 206 As a example in Fig.2, and is 207 selected as centroids for sets "first" and "second". 209 step2. Peer takes the latency item in vector to make an absolute 210 distance value with two centroids in turn, and then 211 separately associated the corresponding vector to one 212 vector cluster that has smaller absolute distance value. 214 So for the Fig2. example, the vector of R2 is , and 215 the distance between R2 and R1 is 10-5 = 5, and the distance 216 between R2 and R5 is 150-10 = 140. So belongs to 217 the "first" set. 219 step3. Peer calculates the latency mean and variance value of 220 two vector clusters. 222 As in in Fig.2, the R1,R2,R4,R6,R7 belong to the "first" set, 223 and R3,R5 belong to the "second" set and the mean and variance 224 can be calculated. 226 step4. If the variance value was larger than the threshold, peer 227 picks two latency mean values as new centroids of "first" and 228 "second" sets, then goto step2, otherwise finishs the 229 classification and gets two "first" and "second" sets. 231 Finally, peer chooses the router with minimum Hops item in 232 "second" set as a hop threshold. This router and the other 233 routers whose Hops item are larger than the hop threshold all 234 divided into a "remote" router cluster. And then the remaining 235 routers are gathered into another "near" cluster. and the router 236 with maximum hops of the "near" cluster is regarded as overlay 237 peer's Edge Gateway. 239 So for the Fig.2 example, R1,R2,R3 are the "near" routers of 240 overlay peer and others routers are the "remoter" routers of the 241 overlay peer. R3 will be the Edge Gateway in this case. 243 3.3. Form the Cluster 245 The peer registers into the P2P overlays with their Edge Gateway and 246 "near" routers as the Key, and the DHT ID and IP of itself as the 247 value.Due to the essence of DHT, if two item have the same Key,they 248 will be routed to the same DHT peer. Thus it makes possible to let 249 several peers to know each other, if they have some common elements 250 of their "near" router set. Edge Gateway is more useful, so if the 251 hosting DHT peers become overloaded, it will firstly deletes such non 252 Edge Gateway routers item. The hosting DHT peer will notify those 253 peers to form a "close" cluster, or join an existed cluster. 255 Each peer clusters has a ClusterId generated by consistent hashing 256 when the first two peers decided to form the cluster. The ClusterId 257 and its member peer Ids will be PUT into the DHT, and the peer can 258 find the other members within the same cluster by DHT GET with its 259 ClusterId remembered during its last online life. 261 3.4. Update 263 During normal peer-to-peer interactions such as DHT lookup or 264 maintenance, if peers belonging to different clusters found the delay 265 between them were relatively low, then these two clusters should 266 decide to combine a new bigger cluster. The mapping between those 267 original ClusterIds and the new generated ClusterIds should also be 268 registered into the DHT so as to let those peers belonging to old 269 clusters could find and join the new cluster. This technique 270 alleviates the problem occurred when peers belonging to same cluster 271 get different Edge Gateways from their traceroute response,thus they 272 can not form the ideal bigger cluster. 274 4. Enhancement Examples 276 4.1. Find the proximate candidates 278 Peers register their resources to be shared as pairs 279 into the DHT. Usually the Key is generated by consistent hashing some 280 information like the file name, and the Value is the IP address of 281 the sharing peer. When use our scheme, we will also include the 282 sharing peer's ClusterID in the Value. 284 When a overlay peer wants to find a resource, it will raise a DHT get 285 with the hashed Key and piggyback its ClusterID. When getting the 286 request, the peer hosting the Key k will check the list of 287 pairs registered by all the sharing candidates, then it 288 will choose the sharing peer with the same ClusterId to be the 289 preference result. 291 4.2. More Efficient Overlay Routing 293 The delay between the ISP is larger more than the inner-domain 294 delay.And if AS domain is big enough many resource can be found in 295 the same AS domains. So a more efficient hierarchical P2P network is 296 feasible. Each low layer (local) DHT is composed by the peers with 297 same ClusterID. All the peers or some candidate peers from each local 298 DHT will join the global DHT. Every peer firstly search in its local 299 DHT for its desired resource, then it may switched to the global DHT 300 only if the resource not available locally. 302 4.3. Placement of Cache 304 In order to reduce the inter-domain traffic and delay, cache is 305 always considered in the P2P network. The placement strategy takes 306 the cluster info into account. It will place caches to cover the peer 307 clusters in the order of its population, the number of peers 308 participating the cluster. 310 5. Security Considerations 312 This document does not currently introduce security considerations. 314 6. IANA Considerations 316 This document does not specify IANA considerations. 318 7. Conclusions 320 This document describes how DHT overlay peers can interact with the 321 routers by traceroute to get the path information, and execute 2- 322 Means Classification, thereafter peers leverage the DHT itself to 323 build efficient "closer" cluster. This scheme only requires the 324 infrastructure to enable traceroute queries. 326 8. References 328 8.1. Normative References 330 [1] Bradner, S., "Key words for use in RFCs to Indicate Requirement 331 Levels", BCP 14, RFC 2119, March 1997. 333 8.2. Informative References 335 [2] Guangyu Shi, Youshui Long. "T2MC: A Peer-to-Peer Mismatch 336 Reduce Technique by Traceroute and 2-Means Classification 337 Algorithm",Proc. IFIP Networking 2008. 339 [3] V. Pascual et.al," P2PSIP Clients",IETF draft, February 2008. 341 Author's Addresses 343 Yunfei Zhang 344 China Mobile Communications Corporation 346 Phone: +86 10 66006688 347 Email: zhangyunfei@chinamobile.com 349 Liufei Wen 350 Huawei Technologies Co. Ltd 352 Phone: +86 755 28977571 353 Email: wenliufei@huawei.com 355 Intellectual Property Statement 357 The IETF takes no position regarding the validity or scope of any 358 Intellectual Property Rights or other rights that might be claimed to 359 pertain to the implementation or use of the technology described in 360 this document or the extent to which any license under such rights 361 might or might not be available; nor does it represent that it has 362 made any independent effort to identify any such rights. Information 363 on the procedures with respect to rights in RFC documents can be 364 found in BCP 78 and BCP 79. 366 Copies of IPR disclosures made to the IETF Secretariat and any 367 assurances of licenses to be made available, or the result of an 368 attempt made to obtain a general license or permission for the use of 369 such proprietary rights by implementers or users of this 370 specification can be obtained from the IETF on-line IPR repository at 371 http://www.ietf.org/ipr. 373 The IETF invites any interested party to bring to its attention any 374 copyrights, patents or patent applications, or other proprietary 375 rights that may cover technology that may be required to implement 376 this standard. Please address the information to the IETF at 377 ietf-ipr@ietf.org. 379 Disclaimer of Validity 381 This document and the information contained herein are provided on an 382 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 383 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND 384 THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS 385 OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF 386 THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 387 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 389 Copyright Statement 391 Copyright (C) The IETF Trust (2008). 393 This document is subject to the rights, licenses and restrictions 394 contained in BCP 78, and except as set forth therein, the authors 395 retain all their rights. 397 Acknowledgment 399 Funding for the RFC Editor function is currently provided by the 400 Internet Society.