`
`
`
`
`
`
`
`
`
`
`Exhibit 1020
`
`Exhibit 1020
`
`
`

`

`US007554930B2
`
`(12) United States Patent
`Gaddis et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7,554,930 B2
`Jun. 30, 2009
`
`(54) INTERNET ROUTE DEAGGREGATION AND
`ROUTE SELECTION PREFERENCING
`
`(75) Inventors: Michael E. Gaddis, DeFiance, MO
`(US); Peter N. Hicks, Webster Groves,
`MO (US); David Barmann, Valley Park,
`MO (US); Steven T. Nunes,
`Edwardsville, IL (US)
`
`FOREIGN PATENT DOCUMENTS
`
`CN
`
`1424756 A
`
`6/2003
`
`(Continued)
`OTHER PUBLICATIONS
`
`(*) Notice:
`
`(73) Assignee: Level 3 Communications, LLC,
`Broomfield, CO (US)
`s
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 682 days.
`21) Appl. No.: 11/084.804
`(21) Appl. No
`s
`(22) Filed:
`Mar 18, 2005
`
`& 4
`: - - - - -- ??
`Rekhter& Gross, “BGP-4 Application” (RFC 1772), Mar. 1995, p.
`10.*
`
`inued
`(Continued)
`Primary Examiner—Gregory B Sefcheck
`Assistant Examiner—Salvador E Rivas
`(74) Attorney, Agent, or Firm—Fellers, Snider, Blankenship,
`Bailey & Tippens
`
`(65)
`
`Prior Publication Data
`|US 2005/0201302 A1
`Sep. 15, 2005
`Related U.S. Application Data
`-
`. -
`-
`-
`-
`(62) º of º Nº. 09/594,461, filed on Jun.
`s
`, now abandoned.
`(51) Int. Cl.
`(2006.01)
`H04L 12/28
`(2006.01)
`PH04 L I 2/56
`(52) U.S. Cl. .................. 370/254; 370/389; 370/395.31:
`707/1: 707/100; 709/224; 709/229; 713/1:
`713/185; 726/3: 726/22
`(58) Field of Classification Search ....................... None
`See application file for complete search history.
`References Cited
`
`(56)
`
`|U.S. PATENT DOCUMENTS
`5,233,604 A * 8/1993 Ahmadi et al. .............. 370/238
`5,926,101 A
`7/1999 Dasgupta ........
`... 340/825.02
`6,009,081 A 12/1999 Wheeler et al. ............. 370/255
`6,038,600 A
`3/2000 Faulk, Jr. et al. ............ 709/224
`(Continued)
`
`Route Processing
`at the Nº.
`
`
`
`(57)
`
`ABSTRACT
`
`A method and system for managing the routing of traffic
`within a network develops atopological address space map of
`the network to enable a “best route” selection process. The
`network is comprised of a backbone connected to a plurality
`of peering partners. Points on the network monitor traffic
`flows. A central facility analyzes the traffic flows and routes
`within the network and performs intelligent routing manage
`ment.
`
`Intelligent routing management ensures that traffic is prop
`erly routed through preferred routes on the network, and
`avoids inefficient routing. Intelligent routing management
`also selects new routes to be injected into the networkin order
`to further improve the accuracy of the address space map of
`the network. Intelligent routing management ensures that
`bandwidth is requested and delivered topologically closely to
`peering partner networks, and that traffic is carried by the
`backbone for long haul data distribution in both directions.
`
`16 Claims, 16 Drawing Sheets
`
`

`

