Classifications

• • H—ELECTRICITY
  • H04—ELECTRIC COMMUNICATION TECHNIQUE
  • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
  • H04L12/00—Data switching networks
  • H04L12/28—Data switching networks characterised by path configuration, e.g. LAN [Local Area Networks] or WAN [Wide Area Networks]
  • H04L12/2854—Wide area networks, e.g. public data networks
  • H04L12/2856—Access arrangements, e.g. Internet access
  • H04L12/2858—Access network architectures
  • H04L12/2859—Point-to-point connection between the data network and the subscribers
• • H—ELECTRICITY
  • H04—ELECTRIC COMMUNICATION TECHNIQUE
  • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
  • H04L12/00—Data switching networks
  • H04L12/54—Store-and-forward switching systems 
  • H04L12/56—Packet switching systems
  • H04L12/5691—Access to open networks; Ingress point selection, e.g. ISP selection
• • H—ELECTRICITY
  • H04—ELECTRIC COMMUNICATION TECHNIQUE
  • H04Q—SELECTING
  • H04Q11/00—Selecting arrangements for multiplex systems
  • H04Q11/04—Selecting arrangements for multiplex systems for time-division multiplexing
  • H04Q11/0428—Integrated services digital network, i.e. systems for transmission of different types of digitised signals, e.g. speech, data, telecentral, television signals
  • H04Q11/0478—Provisions for broadband connections
• • H—ELECTRICITY
  • H04—ELECTRIC COMMUNICATION TECHNIQUE
  • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
  • H04L12/00—Data switching networks
  • H04L12/54—Store-and-forward switching systems 
  • H04L12/56—Packet switching systems
  • H04L12/5601—Transfer mode dependent, e.g. ATM
  • H04L2012/5619—Network Node Interface, e.g. tandem connections, transit switching
  • H04L2012/562—Routing
• • H—ELECTRICITY
  • H04—ELECTRIC COMMUNICATION TECHNIQUE
  • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
  • H04L12/00—Data switching networks
  • H04L12/54—Store-and-forward switching systems 
  • H04L12/56—Packet switching systems
  • H04L12/5601—Transfer mode dependent, e.g. ATM
  • H04L2012/5619—Network Node Interface, e.g. tandem connections, transit switching
  • H04L2012/5621—Virtual private network [VPN]; Private-network - network-interface (P-NNI)

Definitions

