idnits 2.17.1 draft-xu-rtgwg-twod-ip-routing-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- == There are 1 instance of lines with non-RFC6890-compliant IPv4 addresses in the document. If these are example addresses, they should be changed. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == The document seems to contain a disclaimer for pre-RFC5378 work, but was first submitted on or after 10 November 2008. The disclaimer is usually necessary only for documents that revise or obsolete older RFCs, and that take significant amounts of text from those RFCs. If you can contact all authors of the source material and they are willing to grant the BCP78 rights to the IETF Trust, you can and should remove the disclaimer. Otherwise, the disclaimer is needed and you can ignore this comment. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (Mar 2012) is 4425 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) ** Downref: Normative reference to an Informational RFC: RFC 1940 (ref. '3') ** Downref: Normative reference to an Informational RFC: RFC 5439 (ref. '5') Summary: 2 errors (**), 0 flaws (~~), 4 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Network Working Group M. Xu 2 Internet-Draft J. Wu 3 Expires: September 2, 2012 S. Yang 4 Tsinghua University 5 D. Wang 6 Hong Kong Polytechnic University 7 Mar 2012 9 Two Dimensional IP Routing Architecture 10 draft-xu-rtgwg-twod-ip-routing-00 12 Abstract 14 This document describes Two Dimensional IP (TwoD-IP) routing, a new 15 Internet routing architecture which makes forwarding decisions based 16 on both source address and destination address. This presents a 17 fundamental extension from the current Internet, which makes 18 forwarding decisions based on the destination address, and provides 19 shortest single-path routing towards destination. Such extension 20 provides rooms to solve fundamental problems of the past and foster 21 great innovations in the future. 23 We present the TwoD-IP routing framework and its two underpinning 24 schemes. The first is a new hardware-based forwarding table 25 structure for TwoD-IP, FIST, which achieves line-speed lookup with 26 acceptable storage space. The second is a policy routing protocol 27 that flexibly diverts traffic. 29 Status of this Memo 31 This Internet-Draft is submitted in full conformance with the 32 provisions of BCP 78 and BCP 79. 34 Internet-Drafts are working documents of the Internet Engineering 35 Task Force (IETF). Note that other groups may also distribute 36 working documents as Internet-Drafts. The list of current Internet- 37 Drafts is at http://datatracker.ietf.org/drafts/current/. 39 Internet-Drafts are draft documents valid for a maximum of six months 40 and may be updated, replaced, or obsoleted by other documents at any 41 time. It is inappropriate to use Internet-Drafts as reference 42 material or to cite them other than as "work in progress." 44 This Internet-Draft will expire on September 2, 2012. 46 Copyright Notice 47 Copyright (c) 2012 IETF Trust and the persons identified as the 48 document authors. All rights reserved. 50 This document is subject to BCP 78 and the IETF Trust's Legal 51 Provisions Relating to IETF Documents 52 (http://trustee.ietf.org/license-info) in effect on the date of 53 publication of this document. Please review these documents 54 carefully, as they describe your rights and restrictions with respect 55 to this document. Code Components extracted from this document must 56 include Simplified BSD License text as described in Section 4.e of 57 the Trust Legal Provisions and are provided without warranty as 58 described in the Simplified BSD License. 60 This document may contain material from IETF Documents or IETF 61 Contributions published or made publicly available before November 62 10, 2008. The person(s) controlling the copyright in some of this 63 material may not have granted the IETF Trust the right to allow 64 modifications of such material outside the IETF Standards Process. 65 Without obtaining an adequate license from the person(s) controlling 66 the copyright in such materials, this document may not be modified 67 outside the IETF Standards Process, and derivative works of it may 68 not be created outside the IETF Standards Process, except to format 69 it for publication as an RFC or to translate it into languages other 70 than English. 72 Table of Contents 74 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 75 2. Benefits of Introducing TwoD-IP Routing . . . . . . . . . . . 5 76 2.1. Multi-homing . . . . . . . . . . . . . . . . . . . . . . . 5 77 2.2. Load Balancing . . . . . . . . . . . . . . . . . . . . . . 6 78 2.3. Diagnosis . . . . . . . . . . . . . . . . . . . . . . . . 7 79 2.4. Policy Routing . . . . . . . . . . . . . . . . . . . . . . 7 80 2.5. Others . . . . . . . . . . . . . . . . . . . . . . . . . . 7 81 3. Framework . . . . . . . . . . . . . . . . . . . . . . . . . . 9 82 3.1. Data Plane . . . . . . . . . . . . . . . . . . . . . . . . 9 83 3.2. Control Plane . . . . . . . . . . . . . . . . . . . . . . 9 84 4. Forwarding Table Design . . . . . . . . . . . . . . . . . . . 11 85 4.1. Design Goals . . . . . . . . . . . . . . . . . . . . . . . 11 86 4.2. Forwarding Table Structure . . . . . . . . . . . . . . . . 11 87 4.3. Lookup Action . . . . . . . . . . . . . . . . . . . . . . 13 88 4.4. Update Action . . . . . . . . . . . . . . . . . . . . . . 14 89 4.5. Scalability Improvements . . . . . . . . . . . . . . . . . 14 90 5. Routing Protocol Design . . . . . . . . . . . . . . . . . . . 15 91 5.1. Protocol Overview . . . . . . . . . . . . . . . . . . . . 15 92 5.2. Router Actions . . . . . . . . . . . . . . . . . . . . . . 16 93 5.3. TwoD-IP Routing Table Construction . . . . . . . . . . . . 17 94 6. Deployment . . . . . . . . . . . . . . . . . . . . . . . . . . 19 95 7. Implementation Status . . . . . . . . . . . . . . . . . . . . 20 96 8. Security Considerations . . . . . . . . . . . . . . . . . . . 21 97 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 22 98 10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 23 99 10.1. Normative References . . . . . . . . . . . . . . . . . . . 23 100 10.2. Informative References . . . . . . . . . . . . . . . . . . 23 101 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 24 103 1. Introduction 105 Since IP routing took place, the current Internet has been making 106 forwarding decisions based on destination addresses. The 107 destination-based routing system provides limited semantics with only 108 a single path towards each destination. Many services, such as 109 multi-homing, multi-path and traffic engineering, face difficulties 110 within the current Internet routing system. Due to the important 111 semantics of source address, recent years see increasing works on 112 adding source addresses into routing controls. 114 IP source routing [3] carries the routes in packet header. However, 115 IP source routing is disabled in most networks due to security 116 reasons. MPLS [4] uses label switching to manage traffic per-flow. 117 However, MPLS raises scalability issues when the number of label 118 switching paths (LSPs) increases [5]. What's more, many ISPs prefer 119 pure-IP networks. 121 In this draft, we describe Two Dimensional IP (TwoD-IP) routing, 122 which makes forwarding decisions based on both source and destination 123 addresses. TwoD-IP routing presents a fundamental extension of the 124 semantics from the current Internet. The network will become more 125 flexible, manageable, reliable, etc. Such extension provides rooms 126 to solve problems of the past and foster innovations in the future. 128 TwoD-IP routing framework is divided into data plane and control 129 plane. In data plane, packet forwarding needs to check both source 130 and destination addresses. Though current TCAM-based forwarding 131 table can match line speeds with parallel search over the table, with 132 one more dimension in the table, the forwarding table will explode 133 and exceed the maximum storage space of current TCAM. We devise a 134 new forwarding table structure for TwoD-IP, FIB Structure for TwoD-IP 135 (FIST). The new structure makes a separation between TCAM and SRAM, 136 where TCAM contributes to fast lookup speeds and SRAM contributes to 137 a larger memory space. In the control plane, we devise a simple 138 policy based routing protocol. For the traffic of a customer network 139 of an ISP, this policy routing protocol can flexibly divert the 140 traffic from one edge router to another edge router. 142 This document also presents the deployment issues and objectives of 143 the TwoD-IP routing. 145 2. Benefits of Introducing TwoD-IP Routing 147 In this section, we list the use cases that can benefit from TwoD-IP 148 routing. 150 2.1. Multi-homing 152 Multi-homing is prevalent among ISPs for better traffic distribution 153 and reliability. Traditionally, Provider Independent (PI) address is 154 used. Because PI address can not be aggregated by higher level ISPs, 155 it will cause explosion of routing table. To solve the problem, 156 Provider Aggregatable (PA) address is proposed. However, PA address 157 complicates network configurations for ISP operators. Besides, due 158 to destination-based routing in traditional networks, PA address has 159 difficulties when facing failures, i.e., the network has to re- 160 compute a new path when failures happen. 162 +--------------------+ 163 | | 164 | Internet | 165 | | 166 +--+---------------+-+ 167 | | 168 | l3 | l4 169 | | 170 +------+----+ +--+--------+ 171 | ISP1 | | ISP2 | 172 | Prefix P1 | | Prefix P2 | 173 +--------+--+ +-+---------+ 174 | | 175 | l1 | l2 176 +--+------------+--+ 177 | | 178 | Multi-homed Site | +---------+ 179 | +--------+ Host | 180 +------------------+ +---------+ 181 ISP1 address: A 182 ISP2 address: B 184 Figure 1: TwoD-IP routing for multi-homing 186 For example, in Figure 1, assume a multi-homed site is connected to 187 two ISPs: ISP1 and ISP2. ISP1 has a prefix P1, and ISP2 has a prefix 188 P2. A host connect to the multi-homed site has two addresses, 189 address A that can be aggregated into P1, and address B that can be 190 aggregated into P2. With TwoD-IP routing, the multi-homed site can 191 deliver the traffic from A towards the Internet to ISP1, and deliver 192 the traffic from B towards the Internet to ISP2. If the host is 193 using address A, and the link l1 or l3 fails. Then the host can 194 immediately detect the failure, then switch to address B, and 195 continue to communicate with the Internet via ISP2. With TwoD-IP, 196 the host does not have to wait for routing convergence in the multi- 197 homed site when failures happen. 199 2.2. Load Balancing 201 Compared to destination-based routing, TwoD-IP routing can manipulate 202 traffic in a finer-grained granularity. Such that TwoD-IP can 203 achieve better traffic distribution. For example, in Figure 2, 204 assume that there are 5 hosts that are communicating with the same 205 server at 10Mbps. Our goal is to minimize the maximum link 206 utilization over the network. Within destination-based routing, 207 traffic towards the same destination has to travel along the same 208 path in the network. Thus the best traffic distribution is to let 209 all traffic take the north route via router b, and the Min-max link 210 utilization is 83.3%. 212 +-----+ 213 |Host1+---+ 214 +-----+ | 215 +-----+ | 60Mbps +-----+ 60Mbps 216 |Host2+---+ +--------+ b +---------+ 217 +-----+ | | +-----+ | 218 +-----+ | +--+--+ +--+--+ +------+ 219 |Host3+---+---+ a | | c +--------+Server| 220 +-----+ | +--+--+ +--+--+ +------+ 221 +-----+ | | +-----+ | 222 |Host4+---+ +________+ d |_________+ 223 +-----+ | 40Mbps +-----+ 40Mbps 224 +-----+ | 225 |Host5+---+ 226 +-----+ 228 Figure 2: TwoD-IP routing for load balancing 230 With TwoD-IP routing, we can let the traffic of three hosts (e.g., 231 Host1, Host2 and Host3) take the north route via b, and let the 232 traffic of the other two hsots (e.g., Host4 and Host5) take the south 233 route via d. Thus the Min-max link utilization is only 50.0%. 235 2.3. Diagnosis 237 In Figure 3, assume a network has four routers: a, b, c and d. The 238 operator wants to monitor the status of the link between b and d. 239 Thus the operator sets up a monitor at router a, and sends probe 240 packets to d. Theoretically, the probe packets will flow on the 241 shortest path, i.e., a-b-d. However, the network provides traffic 242 engineering capabilities. If there is congestion on the link between 243 b and d, and router b moves the traffic towards d to the north path 244 via c. Thus, the probe packets will flow on the path a-b-c-d, which 245 does not include the link between b and d. 247 +------+ 248 +-------+ c +-----+ 249 | +------+ | 250 | | 251 | | 252 +------+ +--+---+ +---+--+ 253 | a +----------+ b +------------+ d | 254 +------+ +------+ +------+ 256 Figure 3: TwoD-IP routing for Diagnosability 258 With TwoD-IP routing, router b can identify the probe packets from a 259 towards d, and deliver them directly to router d. Thus the link 260 between b and d can be easily monitored. 262 2.4. Policy Routing 264 Assume in an ISP network, ISP operator wants that the traffic from 265 source address A towards destination address B passes by router C. 266 With TwoD-IP routing, routers make forwarding decisions based on both 267 destination and source addresses, thus can easily identify the 268 traffic from A towards B, and divert it to the next hop towards C. 270 2.5. Others 272 Besides the above-mentioned use cases, TwoD-IP routing is beneficial 273 in many other use-cases. We list the other use-cases briefly. 275 o Reliability: TwoD-IP provides multiple paths towards destination, 276 rather than the shortest path only. When one path breaks down, 277 routers can immediately switch to another path. 279 o Multi-path: TwoD-IP can forward packets towards the same 280 destination, and from different sources to different next hops. 282 If a host has multiple source addresses, the host will have 283 multiple paths towards the same destination. 285 o Security: Traditional network pushes the security devices to the 286 border routers, the intermediate network just delivers the 287 packets. With TwoD-IP, intermediate routers also have source 288 checking functionality. Thus, the whole network rather than the 289 border network, can defense attacks. 291 o Measurability: With TwoD-IP, ISP operators can explicitly control 292 the routing paths of probe packets. Thus the number of monitors, 293 and the additional traffic caused by the probe packets, can be 294 reduced [6]. 296 3. Framework 298 Similar with traditional routing, TwoD-IP routing can be separated 299 into two parts: data plane and control plane. 301 3.1. Data Plane 303 Data plane contains the forwarding table, that decides what to do 304 when a packet arrives. Different with traditional destination-based 305 routing, each entry in the TwoD-IP routing forwarding table is a 306 3-tuple: {destination address, source address, next hop}. When a 307 packet arrives, routers extract both destination and source addresses 308 from the packet, then lookup the forwarding table, and output a 309 matched entry. Finally, routers will forward the packet to the next 310 hop associated with the matched entry. 312 With a new dimension, the size of forwarding table will increase to 313 be O(N^2) (where N is the size of source/destination address space), 314 which is too large for current TCAM-based storage to accomodate. To 315 avoid forwarding table explosion, we design a new forwarding table 316 structure in Section 4. 318 3.2. Control Plane 320 In traditional routing, the control plane is concerned with the 321 network status, e.g., network topology. Within TwoD-IP routing, the 322 control plane is concerned with both network status and user demands. 323 TwoD-IP routing not only provides basic connectivity service, but 324 also satisfies kinds of user demands, e.g., policy routing, multi- 325 path and traffic engineering. TwoD-IP routing protocol has two 326 components: 328 o Destination-based routing protocol: To be compatible with 329 traditional routing (especially when most networks only support 330 destination-based routing), TwoD-IP routing protocol should 331 support destination-based routing. Such that ISPs can provide the 332 same connectivity service, while upgrading routers with TwoD-IP 333 functionality. To provide better connectivity services, 334 destination-based routing protocol should respond instantly to the 335 changes of network topology. 337 o Source-related routing protocol: Combined with source addresses, 338 TwoD-IP routing can make better forwarding decisions for users. 339 Source-related routing protocols focus on providing services that 340 are related with source addresses. They may need to collect 341 demands from users, and compute the routing table to satisfy these 342 demands. Depending on the specific user demands, some source- 343 related routing protocols need real-time updates, while others do 344 not. The newly designed source-related routing protocols should 345 be: 347 * Consistent, they should be consistent with other routing 348 protocols, including the destination-based routing protocol and 349 other new source-related routing protocols; 351 * Efficient, they should not bring lots of additional overheads 352 to the network. 354 4. Forwarding Table Design 356 4.1. Design Goals 358 The forwarding table stores a set of 3-tuple rules, {pd, ps, nh}, 359 where pd is a destination prefix, ps is a source prefix, and nh 360 indicates the next hop. When a packet arrives, if its destination 361 address matches pd according to LMF (longest match first) rule among 362 all rules, and its source address matches ps according to LMF rule 363 among all rules that are associated with pd. Then the router will 364 forward the packet to the next hop nh. 366 The new forwarding table should satisfy the following requirements. 368 o Storage requirement: The new forwarding table should not cause 369 forwarding table explosion problem. Current storage technology 370 should be able to accomodate the table. 372 o Speed requirement: The new forwarding table should match line- 373 speeds. 375 4.2. Forwarding Table Structure 377 We design a new TwoD-IP forwarding table structure, called FIST. As 378 shown in Figure 4, FIST consists of four parts. 380 Source +-------+------+------+------+------+ 381 Table |default| 111* | 101* | 100* | 11** | 382 +-------+------+------+------+------+ 383 | 0 | 1 | 2 | 3 | 4 | 384 +-------+------+------+------+------+ 385 Destination 386 Table | | | | | | 387 +-------+---+ --+------+------+------+------+------+--- 388 | 111* | 0 | | 1 | 0 | | 1 | | 389 +-------+---+ --+------+------+------+------+------+--- 390 | 100* | 1 | | 0 | 2 | | | | 391 +-------+---+ --+------+------+------+------+------+--- 392 | 101* | 2 | | 1 | | | | 2 | 393 +-------+---+ --+------+------+------+------+------+--- 394 | 11** | 3 | | 2 | | | | | 395 +-------+---+ --+------+------+------+------+------+--- 396 | 10** | 4 | | 2 | | | | 3 | 397 +-------+---+ --+------+------+------+------+------+--- 398 | | | | | | 399 TD-table 401 +------+---------+ 402 |Index |Next hop | 403 +------+---------+ 404 | 0 |1.0.0.0 | 405 +------+---------+ 406 Mapping | 1 |1.0.0.1 | 407 Table +------+---------+ 408 | 2 |1.0.0.2 | 409 +------+---------+ 410 | 3 |1.0.0.3 | 411 +------+---------+ 413 Figure 4: Forwarding Table for TwoD-IP 415 o Destination table: It resides in TCAM, and stores the destination 416 prefixes. Each destination prefix in destination table 417 corresponds to a row number. 419 o Source table: It resides in TCAM, and stores the source prefixes. 420 Each source prefix in source table corresponds to a column number. 422 o Two Dimensional Table (TD-table): It is a two dimensional array 423 that resides in SRAM. Given a row and column numbers, we can find 424 a cell in TD-table. Each cell in TD-table stores an index value, 425 that can be mapped to a next hop. 427 o Mapping table: It resides in SRAM, and maps index values to next 428 hops. 430 For example, in Figure 4, the destination table contains 5 431 destination prefixes, and the destination prefix 101* corresponds to 432 a row number 2. The source table contains 4 source prefixes and a 433 default one (can be see as "****"), the source prefix 11** 434 corresponds to a column number 4. The TD-table has 5 rows and 5 435 columns, the cell that is in the 2nd row and the 4th column has index 436 value 2. In the mapping table, we can see that the index value 2 is 437 related with the next hop 1.0.0.2. 439 If destination prefix pd outputs row number n, and source prefix ps 440 outputs column number m, we use (pd, ps) to denote a cell in the nth 441 row and mth column of the TD-table. 443 4.3. Lookup Action 445 When a packet arrives at a router, the lookup action is as follows. 447 1. Extract the destination address d and source address s from the 448 packet; 450 2. Perform the following two operations in parallel: 452 * Lookup the destination address d in the destination table 453 using the LMF rule, and output the row number n; 455 * Lookup the source address s in the source table using the LMF 456 rule, and output the column number m; 458 3. Lookup the cell that is in the nth row and mth column of the TD- 459 table, and output the index value v; 461 4. Lookup v in the mapping table, and ouput the corresponding next 462 hop; 464 5. Forward the packet to the next hop. 466 The 2nd step takes one TCAM clock cycle to match both d and s, and 467 one SRAM clock cycle to get the row/column number. The 3rd step 468 takes one SRAM clock cycle to get the index value, the 4th step takes 469 one SRAM clock cycle to get the next hop. Thus, the lookup speed is 470 one TCAM clock cycle plus three SRAM clock cycles. Beside, the 471 lookup process can be pipelined to achieve higher speed. 473 4.4. Update Action 475 Although FIST can reduce TCAM storage space, and achieve fast lookup 476 speed, it also faces new challenges. The challenges are caused by 477 performing LMF rule on source addresses. Assume a packet should 478 match destination prefix pd, and source prefix ps. However, if the 479 source table contains a source prefix ps' that also mathces the 480 packet and is longer than ps, then the packet will match (pd, ps') 481 within FIST. 483 For example, if the forwarding table on a router is shown in 484 Figure 4, and a packet with destination address of 1011 and source 485 address of 1111 arrives on the router. According to the matching 486 rule, destination prefix 101* is matched first, and source prefix 487 11** should be matched. However, within FIST, destination prefix 488 101* and source prefix 111* are matched. But the cell (101*, 111*) 489 is empty. 491 To resolve the confliction, we should pre-compute and fill the empty 492 cell with appropriate index value. For example, in Figure 4, we 493 should fill the cell (101*, 111*) with the index value 2, that is the 494 index value of cell (101*, 11**). We will discuss the update action 495 in the next version of this document. 497 4.5. Scalability Improvements 499 In Section 4.2, we design the FIST structure, where each destination 500 prefix corresponds to a row, and each source prefix corresponds to a 501 column. Considering the large number of address prefixes, we can 502 make improvements in the following two aspects: 504 o Not every destination prefix need to be mapped to a row, because 505 ISPs only need to divert traffic for part of the destination 506 prefixes. The destination table of FIST should be divided into 507 two parts, each destination prefixes in the first part points to a 508 row and each destination prefix in the second part points directly 509 to an index value. 511 o Different destination/source prefixes can be mapped to the same 512 row/column, because ISPs may implement the same policy on 513 different prefixes. For example, ISPs wants to divert the traffic 514 of some customer network, which has multiple prefixes, to another 515 path. 517 5. Routing Protocol Design 519 5.1. Protocol Overview 521 In this section, to illustrate TwoD-IP routing protocol, we design a 522 simple policy routing protocol. The routing protocol provides a 523 flexible tool for ISPs to divert traffic (that is from some customer 524 networks towards the foreign Internet) to another path. 526 +---------+ 527 |0.0.0.* | +-----------------------+ +----------+ 528 | +-----+-B0 I3 ------ E0-+-----+ | 529 +---------+ | ) ( | | 1.0.0.* | 530 Domain number=0 | ) ( | | | 531 The first customer | I0 | | 1.0.1.* | 532 +---------+ | ) ( | | | 533 |0.0.1.* | | ) ( | | 1.0.2.* | 534 | +-----+-B1 I1---I2---E1-+-----+ | 535 +---------+ +-----------------------+ +----------+ 536 Domain number=1 ISP network Foreign Internet 537 The second customer 539 Figure 5: A simple policy routing protocol 541 For example, in Figure 5, the ISP has two customer networks, the 542 first customer network has domain number of 0 and one prefix of 543 0.0.0.*, the second customer network has domain number of 1 and one 544 prefix of 0.0.1.*. The first customer network is conneted to 545 provider edge router (PE router) B0 and the second customer network 546 is connected to PE router B1. The ISP is connected to the foreign 547 Internet through two edge routers, E0 and E1, besides, it has four 548 intermediate routers (P router), I0, I1, I2 and I3. The shortest 549 paths from the customer networks to the foreign Internet are B0-I0- 550 I3-E0 and B1-I0-I3-E0. However, due to congestion on E0, the ISP 551 operator wants to divert the traffic of the second customer network 552 (behind B1) to the path through E1, i.e., B1-I0-I1-I2-E1. 554 We design the protocol based on the extension of OSPF [2], which can 555 disseminate the information within the network. To illustrate the 556 protocol, we first clarify the following aspects. 558 o Through e-BGP, edge routers know the prefixes of foreign Internet, 559 e.g., both E0 and E1 know that there are three foreign Internet 560 prefixes, 1.0.0.*, 1.0.1.*, 1.0.2.*; 562 o Through OSPF, PE routers know the prefixes of the customer 563 networks behind them, e.g., B0 knows that prefix 0.0.0.* belong to 564 the first customer network in Figure 5. Besides, PE routers know 565 the customer domain number of the customer networks behind them, 566 e.g, B0 knows that the customer domain number of the first 567 customer network is 0. Through manual configuration or automatic 568 selection (e.g., selecting the router that has lower utilization), 569 edge routers know the preferences of customer networks on edge 570 routers, e.g., B1 knows that the second customer network in 571 Figure 5 prefers to pass by E1. 573 With these preconditions, each edge router can announce the foreign 574 Internet prefixes combined with its own router identification to the 575 network, each PE router can announce the customer prefixes combined 576 with the corresponding customer domain number, PE routers are also 577 responsible for announcing the preference of customer networks on 578 edge routers. When receiving all necessary information, both PE and 579 P routers will construct the routing table, which can be used to 580 generate the forwarding table. 582 5.2. Router Actions 584 We first define three types of messages. 586 Announce(Prefixes, Router_ID): Edge routers send this message, to 587 announce the binding relations between foreign IP perfixes and the 588 edge router identification (can be represented by the IP address 589 of the edge router). This message indicates that traffic can 590 reach the foreign Internet through the edge router. 592 Bind(Prefixes, Domain_Number): PE routers send this message, to 593 announce the binding relations between customer network IP 594 prefixes and customer domain number. This message indicates that 595 the customer network IP prefixes belong to the cusomter network 596 that owns the Domain_Number. 598 Pref(Domain_Number, Router_ID): PE routers send this message, to 599 announces the preference of a customer network on an edge router. 600 This message indicates that the customer network that owns the 601 Domain_Number prefers to pass by the edge router that owns the 602 Router_ID. 604 Then the actions on different types of routers are as follows. 606 Edge Routers: Edge routers have to send Announce(Prefixes, 607 Router_ID) to announce the foreign Internet prefixes to the 608 network. For example, in Figure 5, E0 will send Announce(1.0.0.*, 609 E0), Announce(1.0.1.*, EO) and Announce(1.0.2.*, EO). E1 will 610 send Announce(1.0.0.*, E1), Announce(1.0.1.*, E1) and 611 Announce(1.0.2.*, E1). 613 PE Routers: 615 1. PE routers have to send Bind(Prefixes, Domain_Number) to 616 announce the customer network prefixes to the network. For 617 example, B0 will send Bind(0.0.0.*, 0), B1 will send 618 Bind(0.0.1.*, 1). 620 2. PE routers have to send Pref(Domain_Number, Router_ID) to 621 announce the preference of the cusomter network on an edge 622 routers. For example, B1 will send Pref(1, E1). 624 3. After receiving Announce(Prefixes, Router_ID) from edge 625 routers, PE routers should construct the routing table. 627 Intermediate Routers: After receiving Announce(Prefixes, Router_ID) 628 from edge routers, Bind(Prefixes, Domain_Number) and 629 Pref(Domain_Number, Router_ID) from PE routers, P routers should 630 construct the routing table. 632 5.3. TwoD-IP Routing Table Construction 634 Receiving the necessary information (including customer network 635 prefixes, foreign Internet prefixes and preferences of customer 636 networks), both PE and P routers should construct the routing table. 637 Edge routers do not need to construct the routing table, unless they 638 also belong to PE/P routers. 640 The routing table consists of two parts, the first part (traditional 641 routing table) is constructed based on OSPF, the second part (TwoD-IP 642 routing table) is construted based on our TwoD-IP policy routing 643 protocol. When forwarding a packet to the destination, routers first 644 lookup the TwoD-IP routing table, if there does not exist a matched 645 entry, routers will lookup the traditional routing table. We focus 646 on the construction of TwoD-IP routing table in this document. For 647 simplicity, we assume that there are only threee fields in each entry 648 of TwoD-IP routing table, i.e., (Destination, Source, Next hop). 649 Both the destination and source fields represent an IP prefix, the 650 next hop field denotes the outgoing router interface to use (see 651 Section 11 of [1] for more details). 653 The routing table construction process is as follows. 655 1. For each received Pref(Domain_Number, Router_ID), lookup the 656 traditional table, and obtain the next hop towards the edge 657 router that owns Router_ID. We use Next_Hop to denote the 658 obtained next hop. 660 2. For each foreign Internet prefix (Foreign_Prefix), lookup the 661 traditional table, and obtain the next hop towards the 662 Foreign_Prefix. We use Next_Hop' to denote the obtained next 663 hop. 665 3. If Next_Hop!=Next_Hop', for each customer network prefix 666 (Customer_Prefix) that belongs to the customer network that own 667 Domain_Number, we add a new entry (Foreign_Prefix, 668 Customer_Prefix, Next_Hop) to the TwoD-IP routing table. 670 For example, we continue the example in Figure 5, the TwoD-IP routing 671 table on the P router I0 is shown in Figure 6. 673 Destination Source Next hop 674 _______________________________________________________ 675 1.0.0.* 0.0.1.* I1 676 1.0.1.* 0.0.1.* I1 677 1.0.2.* 0.0.1.* I1 679 Figure 6: TwoD-IP routing table on the P router I0 681 6. Deployment 683 TwoD-IP should support incremental deployment, and during deployment, 684 the following requirements should be satisfied. 686 Backward compatibility: During deployment, reachability should be 687 guaranteed, and loops should be avoided. 689 Incentive: After deploying partial routers, ISPs should be able to 690 see visible gains, e.g., their policies are implemented, traffic 691 distribution is improved or security level is enhanced. 693 Effectivity: The deployment should maximize the benefits for ISPs, 694 e.g., the deployment sequence should be carefully scheduled, such 695 that ISPs can obtain maximum benefits in each step. 697 7. Implementation Status 699 We have developed a prototype of the TwoD-IP policy routing protocol 700 (see Section 5) on a commercial router, and set up small scale tests 701 under VegaNet [7], a high performance virtualized testbed. 703 Currently, we are developing the prototype of TwoD-IP router, that 704 uses the FIST forwarding table strucute (see Section 4.2). 706 8. Security Considerations 708 TwoD-IP routing will enhance the security level of the networks, 709 because routers will check source addresses, which is an important 710 identity of the senders. Distributed attack defenses will be an 711 important topic of TwoD-IP routing, because source checking 712 functionality is deployed deeper in the network. 714 However, TwoD-IP routing protocols must be carefully designed, to 715 avoid to be used by hackers. 717 9. IANA Considerations 719 Some newly designed TwoD-IP routing protocols may need new protocol 720 numbers assigned by IANA. 722 10. References 724 10.1. Normative References 726 [1] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998. 728 [2] Zinin, A., Roy, A., Nguyen, L., Friedman, B., and D. Yeung, 729 "OSPF Link-Local Signaling", RFC 5613, August 2009. 731 [3] Estrin, D., Li, T., Rekhter, Y., Varadhan, K., and D. Zappala, 732 "Source Demand Routing: Packet Format and Forwarding 733 Specification (Version 1)", RFC 1940, May 1996. 735 [4] Rosen, E., Viswanathan, A., and R. Callon, "Multiprotocol Label 736 Switching Architecture", RFC 3031, January 2001. 738 [5] Yasukawa, S., Farrel, A., and O. Komolafe, "An Analysis of 739 Scaling Issues in MPLS-TE Core Networks", RFC 5439, 740 February 2009. 742 10.2. Informative References 744 [6] Breitbart, Y., Chan, Chee-Yong., Garofalakis, M., Rastogi, R., 745 and A. Silberschatz, "Efficiently monitoring bandwidth and 746 latency in IP networks", INFOCOM 2001, Apr 2001. 748 [7] Chen, Wenlong., Xu, Mingwei., Yang, Yang., Li, Qi., and 749 Dongchao. Ma, "Virtual Network with High Performance: VegaNet", 750 Chinese Journal of Computers vol. 33, no. 1, 2010. 752 Authors' Addresses 754 Mingwei Xu 755 Tsinghua University 756 Department of Computer Science, Tsinghua University 757 Beijing 100084 758 P.R. China 760 Phone: +86-10-6278-5822 761 Email: xmw@csnet1.cs.tsinghua.edu.cn 763 Jianping Wu 764 Tsinghua University 765 Department of Computer Science, Tsinghua University 766 Beijing 100084 767 P.R. China 769 Phone: +86-10-6278-5983 770 Email: jianping@cernet.edu.cn 772 Shu Yang 773 Tsinghua University 774 Department of Computer Science, Tsinghua University 775 Beijing 100084 776 P.R. China 778 Phone: +86-10-6278-5822 779 Email: yangshu@csnet1.cs.tsinghua.edu.cn 781 Dan Wang 782 Hong Kong Polytechnic University 783 Department of Computing, Hong Kong Polytechnic University 784 Hong Kong 785 P.R. China 787 Phone: +852-2766-7267 788 Email: csdwang@comp.polyu.edu.hk