`US 7,554,930 B2
`Page 2
`
`|U.S. PATENT DOCUMENTS
`
`5/2000 Ayandeh ..................... 370/399
`6,069,895 A
`6,094,682 A * 7/2000 Nagasawa
`. 709/224
`6,178,235 B1* 1/2001 Petersen et al.
`... 379/134
`6,411,997 B1
`6/2002 Dawes et al. ...
`... 709/224
`6,421,434 B1
`7/2002 Rosu ..........
`. 379/133
`6,501,752 B1
`12/2002 Kung et al. ....
`... 370/352
`6,574,663 B1
`6/2003 Bakshi et al. ..
`... 709/223
`6,584,093 B1
`6/2003 Salama et al. .....
`... 370/351
`6,598,034 B1
`7/2003 Kloth .........
`... 706/47
`6,618,755 B1
`9/2003 Bonn ............
`. 709/223
`6,633,585 B1
`10/2003 Ghanwani et al. ........... 370/468
`6,728.215 B1
`4/2004 Alperovich et al. ......... 370/252
`6,728,777 B1
`4/2004 Lee et al. ..........
`... 709/238
`6,763,000 B1
`7/2004 Walsh ...........
`. 370/252
`6,801,534 B1 * 10/2004 Arrowood etal
`... 370/400
`2002/0002686 A1* 1/2002 Vange et al. ......
`... 713/201
`2003/013 1263 A1* 7/2003 Keane et al. ...
`... 713/201
`2003/0145246 A1* 7/2003 Suemura ........................ 71.4/2
`
`
`
`FOREIGN PATENT DOCUMENTS
`
`JP
`JP
`WO
`WO
`WO
`
`3-191541
`2003-78171
`WO 98/20724 A2
`WO 98/20724 A3
`WO 00/38381 A1
`
`8/1991
`3/2003
`5/1998
`5/1998
`6/2000
`
`OTHER PUBLICATIONS
`Network
`http://info.internet.isi.edu/in-notes/rfc/files/rfc.1771.txt,
`Working Group, Requests for Comments: 1771, Obsoletes: 1654,
`Category: Standards Track; Editors: Y. Rekhter, T.J. Watson;
`Research Center, IBM Corp., T. Li, Cisco Systems, Mar. 1995; “A
`Border Gateway Protocol 4 (BGP-4)”; pp. 1-50; [retrieved on Mar.
`27, 2000].
`Network
`http://info.internet.isi.edu/in-notes/rfc/files/rfc.177.txt;
`Working Group, Requests for Comments: 1772, Obsoletes: 1655,
`
`Category: Standards Track; Editors: Y. Rekhter, T.J. Watson;
`Research Center, IBM Corp., P. Gross, MCI; Mar 1995; “Application
`of the Border Gateway Protocol in the Internet”; pp. 1-17; [retrieved
`on Mar. 27, 2000].
`http://www.ec.enron.com/about/; Enron Broadband Services, Inc.;
`“About Enron Broadband Services” Copyright 1997-2000 Enron
`Corp.; pp. 1, 2; [retrieved on May 2, 2000].
`ISPs:
`http://www.ec.enron.com/isplein/interagent.html; Enron:
`Enron Broadband Services; “InterAgent R Software”, Copyright
`1997-2000 Enron Corp.; pp. 1 of 1; [retrieved on May 2, 2000].
`http://www.ec.enron.com/isp/ein/more interagent.html;
`Enron:
`ISPs; Enron Broadband Services; “More About InterAgent?& Soft
`ware”, Copyright 1997-2000 Enron Corp.; pp. 1, 2; [retrieved on May
`2, 2000].
`InterNAP’s
`http://www.internap.com/html/how botright.htm:
`Technology Works; INTERNAP C Network Services; “How it
`works”; pp. 1-3; [retrieved on Feb. 10, 2000].
`http://www.internap.com/html/why botright.htm; InterNAP; Why
`The Internet Is So Slow; INTERNAPC) Network Services; “Why is
`the Internet so slow”, pp. 1, 2; [retrieved on Feb. 10, 2000].
`http://www.internap.com/html/news_pr_02102000.htm:
`InterNAP: Press Release; INTERNAP (C) Network Services;
`“BizRate.com Selects InterNAP’s High Performance Internet Con
`nectivity”; pp. 1-3; [retrieved on Feb. 10, 2000].
`http://www.cisco.com/univercq/cd/td/doc/cisintwk/ics/icsbgp4.
`htm; Using the Border Gateway Protocol for Interdomain Routing;
`Copyright 1989-2000 C, Cisco Systems Inc.; Posted Wed. Feb. 9
`13:25 PST 2000; pp. 1-65; [retrieved May 8, 2000].
`Paxon, Measurements and Analysis of End-to-End Internet Dynam
`ics; Chapter 8, Routing Symmetry, p. 92-100 (Jun. 1997).
`Search report dated Aug. 21, 2007 from corresponding Chinese
`Patent Appln. No. 200510056380.1.
`Search report dated Sep. 19, 2007 from corresponding Japnese Patent
`Appln. No. 2004-266923.
`* cited by examiner
`
`

`

`U.S. Patent
`
`Jun. 30, 2009
`
`Sheet 1 of 16
`
`US 7,554,930 B2
`
`VL aunfil
`
`
`
`
`
`
`
`
`
`
`
`09||_ _ __. - A- - - - - - ~~~ ~ ~Zy| ?u?od
`
`
`
`__ __. -_- ----- - - - - ~~-->•
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jun. 30, 2009
`Jun.30,2009
`
`Sheet 2 of 16
`Sheet20f16
`
`US 7,554,930 B2
`US 7,554,930 B2
`
`
`
`N:E8
`
`m:2:9". N238
`
`

`

`U.S. Patent
`
`Jun. 30, 2009
`
`Sheet 3 of 16
`
`US 7,554,930 B2
`
`
`
`
`
`
`
`og = Jaquunu Sv.
`0Z || CHS|
`
`00! = uaquunu SV
`
`809 ||
`
`
`
`wyz eunfil
`
`

