A new multi-homing architecture based on overlay network Satoshi UDA, Nobuo OGASHIWA, Kenichi NAGAMI, Kuniaki KONDO, Ikuo NAKAGAWA, Yoichi SHINODA, and Hiroshi ESAKI 1. 1 (ISP) School of Information Science, Japan Advanced Institute of Science and Technology (JAIST), 1 1 Asahidai, Tatsunokuchi, Ishikawa 923 1292, Japan. ( ) Intec NetCore Inc., 1 3 3 Shinsuna, Koto-ku, Tokyo 136 0075, Japan. Center for Information Science, Japan Advanced Institute of Science and Technology (JAIST), 1 1 Asahidai, Tatsunokuchi, Ishikawa 923 1292, Japan. Graduate School of Information Science and Technology, The University of Tokyo, 7 3 1 Hongo, Bunkyo-ku, Tokyo 113 8656, Japan. ( ) [1], [2] 2. ISP B Vol. Jxx B No. xx pp. 1 10 xxxx xx 1
xxxx/xx Vol. Jxx B No. xx ISP A s address ISP A User The Internet ISP B s address ISP B (a) No multi-home User ISP A s address User s address ISP A User s address The Internet User ISP B s address User s address ISP B (b) Multi-home User User s address 1 Fig. 1 Route advertisements on traditional multihoming ISP 2. 1 2003 12 CIDR (Classless Inter-Domain Routing) [3], [4] ISP ISP ( 1) 1 1 6 24 1 ISP ISP ISP Prefix 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 21 9 5 10 8 11 13 12 53 13 98 14 256 15 469 16 7,400 Prefix 17 1,666 18 2,991 19 8,446 20 8,458 21 6,011 22 8,997 23 8,498 24 59,378 25 78 26 87 27 13 28 19 29 31 30 1 31 0 32 20 1 ( ) Table 1 A number of route entries on the Internet (by each prefix length) ( 1) 2. 2 ISP ( ) RouteScience PathControl 2 BIG- IP Link Controller 3 2RouteScience : http://www.rootscience.com/ 3F5 Networks : http://www.f5networks.com/ 2
CDN (Contents Distribution Network) 2. 3 ISP AS (Autonomous System) BGP-4 (Border Gateway Protocol version 4) [5] BGP-4 BGP-4 BGP-4 3. 3. 1 (DR: Distribution Router) ( ISP) DR DR ( 2) DR (UR: User Router) ISP A UR1 User1 The Internet DR ISP B UR2 User2 ISP C 2 Fig. 2 Overview of our proposed multi-homing architecture 2 ISP (ISP-A, ISP-B) 2 (ISP-A ISP-B ) DR UR ISP ISP-A ISP-B ISP-A ISP-B ISP DR DR ISP DR UR DR UR DR ( ) 3
xxxx/xx Vol. Jxx B No. xx 3. 2 DR CIDR ISP DR DR 1 DR 3. 3 DR DR DR (a single point of failure) DR DR UR DR ISP DR UR DR A The Internet DR B ISP A ISP B DR-UR tunnel UR1 User1 3 DR Fig. 3 Using multiple DRs for increasing reliability DR DR ( 3) DR DR DR DR DR DR DR DR DR DR DR DR DR DR DR DR DR 3. 4 DR UR DR DR 4
ISP ISP IP ISP DR UR Anycast DR DR 4. 4. 1 ( ) 2. BGP-4 BGP-4 10 DR UR DR 1 1 1 BGP-4 ( ) UR DoS(Deny of Service) DR () UR UR DR 2 2 5
xxxx/xx Vol. Jxx B No. xx ISP 2 Table 2 Comparison the proposed architecture with the traditional method DR DR DR 4. 2 2. 1 6 24 RIR (Regional Internet Registries) ISP 20 ISP RIR RIR 24.0.0.0/8 ARIN 20 0 0 60.0.0.0/7 APNIC 20 1,169 442 (37%) 62.0.0.0/8 RIPE 19 1,248 611 (48%) 63.0.0.0/8 ARIN 20 2,835 2,516 (88%) 64.0.0.0/6 ARIN 20 13,703 10,703 (78%) 68.0.0.0/7 ARIN 20 2,990 1,831 (61%) 80.0.0.0/7 RIPE 20 1,656 715 (43%) 82.0.0.0/8 RIPE 20 31 5 (16%) 193.0.0.0/8 RIPE 29 3,974 0 (0%) 194.0.0.0/7 RIPE 29 5,396 0 (0%) 196.0.0.0/8 ARIN 24 694 0 (0%) 198.0.0.0/7 ARIN 24 8,146 7 (0%) 200.0.0.0/8 LACNIC 24 4,747 1 (0%) 201.0.0.0/8 LACNIC 20 0 0 202.0.0.0/7 APNIC 24 13,395 77 (0%) 204.0.0.0/6 ARIN 24 14,268 10 (0%) 208.0.0.0/7 ARIN 20 8,775 7,637 (87%) 210.0.0.0/7 APNIC 20 3,665 1,951 (53%) 212.0.0.0/7 RIPE 19 4,755 2,876 (60%) 216.0.0.0/8 ARIN 20 6,197 4,982 (80%) 217.0.0.0/8 RIPE 20 1,514 843 (55%) 218.0.0.0/7 APNIC 20 1,301 360 (27%) 220.0.0.0/7 APNIC 20 473 212 (44%) 222.0.0.0/8 APNIC 20 0 0 ARIN: American Registry for Internet Numbers RIPE: Reseau IP Europeens APNIC: Asia-Pacific Network Information Center LACNIC: Latin American and Caribbean Internet Address Registry 3 (CIDR ) Table 3 Routing entries in the Internet in each CIDR block ISP 3 AS 17932 CIDR RIR 20 24 24 6
1500 bytes IP IP GRE IP IP 28 bytes 1472 bytes 20 bytes 28 bytes 1500 bytes 48bytes 4 IP Fig. 4 IP fragment arising in encapsulation () () 20 47 24.15 (2.16) 1.92 (0.13) 48 2.89 (0.27) 20.57 (1.94) 49 255 32.23 (5.28) 58.30 (10.66) 256 511 7.31 (5.72) 6.24 (4.77) 512 1023 6.03 (7.73) 7.42 (9.32) 1024 1499 7.29 (19.67) 5.51 (14.60) 1500 20.10 (59.17) 22.06 (64.94) 100.00 (100.00) 122.02 (106.36) 4 Table 4 Comparison a distribution of packet lengthes between before/after encapsulation 4. 3 4. 1 IP IP GRE (Generic Routing Encapsulation) [6] 28 (IP 20 GRE 8 ) MTU (Maximise Transfer Unit) MTU 1500 GRE MTU 28 1472 MTU MTU MTU 1500 GRE MTU 1500 1472 IP 1500 1 1500 48 2 ( 4) 4 24 100 48 IP 22% 6% 48 1500 1500 48 20% 6% 6% 5. 7
xxxx/xx Vol. Jxx B No. xx AS1 user dr1 R1 user User Network ur Prefix:x.x.x.x/n user dr2 R2 5 Fig. 5 Topology of experimental network AS2 DR UR DR DR DR UR DR DR UR IP over IP GRE DR UR UR DR NetBSD NetBSD 1.6 RELEASE 2 ISP (AS1,AS2) ISP AS DR (dr1,dr2) UR (ur) ( 5) ISP (user) DR ( GRE ) UR DR ( ) 2 AS1 (user) (user) 200ms 4 DV (Digital Video) DVTS 5 (8 ) 6. DR DR DR DR DR 4AS1 DR 20ms 100ms 5DVTS DV UDP 30 / 30Mbps 8
DR1A DR2A DR1D DR2D ISP A ISP D The Internet ISP B ISP C DR1B DR2B DR1C DR2C 6 DR Fig. 6 A structure based on multiple DRs 5. DR UR DR UR DR ISP BGP-4 DR ISP 3. 3 DR DR DR DR 6 (1,2,...) DR (1 DR DR1A,DR1B,...) DR DR DR DR 4. 3 MTU MTU MTU IP MTU 7. [1] T. Bates, and Y. Rekhter, RFC 2260: Scalable Support for Multi-homed Multi-provider Connectivity, IETF, January 1998. [2] J. Hagino, and H. Snyder, RFC 3178: IPv6 Multihoming Support at Site Exit Routers, IETF, October 2001. [3] Y. Rekhter, and T. Li, RFC 1518: An Architecture for IP Address Allocation with CIDR, IETF, September 1993. [4] V. Fuller, T. Li, J. Yu, and K. Varadhan, RFC 1519: Classless Inter-Domain Routing (CIDR), IETF, September 1993. 9
xxxx/xx Vol. Jxx B No. xx [5] Y. Rekhter, and T. Li, RFC 1771: A Border Gateway Protocol 4 (BGP-4), IETF, March 1995. [6] D. Farinacci, T. Li, S. Hanks, D. Meyer, and P. Traina, RFC 2784: Generic Routing Encapsulation (GRE), IETF, March 2000. xx xx xx 1983 1985 1988 1989 1991 1997 1999 2004 ( ) 1987 ( ) CSR/MPLS 1998 () 1998 1999 2001 2004 () ( ) 1992 ( ) CSR/MPLS 2001 () 2002 ( ) 1992 1997 ( ) BGP-4 2002 ( ) 1993 ( ) 2002 ( ) 10
Abstract As a result of the vast Internet growth, a multi-homing technology is being extensively utilized to keep a connectivity to important networks. However, the traditional multi-homing architecture severely impacts routing performance of the Internet making it nonscalable. Furthermore, although it can enhance a reachability, it can not be used to enhance an utilization because it can not assign in-coming traffic to multiple links. In this paper, we propose a new multi-homing architecture which is based on the overlay networking model, providing solutions to these problems. Our architecture improves scalability and realizes a dynamic and flexible line selection for in-coming traffic. Key words Internet, Multi-homing, Overlay network.