• This invention pertains generally to routing information packets in a network involving a plurality of traffic carrying networks, and more particularly to an improvement in routing described in U.S. Patent 6,009,081.
• the present invention is an improvement on the invention of improvement in routing described in U.S. Patent 6,009,081 , and assigned to the assignee hereof. Additional background information can be found the aforesaid patent, as well as in the book entitled
• a PNAP or "Private Network Access Point” can be thought of as being made up of two halves. One half connects to customers. The other half connects to NSPs or "National Service Providers".
• the Internet is a network of networks.
• a PNAP contains an ASimilater that determines the Internet interconnection matrix.
• ASimilater servers residing within the PNAP collect and collate the routing data received from Network Service Providers (NSPs) to build a database of how the Internet is interconnected.
• the database shows the NSPs connected to the PNAP are interconnected as well as how they are connected to their customers.
• the PNAP receives each NSP's perspective of the Global Routing Table which, when collated, includes identical routes from multiple NSPs, and that distillation of the sum of each NSP's view of the Global Routing Table is used to direct traffic from the customer to the destination over the optimal path via another PNAP customer if available or, otherwise, one of the NSP's connected to the PNAP.
• PNAP is provided with access to the PNAP's optimized version of the Global Routing Table so that the customer will also have the ability to know the best route for a particular destination.
• the PNAP customer can, based on information provided by the PNAP, send the information to the destination through that commonly connected NSP.
• a further aspect of the invention provides for routing traffic for customers who are not massively multi-homed, but are connected to more than one PNAP.
• FIG. 1 is a schematic diagram showing two PNAPs with multi -homed customers according to an embodiment of the invention.
• FIG. 2 and FIG. 3 are flow charts showing a method of the invention for causing traffic between two customers of the same PNAP to be exchanged through the PNAP without transiting over the Internet.
• FIG. 4 is a schematic diagram of a customer multi-homed to a PNAP and a plurality of NSPs in accordance with the invention.
• a first PNAP 20 and second PNAP 20a are both shown as a circle with a vertical dashed line 21 dividing it in half. While more customers would typically be connected to the PNAPs 20, 20a, the left half of the PNAPs 20, 20a are shown connected to two customers 1, 2 as an example to simplify the discussion. Furthermore, while two PNAPs 20, 20a are shown, there could be one or any other number of PNAPs. While customers 1, 2 are both shown connected to two PNAPs, a customer may be connected only to one PNAP or any other number of PNAPs.
• PNAP 20 will be referred to herein for simplicity, the discussion is applicable to PNAP 20a as well.
• the right half of the PNAP 20 is connected to a plurality of NSPs A, B, C, D, ... N which, in turn, form the Internet 22 to which Internet users, such as destinations 3, 4 are also connected.
• NSPs A-N do not exchange traffic among themselves through the PNAP 20. Traffic exchanges between NSPs A-N takes place at public or private peering points (not shown).
• the customers 1, 2 typically route their traffic through the PNAP 20 from the left half to the right half.
• the PNAP 20 then selects the path from the customers 1, 2 to the destinations 3, 4.
• the PNAP 20 contains an ASimilater that determines how everyone on the Internet 22 is connected to everyone else.
• ASimilater will be used synonymously with the term “ASsimilator” in that patent.
• Border Gateway Protocol, version 4 protocol (BGP4) used therein encompasses the concept of a "Global Routing Table” which may be defined as the list of all routes visible to each provider, both of its customers as well as its peers and their customers, of everyone to which they are connected.
• an ASimilater server inside the PNAP 20 receives a data "dump" of the Global Routing Table from each of its NSPs A-N, and collates the data together to build a database of how the Internet 22 is interconnected.
• the database shows how all of the NSPs A-N are connected together as well as connections to their customers.
• the ASimilater takes a dump of the Global Routing Table from each NSP A-N.
• the ASimilater collates the data from each NSP's perspective of the Global Routing Table. 3. The ASimilater builds a summed Global Routing Table database of the Internet
• the ASimilater determines which routes are NSP A's customers and so on for all customers and for all other NSPs B-N. As a clarification, note that each NSP is also sending routes of all other NSPs to which it is connected.
• the routing table inside the PNAP 20 also maps a plurality of routes from customer 1 to customer 2 that go through the NSPs A-N.
• FIG. 2 and FIG. 3 are method flow charts.
• the method begins at block 30 and proceeds to block 31 which is the step of causing the router within the PNAP to list the direct route through the PNAP as one of its routes between two customers connected to the PNAP.
• the step of the next block 32 is causing the level of preference for the direct path to be higher than for any other routes between the two customers.
• the step of the next block 33 is causing the router protocol to select the direct route as being the best path between the two customers.
• the last block 34 of FIG. 2 is "end" .
• FIG. 2 is "end" .
• the method begins at block 36.
• the first step in block 37 is causing the customer router to forward a packet from customer 1 to customer 2 over the PNAP link.
• the next step in block 38 is causing the PNAP router to forward the packet from customer 1 over the direct PNAP path to customer 2 without transiting a service provider backbone.
• the last block 40 of FIG. 3 is "end".
• Path latency can, for example, result from delay between the time when a device receives a frame and the time that frame is forwarded out the destination port, or the delay caused by a shift to a more circuitous path due to an outage.
• the routers within the PNAP are used to forward packet traffic through the Internet 22 in an optimized fashion.
• the routers build routing tables that contain their distillation of the summed Global Routing Table resulting in the best paths to all the destinations from the PNAP's perspective. They both advertise and receive route information to and from other routers.
• the routers keep track of next hop information that enables a data packet to reach its destination. A router that does not have a direct physical connection to the destination checks its routing table and forwards the packet to its next hop; that is, a router that it is directly connected to and is closer to that destination.
• a customer may be preferred for a customer to use its pipe to NSP D for communicating with destinations that are connected to NSP D and to use the PNAP (and its external connections to NSPs A-N) for all other destinations.
• the optimized and distilled Global Routing Table would be sent to the PNAP customer.
• the BGP4 attribute known as the "community" would be used to tag NSP C customer routes as determined by ASimilater with the PNAP NSP C customer community. Since the customer has complete control over outbound traffic, the customer can set the local preference in its router to tag a particular route of multiple identical routes from multiple sources as the preferred route. The higher the local preference, the more preferred the route.
• any routes tagged with the PNAP's community for NSP D could have their local preference set to 50 and every other route (not tagged) set to 150.
• the customer could leave all routes at local preference 100 which is the default. This allows the customer to optimize their routing so that the direct pipe to NSP D is used for destinations on NSP D and the PNAP 20 is used for other destinations, thus providing effective and optimized use of both the customer's PNAP and NSP pipes based on the ASimilater information related to said customer over the PNAP BGP feed.
• the data packet is transmitted from customer 1 over link 24 to the left half of the PNAP 20.
• the PNAP routing infrastructure within the PNAP 20 will have determined a plurality of paths to destination 3. These different paths to the same destination are listed in a routing table along with a parameter indicating the degree of preference attached to each route of a set of the different paths.
• the PNAP 20 picks the best path for the traffic to traverse to reach destination 3.
• the data packet leaves the right side of the PNAP 20 via the selected one of the NSPs A-N, follows the selected best path through the Internet 22, and reaches destination 3.
• two customers connected to the same PNAP 20 see the PNAP 20 as the best path, and exchange traffic with each other through the PNAP 20 without ever going out over the backbones of the NSPs A-N. Or, if a PNAP customer is directly connected to a particular NSP to which a destination is also connected, the
• PNAP customer can utilize that NSP connection to send the traffic to the destination based on the ASimilater information received over the BGP peering with the PNAP.
• the routing table inside the PNAP 20 would list the direct connection from customer 1 to customer 2 through the left half of the PNAP 20 over the dotted path 25 as the optimum route. This means that communications between customer 1 and customer 2 who are connected to the PNAP 20 should always use the dotted path 25 as the preferred path unless a failure or flaw prevents that path from being used.
• Each PNAP has it's own BGP AS and is completely distinct from the routing perspective of the other PNAPs with no private backbone connecting the PNAPs.
• Each PNAP is, however, connected to the same fabric of NSPs as all other PNAPs.
• the levels of bandwidth to a PNAP may be larger or smaller depending on it's location but the fabric is the same.
• PNAPs PNAPs.
• routing of traffic inbound from an NSP over the pipe to said NSP is easy. All of these NSPs attach a higher local preference to the routes heard from their customers over those same routes heard from their peers. Routing outbound traffic in a massively multi-homed network is much more difficult. Faced with such a multiplicity of links, the question of how to route traffic in a tightly controlled fashion is one of great importance in attaining the highest performance.
• PNAPs to route traffic between them. This allows us to choose the fastest NSP between any two PNAPs, and thus allows us to offer the optimal path between our customers and the
• a customer is connected to NSP C and a PNAP, we can offer our customer all of NSP C and
• NSP C's customers routes tagged with a specific community Inter NAP community, in this case
• NSP B customer routes over the NSP B link. 5 (c) All others over the PNAP link.
• NSP B NSP A PNAP
• NSP A routes are assigned a local pref of 90 and all of the other routes heard from NSP A are assigned a local pref of 45. If you were to see a route tagged at a local pref of 45 in your IBGP, that would signify a non-NSP A route announced to the customer over the customer's BGP peering with NSP A.
• this local pref hierarchy is that of the routes that we know are not NSP B or NSP A, highest local pref wins on the PNAP link.
• the fall-through local pref value is used in the case of multiple routes heard over > 1 of your connections. Multi-homed customers of the PNAP, NSP A, and NSP B would use the PNAP and, if that link was not available, the NSP A link followed by NSP B. Multi-homed customers of NSP B and NSP A would, in the example above, use NSP A followed by NSP B.
• NSP A or NSP B in the case of a multi-homed customer of both is entirely at the customer's discretion. That behavior is easily modifiable by switching the primary and fall-through local pref sets of NSP A and NSP B.
• Example 1 The following is an example of implementing this approach with NSP A.
• NSP A peer neighbor xxx.xxx.xxx.xxx remote-as neighbor xxx.xxx.xxx.xxx send-community neighbor xxx.xxx.xxx.xxx remote-as NSP A neighbor xxx.xxx.xxx.xxx version 4 neighbor xxx.xxx.xxx.xxx distribute-list 1 out neighbor xxx.xxx.xxx.xxx route -map NSP A-IN in neighbor xxx.xxx.xxx.xxx route-map NSP A-OUT out neighbor xxx.xxx.xxx.xxx filter-list 1 out
• ip as-path access-list 1 permit " $ ip as-path access-list 2 permit .
• ip as-path access-list 10 deny " NSP A_NSP B_.
• ip as-path access-list 10 deny " NSP A_XXXX_.* route-map NSP A-OUT permit 10 ! only allow customer 5 IBGP sourced routes match as-path 1
• Internap Router neighbor xxx.xxx.xxx.xxx remote-as XXXX neighbor xxx.xxx.xxx.xxx send-community neighbor xxx.xxx.xxx.xxx version 4 neighbor xxx.xxx.xxx.xxx distribute-list 1 out neighbor xxx.xxx.xxx.xxx route-map PNAP-IN in neighbor xxx.xxx.xxx.xxx route -map PNAP-OUT out neighbor xxx.xxx.xxx.xxx filter-list 1 out
• ip as-path access-list 1 permit ⁇ $ ip as-path access-list 2 permit .
• route-map PNAP-OUT permit 10 ! only allow customer 5 IBGP sourced routes ! this is already being accomplished by the distribute-list ! out but this routemap is where you can adjust your AS ! prependings. match as-path 1
• NSP B Router neighbor 144.228.98.5 remote-as NSP B neighbor 144.228.98.5 version 4 neighbor 144.228.98.5 distribute-list 1 out neighbor 144.228.98.5 route-map NSP B-IN in neighbor 144.228.98.5 route-map NSP B-OUT out neighbor 144.228.98.5 filter-list 1 out ip as-path access-list 1 permit " $ ip as-path access-list 2 permit .
• ip as-path access-list 10 deny " NSP B XXXX .* ip as-path access-list 10 deny "NSP B NSP A_.* ip as-path access-list 10 deny "NSP B 1664 .*
• route-map NSP B-OUT permit 10 ! only allow customer 5 IBGP sourced routes ! this is already being accomplished by the distribute-list ! out but this routemap is where you can adjust your AS ! prependings. match as-path 1
• route-map NSP B-IN permit 10 ! deny all NSP A, and PNAP routes and set a low ! primary local pref match as-path 10 set local-preference 80
• the local-preference hierarchy of generic Diversity + is intended to address the problem of multi-PNAP routing by creating an interlocking set of preference steps for path selection.
• generic Diversity + supports up to two PNAP transit connections and multiple, other NSP transit connections.
• Each primary level of local-preference has a corresponding secondary value used as a backup should the primary become invalid.
• the complete hierarchy is shown below.
• routes to customers of that PNAP are set to 400.
• the value is still set to 400 and the length of the AS path is left to break the tie, meaning the direct link to the PNAP sourcing those customer routes will be used as the AS path will be shorter.
• routes over the primary link to customers of that PNAP will be set to 400, while routes over the secondary link to those same customer routes will be set to 350.
• Routes belonging to NSPs and their customers directly connected to the primary PNAP are set to 300, while routes belonging to NSPs and their customers directly connected to the secondary PNAP are set to 250. This results in traffic being sent through the primary PNAP if the primary PNAP has a given NSP in its border fabric. If the secondary PNAP has an NSP in its border fabric not common to the primary PNAP, or if an NSP common to them both fails at the primary, the traffic will be sent through the secondary for those destinations.
• routes to that NSP through the primary PNAP will be set to 200, rather than 300. If an NSP connection at the secondary PNAP fails, routes to that NSP through the secondary PNAP will be set to 150, rather than 250.
• the default value of 100 is generally not used for routes through a PNAP and is instead allocated for cases in which a customer has a connection to another NSP in addition to a PNAP.
• the values below 100 are used for customer NSP routes heard through the PNAP.
• the routes heard via the primary PNAP from the NSP to which the customer has a direct connection are set to 90.
• the same routes heard from the secondary PNAP are set to 80. Both of these cases assume the PNAPs have the NSP in their border fabric. If the customer has a connection to an NSP not found in the border fabric of the primary PNAP, those routes heard through the primary PNAP for destinations within that NSP are set to 70. If such is the case with the secondary PNAP, those routes are set to 60. Determining Primary and Secondary
• a customer is connected to more than one PNAP in a given city or region and the primary and secondary PNAPs can be determined based on traffic levels within the PNAPs, provider fabric, or other concerns.
• the multiple PNAPs are not all geographically close, a simple primary/secondary configuration may result in sub-optimal routing both in and out of the customer network.
• PNAP In cases when a customer is connected to multiple, geographically diverse PNAPs the preferred configuration is to have multiple primaries, one per region. In this way, PNAP
• NSPs will use their IGP cost for inbound traffic and the customer can similarly use their own IGP cost for outbound traffic. Care must be taken to properly announce prefixes to control regional traffic flows. Customers with such disperse PNAP connectivity should announce both their aggregate networks as well as more specific, regional prefixes.
• This multiple primary PNAP model can be extended to an arbitrary number of regions, but within a single region, there must be a single primary.
• A is the primary, with connections to NSP C, NSP D, while B is the secondary, with connections to NSP C, NSP D, and NSP E.
• PNAP Data for Customer Configuration PNAP A
• NSP Fabric NSP D (AS 1239) NSP C (AS 701)
• NSP Fabric NSP D (AS 1239) NSP C (AS 701) NSP E (AS 3561)
• Origin IGP metric 0, localpref 400, valid, external, best Customer-CPE > sho ip bgp 137.99.0.0 BGP routing table entry for 137.99.0.0, version 1304669 Paths: (2 available, best #2) 6993 1239 209 172.18.24.33 from 172.18.24.33 (172.18.24.1) Origin IGP, metric 0, localpref 150, valid, external XXXXX 1239 209 10.8.230.1 from 10.8.230.1 (10.8.230.1)
• Origin IGP metric 0, localpref 200, valid, external, best

Landscapes

• Engineering & Computer Science (AREA)
• Computer Networks & Wireless Communication (AREA)
• Signal Processing (AREA)
• Data Exchanges In Wide-Area Networks (AREA)

Priority Applications (4)

Applications Claiming Priority (4)

Publications (1)

Family

ID=27006982

Family Applications (1)

Country Status (6)

Cited By (11)

Families Citing this family (2)

Citations (2)

Family Cites Families (3)

• 2000
  • 2000-08-16 CA CA002383092A patent/CA2383092A1/en not_active Abandoned
  • 2000-08-16 MX MXPA02001585A patent/MXPA02001585A/es unknown
  • 2000-08-16 WO PCT/US2000/022470 patent/WO2001013585A1/en not_active Application Discontinuation
  • 2000-08-16 EP EP00957488A patent/EP1210795A4/en not_active Withdrawn
  • 2000-08-16 AU AU69099/00A patent/AU775473B2/en not_active Ceased
  • 2000-08-16 CN CN00814353.6A patent/CN1379939A/zh active Pending

Patent Citations (2)

Non-Patent Citations (1)

Also Published As

Similar Documents

Legal Events