`

`U.S. Patent
`
`Jun. 30, 2009
`
`Sheet 4 of 16
`
`US 7,554,930 B2
`
`
`
`point
`215
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`-
`
`Figure 2B
`
`point
`
`|SP 110
`
`f e = -
`|
`
`-, .
`1.
`|.
`216.10.0.0 /16 ?:
`232
`| - .
`|
`f -
`|
`f
`:
`.
`/ .
`\ . ~ T ~
`.
`~ *
`.
`address
`...
`space
`230
`
`
`
`240
`- - -
`,”
`\
`!
`z
`f
`p
`f
`f
`p16.5.0.0 (16/
`|
`242
`/
`f
`/
`/
`27
`
`.
`f.
`\
`
`-
`address .
`space
`:
`
`210
`
`Space
`220
`point
`S.
`225 - sº
`* ^.
`f .
`. .”
`:
`A
`Af
`f
`A
`I
`f :
`216.100.00 né, . \
`1
`: \ 216.25.0.0/16
`212
`w
`:
`\
`222
`|
`7 :
`, “ .
`.
`2^ :
`\
`I
`*
`:
`-
`!
`/
`* -- *
`:
`-
`'----' .
`
`
`
`150A
`
`150C
`Peering
`connections
`
`Route information collection site 250
`
`IF ADDRESS
`
`sº
`ºn
`º,
`
`ROUTE INTERFACE
`
`9% OF TRAFFIC SEEN
`BY SITE 250
`
`
`
`.
`
`.
`
`ºn
`.
`gº
`
`.
`
`.
`
`
`
`
`
`.
`
`IP ADDRESS
`
`PREFIX
`
`ROUTE INTERFACE
`
`9. OF TRAFFIC SEEN
`BY SITE 250
`
`2} 6.5,0.0
`
`16
`
`#16
`
`| 5(3D
`
`0
`
`

`

`U.S. Patent
`
`Jun. 30, 2009
`
`Sheet 5 of 16
`
`US 7,554,930 B2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`\LZZZ| ||
`
`ç e infil
`
`dS]
`
`089
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jun. 30, 2009
`Jun.30,2009
`
`Sheet 6 of 16
`Sheet60f16
`
`US 7,554,930 B2
`US 7,554,930 B2
`
`__..______.
`
`_8nu002
`
`
`
`vaEamw
`
`$9.
`
`_m_=ou.\
`
`
`1lIIIt/Lwas
`mom5:5
`
`«mmon;03v
`
`--.ur_a.3a555;
`n11“Eimmm
`
`(omv523
`
`_...............e,-
`
`
`
`[I552.8\ESE
`
`(mm:own5:.in.
`
`9;.qu
`
`GUN?_fixed—:90\_O.__._D_
`
`mm5«S.
`
`_.4illom;
`43:”:actwwr.
`
`aBS9..“SEE
`
`_
`
`
`
`._um;”Rev_._/I5am“mum85.5;__actmma
`
`_11
`
`
`
`
`
`
`
`
`
`
`
`
`
`3:
`:1-
`‘3!
`
`v2:9”.
`
`
`.NovOnov
`
`
`
`iv3%.DDWWQHME—mlhu:3.
`
`
`
`\~In:I:.
`
`hm5m:
`
`
`
`
`
`.lllllllllll..Dowv.an...0an.:2.8a:2uno”.2__\._....__Oomv
`.mEmm...u:_
`lllllllll.m—v%
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Jun. 30, 2009
`
`Sheet 7 of 16
`
`US 7,554,930 B2
`
`
`
`
`
`
`
`3.“:«use:3.5m
`
`:53:53mun:
`
`32:n
`
`03n
`
`mm28:
`
`<m2:9”.
`
`
`
`Sm2%»DEW.2.5m
`
`Batu...—
`
`
`
`
`
`EIEE88888888.:55...:::8.8.83:
`395:.E595.may;35..
`
`gas-tumEu...—.:
`
`8.828:Ivanm0;Hoccoaooodcocccoc;ZZZ—.2:-___993—63I:28Ec888...8888q_:::_.::::
`
`
`38228:35359—
`
`255:5332:5:5EE—
`
`com233.Sanmuzmzmumn:
`
`._
`2»:.22.:—uuutuE—uucsgunm5?...322:.=
`
`
`
`HIE!8888......:::_»::::E
`82:O:mOm88.082_:.::_:_.::_:_06.02.3—
`
`
`
`
`ecoodcoo::.:_::_._:_::9.0.62.3.—
`
`
`
`
`
`oooo.oooc__:.:::2.22::o.~m.om_.o:
`
`
`
`oooo.ooco_:_.:222.222:odflonfo:
`
`
`
`
`

`

`U.S. Patent
`
`Jun. 30, 2009
`
`Sheet 8 of 16
`
`US 7,554,930 B2
`
`Route
`processing
`
`BGP route information I
`and IP statistics data
`from other POPs
`
`|
`
`
`
`
`
`
`
`
`
`
`
`Collect external BGP
`route information
`64D
`
`Collect IP statistics
`data
`620
`
`Correiate BGP route
`information and IP
`Statistics data
`830
`
`Route
`:
`processing
`:
`——T at the NOC
`(800)
`
`
`
`Build composite tables
`650
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Re-correlate IP
`Statistics data and
`route information
`660
`
`Route preference
`selection logic
`670
`
`Route deaggregation
`selection iogic
`680
`
`Distribute route
`information
`690
`
`* * * * * * * * * * * * * * * * * * me a
`
`
`
`implement route policy
`at each POP site
`695
`
`
`
`Route Policy
`Updata
`(1100A & 1100B)
`or (1100C)
`
`Figure 6
`
`

`

`U.S. Patent
`
`Jun. 30, 2009
`
`Sheet 9 of 16
`
`US 7,554,930 B2
`
`700
`
`Read external BGP
`routes from the router
`
`710
`
`Update cumulative
`route table entry
`
`720
`
`Obtain current #P
`statistics file from IP
`Statistics reader
`
`730
`
`Final
`Interval?
`740
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Read |P Statistics file with insertion filter
`on minimum packets and route entry
`coverage. Attach counts to route entries
`and count and store exceptions in the
`process.
`750
`
`Store files to be sent to the NOC:
`- Route entries
`- Filtered lP statistics
`- Exceptions
`- Interface Stats
`750
`
`Figure 7
`
`
`
`
`
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Jun. 30, 2009
`
`Sheet 10 of 16
`
`US 7,554.930 B2
`
`-
`
`Route Processing
`at the NOC
`
`80
`
`*
`/
`
`Receive PCR route entry tables 510 and
`|P statistics data tables 500
`
`815
`
`/
`/
`r
`
`|
`Build master route entry table using route entry tables from
`Hi? POPs
`812
`
`—— iBuild master IP statistics data table using IP statistics data i
`
`Filter using master route entry table.
`
`
`
`Master route entry
`
`| Master P statsiºs
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`iterate through a? the address/mask groups
`in the route entry table. Process Bach entry
`In each group using the Roºte Preference
`Selection Process (900)
`822
`
`Futer the routes to be preferenced by flag.
`Keep any Selected_\nject
`824
`
`
`
`
`
`Filter the preferenced routes by AS
`exclusion
`Bº?
`
`Current
`referenced li
`
`
`
`Master
`preferenced list
`
`
`
`
`
`
`
`
`
`Low pass filter the selected
`preferenced routes
`B2B
`
`i iterate through all the address/mask groups in the IP
`!
`statistics data table, Process each entry in Bath
`group using the Route Deaggregation Selection
`Process (1000)
`|B40
`
`|
`
`Filter the routes to be deaggragated by
`flag. Keep only Deaggregated
`§42
`
`
`
`Route entries
`
`Fitter the deaggregated routes by AS
`exclusion
`844
`
`Low pass ff?tar the 5elected
`deaggregation routes
`
`Store output files and transmit to the
`POPs
`
`Unselected route
`entries
`
`Deaggregation
`rotites
`
`Figure 8
`
`

`

`U.S. Patent
`
`Jun. 30, 2009
`
`Sheet 11 of 16
`
`US 7,554,930 B2
`
`Select route in route group
`
`905
`
`Set
`BELOW THRESHOLD
`910
`
`Clear
`SELECTED_NATURAL
`912
`
`Route Preference
`Selection Process
`
`900
`
`|
`|
`{
`|
`|
`l
`l
`|
`|
`|
`|
`|
`
`|
`i
`
`- * * * - - - - - - - - - - - - - - - - - - - - - - ºr m amº mº m = me m. m. |
`
`y
`
`This route
`violates MED?
`
`916
`
`* A
`N
`
`Sct
`HONOR MED
`918
`
`H
`y ; N
`922
`
`Shortest
`AS path?
`
`-
`
`Compare BGP
`parameters within
`route group
`
`|
`|
`|
`|
`|
`?
`|
`|
`|
`|
`|
`
`|
`|
`
`Set
`| HONOR AS
`924
`
`-
`
`-
`
`|
`|
`|
`|
`t
`|
`|
`|
`|
`|
`i
`|
`|
`|
`{
`|
`|
`|
`|
`|
`|
`|
`|
`|
`|
`|
`H
`|
`i
`|
`|
`|
`|
`|
`|
`|
`|
`|
`|
`|
`L - - - - - - - - - - - - - - - = * * * * * = - * = - - - - - - - - - - - - - - - - - - - - - - - - - - - - - J
`
`-
`
`-
`
`-
`
`N
`
`Packets -
`threshold
`NJ 960
`
`Y
`
`Clear
`BELow_THRESHOLD
`962
`
`End
`980
`
`Y
`
`route Selected
`naturally or prohibited?
`964
`
`
`
`Se!
`PREFERRED_TRANSIT
`974
`
`
`
`
`
`ransi
`available?
`972
`
`sELECTED_INIECT
`966
`
`970
`
`Y
`
`Figure 9
`
`

`

`U.S. Patent
`
`Jun. 30, 2009
`
`Sheet 12 of 16
`
`US 7,554,930 B2
`
`Route Deaggregation
`Selection Process
`
`Select route in route
`group
`
`1005
`
`
`
`
`
`
`
`Packets
`threshold?
`1010
`
`
`
`Corresponding route
`entry allow injection?
`
`
`
`N
`
`
`
`
`
`
`
`
`
`More
`specific route entry
`than parent on other
`peer?
`1025
`
`Set
`MORE SPECIFIC_PEER
`1027
`
`
`
`Set
`DEAGGREGATED
`1040
`
`Oelete
`Deaggregation route
`1030
`
`End
`1042
`
`Figure 10
`
`

`

`U.S. Patent
`
`Jun. 30, 2009
`
`Sheet 13 of 16
`
`US 7,554,930 B2
`
`
`
`Receive NOC preferred/
`deaggregated files
`
`1102
`
`1 100A
`
`Build a Preferred route file for
`the specific POP
`
`1 104
`
`install Local Preferences
`
`1106
`
`Compare existing
`deaggregations to generate a
`list of routes to be announced
`and a list to be withdrawn
`1108
`
`Verify the status of the routes
`we are deaggregating via a
`BGP "Soft in"
`
`1110
`
`Write the announcements and
`withdrawals to a file
`
`1112
`
`issue the announcements and
`withdrawals
`
`1114
`
`Figure 11A
`
`

`

`U.S. Patent
`
`Jun. 30, 2009
`
`Sheet 14 of 16
`
`US 7,554,930 B2
`
`
`
`
`
`
`
`
`
`
`
`BGP
`Announcements
`and withdrawals
`1 120
`
`
`
`
`
`
`
`Wait to receive
`announcements and
`withdrawals through
`BGP
`1122
`
`
`
`
`
`Compare announcements and withdrawals to
`the existing deaggregations to generate a list of
`routes to be announced and a list to be
`withdrawn
`1124
`
`
`
`
`
`
`
`
`
`Write the
`announcements and
`withdrawals to a file
`
`1126
`
`?ssue the
`announcements and
`withdrawals
`
`1128
`
`
`
`
`
`
`
`Figure 11B
`
`

`

`U.S. Patent
`
`Jun. 30, 2009
`
`Sheet 15 of 16
`
`US 7,554,930 B2
`
`
`
`Receive NOC
`preferred and
`deaggregated files.
`1150
`
`1 100C
`
`Read current
`configuration from
`router
`
`1151
`
`Build a Preferred route
`changes file
`
`1 152
`
`Build a deaggregated
`route changes file
`
`1154
`
`Install BGP local
`preferences and
`deaggregated routes
`
`1156
`
`Figure 11C
`
`

`

`U.S. Patent
`U.S. Patent
`
`Jun. 30, 2009
`Jun. 30, 2009
`
`Sheet 16 of 16
`Sheet 16 of 16
`
`US 7,554,930 B2
`US 7,554,930 B2
`
`_
`
`
`
`.Inmnon.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`35m..ii.IIIIIII\\..L.\rII..._mufimfillhymn—~—uuuwflhflwflm.3:23:Buy—an:61.1!}on"3:03€vaIU.3.5m:55.—.Euum.1,80.:nemv5.30m.035—;
`
`
`
`
`
`
`
`
`.03:55.,
`
`
`
`_\.=I“wan—~—._u>2.2.LISIJFJl
`353305:25'a:a":8.u>_quM5.5:2:53.a.t3.ux3.33%Sigma2$33.
`
`
`
`
`
`
`
`
`
`
`
`_E.8:235sfifim
`
`_.3:05:00333.5:58:.
`
`
`
`—
`
`\i..........................I.....
`
`3:\\\llllllllllllI/
`
`3:05:00.5._.3E._«9:
`
`002602V528.28:n3:235a._5:5
`«amvaAUOZV—Qhfisuom_D—N—JQD
`
`
`a..30$J..r5800:2585”..
`I——.._5:._050M
`.flllllllll.I
`
` .lX.2;x2:.__233*n22QOmcfimuoofia:.‘fim'_AIu.5,._ux”2.5m__min.1/so...
`
`
`ummD.........IV5:95:00:5u.Wm.//305Show,..x.‘\‘e.lllllllllllllllllII\
`
`
`—DDAIum.”mar—gall.Iww"S:_
`
`a:a:85ccum_wEmmqum"2mm5—u.5030$
`.23mena:.:a0.5E_
`
`\llllllllllllllllllll
`
`305m."—
`
`
`
`
`

`

`US 7,554,930 B2
`
`1
`INTERNET ROUTE DEAGGREGATION AND
`ROUTE SELECTION PREFERENCING
`
`CROSS REFERENCE TO RELATED
`APPLICATION
`
`This application is a divisional application and claims the
`benefit of copending U.S. patent application Ser. No. 09/594,
`461, filed Jun. 14, 2000, which application is hereby incor
`porated by reference.
`
`10
`
`BACKGROUND
`
`2
`points used for this data transferare geographically dispersed,
`this type of routing creates an asymmetric routing path
`between two network terminations whereby one “to’’ path
`travels primarily on the destination peer’s network and the
`“from path travels primarily on the originator’s network. If
`the amount of bandwidth used is symmetric in both directions
`and the two networks have similar geographic scope then this
`creates a fair economic exchange. Each peer carries half the
`bandwidth and each peer has (presumably) one paying cus
`tomer to pay for its half of the transfer. This is the basic barter
`proposition underlying Internet peering.
`However, although Internet peering models are generally
`based upon the assumption of symmetric bandwidth between
`peers, this assumption has proven to be flawed. The growth of
`the WWW and increases in WWW traffic have exacerbated
`the problem of bandwidth asymmetry. Web content providers
`tend to transmit copious amounts of data. Bandwidth between
`Web content providers and the individuals who view Web
`content is often unbalanced. Web content providers typically
`send as much as 4 to 10 times more bandwidth than they
`receive. An individual might request a Web page by sending
`just a single address or page request, whereas the Web page
`content provider returns multiple Web pages to the individual,
`thereby consuming large amounts of bandwidth.
`For example, consider a scenario between ISPA, servicing
`an individual, and ISP B, servicing a Web content provider.
`ISPA and B both use hot-potato routing, dumping network
`traffic off at the closest entry point to the peering ISP. ISPA
`receives a request for a Web page, and routes the request such
`that the request is carried by ISP B for a majority of the
`distance traveled (hot potato routing). ISP B returns the
`requested Web page, constituting a considerably larger
`amount of bandwidth than the initial request from the indi
`vidual. ISP B similarly uses hot potato routing, which results
`in ISP A carrying the Web traffic for the majority of the
`distance traveled. ISPA is forced to carry more than its fair
`share of the bandwidth traffic burden in this scenario. Fur
`thermore, ISPA is unable to charge its own customers more
`for the extra bandwidth, because the entity originating the
`extra bandwidth is a customer of ISP B. The current peering
`system does not provide the proper economic incentives for
`an ISP to increase its bandwidth, because the increased band
`width may be consumed by the ISP’s peers.
`Web content providers are often constrained by the band
`width limitations they experience through their ISP. Some
`Web content providers attempt to solve this problem by
`becoming multi-homed, i.e., by contracting for service with
`multiple ISPs to purchase additional bandwidth capacity and
`presumably to purchase redundancy. However, the addition
`of redundant paths to each potential client terminal results in
`increased complexity. Being multi-homed requires thinking
`and acting like a backbone Internet network operator, and
`having the capability to properly route traffic.
`The resulting burden of best path management is a difficult
`task and not one that will likely be mastered by most Web
`content providers. The Border Gateway Protocol (BGP)
`(which is used to route data between networks on the Internet)
`is a poor tool, with limited best path information available to
`the automated decision making process in the router. Micro
`engineering good connectivity to many providers requires
`substantial knowledge of not only the BGP protocol and its
`rules but also requires substantial knowledge of the network
`structure and operational capabilities of the downstream pro
`viders themselves.
`Thus Web content providers, as well as other Internet con
`sumers, need a system allowing them to purchase large
`amounts of network bandwidth without requiring each Web
`
`15
`
`20
`
`25
`
`30
`
`35
`
`1. Field of the Invention
`The present invention relates generally to network routing,
`and more particularly, to dynamically determining regional
`address locations for best exit routing based upon route
`deaggregation and route selection preferencing.
`2. Background of the Invention
`The growth of the Internet, and the World Wide Web
`(WWW) in particular, has led to enormous increases in the
`amount of traffic flowing over the group of connected net
`works that comprise the Internet and connected network sys
`tems. Access providers such as Internet Service Providers
`(ISPs) provide connections for businesses and individuals to
`connect to the Internet and access the WWW. ISPs must
`interconnect in order to allow their customers to reach points
`on the Internet serviced by other ISPs.
`The exchange of traffic between Internet service providers
`(ISPs), where traffic from one ISP’s customers is destined for
`customers of another ISP is referred to as “peering.” This is
`contrasted with “transit,” where the traffic that is exchanged is
`destined not only for the receiving ISPs customers, but also
`for other users throughout the Internet (which are in turn
`reached via the receiving ISPs peering connections). ISPs
`generally charge for transit connections, while peering con
`nections do not involve an exchange of money. Therefore,
`peering provides free bi-directional exchange of customer
`traffic between ISPs whereas transit provides paid access to
`the entire Internet. For example, large ISPs with their own
`40
`national backbones often mutually agree with other large
`ISPs with national backbones to freely exchange their cus
`tomer data. An Internet backbone is the central part of an
`ISP’s network which transports data between edge, or
`regional, parts of the networks and Internet peering points.
`Instead of peering, large ISPs that have a national backbone
`offer transit service to smaller, regional ISPs who cannot offer
`reciprocal backbone sharing. These smaller ISPs use the
`larger ISPs national backbones to reach users outside of their
`service areas.
`Peering connections are based upon the underlying
`assumption that traffic flows between two different ISPs will
`be approximately equal. These mutual agreements to
`exchange information traffic (bandwidth) freely and without
`charge do not make economic sense if one peering partner is
`forced to carry substantially more traffic than another. Unbal
`anced bandwidth may affect peering relationships because
`most peered data is routed between peers using a routing
`method called “hot potato routing.”
`In hot potato routing, an originating peer network carrying
`a customer’s traffic finds the nearest entry point to the desti
`nation peer’s network and drops the traffic off as soon as
`possible. There is no incentive for a carrier to transport addi
`tional bandwidth if a peer network is available to carry the
`traffic. Likewise, the destination peer network will send
`returning data to the originator’s network from its nearest
`entry point into the originator’s network. If the two exchange
`
`45
`
`50
`
`55
`
`60
`
`65
`
`

`

`US 7,554,930 B2
`
`3
`content provider to become an expert at Internet routing.
`However, because Web traffic contributes substantially to the
`peering bandwidth asymmetry problem, a method is required
`to compensate all network carriers for the Web bandwidth
`they carry, including Web traffic that originates in a network
`peer. An economically rational system is needed for provid
`ing Web bandwidth, whereby Web content providers pay the
`true cost of their service and ISPs are paid for the Web band
`width that crosses their network systems.
`
`SUMMARY OF THE INVENTION
`
`4
`received at each POP entry point from various IP address
`ranges is gathered at each POP. The POP data is sent to the
`NOC for processing.
`The NOC develops “best route” information, which is dis
`tributed back to the set of POPs and the interconnected peer
`ing partner networks. The “best route” information ensures
`that traffic is properly routed through preferred routes on the
`intelligent routing network, keeping traffic on the backbone
`when possible, and avoiding inefficient routing. The NOC
`also selects new routes to be injected into the intelligent
`routing network in order to further improve the accuracy of
`the address space map.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1A is an illustration of a network using typical peering
`and transit connections between different ISPs.
`FIG. 1B is an illustration of “hot potato routing” and “cold
`potato routing” between two ISPs.
`FIG. 2A is an illustration of connections between different
`ISPs.
`FIG. 2B is an illustration of the deaggregation of the
`address space of an ISP in an embodiment of the present
`invention.
`FIG. 3 is an illustration of an intelligent routing system in
`an embodiment of the present invention.
`FIG. 4 is an illustration of a portion of an intelligent routing
`system in an embodiment of the present invention.
`FIG. 5A is an illustration of an IP statistics data table in an
`embodiment of the present invention.
`FIG. 5B is an illustration of a route entry table in an
`embodiment of the present invention.
`FIG. 6 is a flow diagram of the process of monitoring route
`information and distributing route information in an embodi
`ment of the present invention.
`FIG. 7 is a flow diagram of route processing at the Point of
`Presence (POP) Collector in an embodiment of the present
`invention.
`FIG. 8 is a flow diagram of the route processing at the
`Network Operations Center (NOC) in an embodiment of the
`present invention.
`FIG. 9 is a flow diagram of the route preferencing selection
`process in an embodiment of the present invention.
`FIG. 10 is a flow diagram of the route deaggregation selec
`tion process in an embodiment of the present invention.
`FIG. 11A is a flow diagram of periodic route processing at
`the POP injector in an embodiment of the present invention.
`FIG. 11B is a flow diagram of continuous route processing
`at the POP injector in an embodiment of the present invention.
`FIG. 11C is a flow diagram of route processing at the POP
`injector in another embodiment of the present invention.
`FIG. 12 is an illustration of information and processing
`flows in an intelligent routing system in an embodiment of the
`present invention.
`
`DETAILED DESCRIPTION OF THE PREFERRED
`EMBODIMENTS
`
`Reference will now be made in detail to several embodi
`ments of the present invention, examples of which are illus
`trated in the accompanying drawings. Wherever practicable,
`the same reference numbers will be used throughout the
`drawings to refer to the same or like parts.
`Introduction
`FIG. 1A provides background information on existing sys
`tems for carrying Internet and Web traffic. FIG. 1A shows a
`communications network 100. Network 100 includes three
`
`5
`
`10
`
`15
`
`20
`
`25
`
`The present invention allows Web content providers and
`other Internet bandwidth consumers (“content providers”) to
`obtain the Internet bandwidth they require, while providing a
`system for paying access providers on a per-bit basis for the
`traffic they carry. The system manages and facilitates the
`routing of traffic within the system through the development
`of a topological “address space map” of the system to enable
`a “best route” selection process. The “topology” of the net
`work is analogous to the geography of the network in circuit
`route distances. Content providers do not have to be con
`cerned with multi-homing routing issues, and access provid
`ers are assured that they will be paid for the use of their
`network.
`An intelligent routing exchange system comprises a back
`bone interconnected to a set of peering partner networks. The
`backbone is used to carry long-haul traffic. A central Network
`Operations Center (NOC) develops a topological address
`30
`space map of the overall intelligent routing network, and
`performs routing management. The intelligent routing man
`agement system ensures that bandwidth is requested and
`delivered regionally to peering partner networks, and that
`traffic is carried by the backbone for long haul data distribu
`tion in both directions. The exchange system uses cold potato
`routing for all traffic being sent to regional carriers, and hot
`potato routing for all traffic received from regional carriers.
`By ensuring that peering partners carry only regional traffic,
`the peering partners no longer suffer from unfairly carrying
`asymmetric bandwidth from peer access providers.
`The backbone is connected to a pool of peering partner
`networks through a set of regional Points of Presence (POPs)
`on the backbone. The peering partners are well-connected
`major traffic carriers who typically connect to multiple POPs.
`Contracts with each peering partner will be negotiated to
`ensure that the overall intelligent routing system provides
`sufficient bandwidth fortransferring traffic onto and offof the
`backbone.
`Customers of the intelligent routing system connect to the
`intelligent routing system at one of the POPs. A customer may
`be, for example, a Web hosting company, an individual Inter
`net Service Provider, or a corporate customer. Each customer
`signs up for the intelligent routing system service, and obtains
`a specific POP connection location.
`Each peering partner is paid a fee forevery bit sent from the
`backbone across their network to their access customer ter
`minations. Customers are billed on a pro-rata basis based
`upon their actual utilization of the backbone.
`Implementing the regional delivery of all traffic on the
`backbone requires detailed information about the topological
`locations of groups of Internet Protocol (IP) addresses within
`the interconnected peering partner networks, relative to the
`location of entry points to the backbone. The central NOC
`develops an address space map providing such detailed infor
`65
`mation about the intelligent routing network by monitoring
`the network traffic. Information on the amount of traffic
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`

`

`5
`Internet Service Providers (ISPs) 110, 120, and 130 and a
`representation of the Internet 140. ISP 110 includes a point
`112; ISP 120 includes a point 122; ISP 130 includes a point
`132; and the Internet 140 includes a point 142. Each point
`represents a particular Internet Protocol (IP) address within
`the network 100. Each ISP represents a set of equipment and
`telecommunication lines providing Internet access for a cer
`tain geographic region. An ISP provides an Internet connec
`tion to various individuals and companies, wherein each indi
`10
`vidual and company has an IP address or IP address range.
`The Internet 140 represents the worldwide system of com
`puter networks, of which one part is the World Wide Web
`(“the Web” or “WWW").
`Individual ISPs 110, 120 and 130 are not each individually
`connected to all network 100 destinations. ISPs 110, 120 and
`130 use a system of peering and transit connections to access
`other parts of the network 100. Peering and transit connec
`tions allow regional networks to offer access to out-of-net
`work destinations by negotiating for the use of other regional
`networks. ISPs often interconnect at network focal points
`such as the Network Access Points in the United States and at
`regional or international switching points. Connecting ISPs
`exchange routing information with each other, typically using
`the Border Gateway Protocol (BGP).
`25
`Peering connection 150 connects ISP 110 and ISP 130. A
`peering connection is a negotiated agreement between two
`network carriers to allow for a mutual traffic exchange. As
`shown in FIG. 1A, in order to permit point 112 of ISP 110 to
`access point 132 of ISP 130, the ISPs 110 and 130 exchange
`traffic across peering connection 150.
`Transit connection 160 connects ISP 120 with the Internet
`140. A transit connection passes through one network to
`connect to a second network. For example, as shown in FIG.
`1A, in order for point 142 of the Internet 140 to be reached by
`point 122 of ISP 120, it is necessary for traffic to be routed
`across ISP 110.
`FIG. 1B is an illustration of “hot potato routing” and “cold
`potato routing” between two ISPs in a network 190. ISP 110
`and ISP 130 are connected via two different peering connec
`tions 150A and 150B. ISPs that exchange peering traffic
`(