Connectionless network express route

FIELD OF THE INVENTION

0001The present invention relates to connectionless networks such as IP networks for example, and in particular to the provision of express or priority routes for priority traffic.

BACKGROUND OF THE INVENTION

0002Communications systems increasingly use connectionless networks such as internet protocol (IP) networks for example. Connectionless networks comprise a number of network elements such as routers for example, which are connected together according to some topology. Traffic introduced into the network at a network element and destined for another element including an access element at the network periphery for example is directed across the network according to forwarding tables in each of the network elements it passes through. The forwarding tables in each element map the traffics end destination in the network onto a network element directly connected to the current element. In this way traffic across the network makes a series of short hops from network element to network element according to each elements forwarding tables. The forwarding tables are created automatically by distributed software programmes and protocols called routing protocols (eg OSPF or BGP<b>4</b>) as a result of routing guidelines provided by network operators and designers.

0003Because of the size and complexity of many networks, together with the practical difficulties of predicting traffic flows through the network, congestion points or bottlenecks can result in practical networks. While forwarding tables of network elements can be amended to try to mitigate congestion in other elements, this can have a knock on effect on the rest of the network creating other congestion points for example.

SUMMARY OF THE INVENTION

0004It is an object of the present invention to provide an improved method of operating a network to mitigate the effects of congestion points within the network for high priority traffic.

0005It is a further object of the present invention to provide a method and apparatus for providing improved traffic routing within the networks.

0006In a first aspect the present invention comprises a method of operating a connectionless network to provide a priority routing service for a network user having a plurality of customers communicating with said user via said network, the network comprising a plurality of network elements and links therebetween, the method comprising:

0007maintaining an express route comprising one or more said links between two end elements;

0008at least one said end element arranged to identify data packets originating from said user and destined for a said customer or originating from a said customer and destined for said user and diverting said packets along said express route.

0009Preferably said route is bi-directional, both said end elements being arranged to identify and divert said packets.

0010Preferably said maintaining step comprises reserving bandwidth on said links forming said route.

0011Preferably said route has one end element adjacent or forming the network entry point of said user.

0012Preferably said diverting step comprises modifying a forwarding table within one said end element such that data packets having a destination address corresponding to said user are diverted along said route.

0013Preferably said diverting step comprises filtering data packets within the other said end element such that data packets having a source address corresponding to said user are diverted along said route.

0014In a second aspect the present invention provides a network element for use in a connectionless network comprising a plurality of network elements and links therebetween, the network element comprising:

0015means for routing data packets onto another element dependent on a destination address of said packets;

0016filter means for identifying and diverting data packets having a source address corresponding to a predetermined user, said identified packets being diverted to an element not specified by said routing means and forming part of an express route for said user.

0017In a third aspect the present invention comprises a plurality of network elements and links therebetween;

0018means for maintaining an express route comprising one or more said links between two end elements;

0019wherein at least one said end element is arranged to identify data packets originating from a network user and destined for one of a plurality of customers of said user or originating from a said customer and destined for said user and diverting packets long said express route.

BRIEF DESCRIPTION OF THE DRAWINGS

0020In order that a greater understanding of the invention can be obtained, embodiments of the invention will now be described with reference to accompanying drawings, by way of example only and without intending to be limiting, in which:

0021<figref idref="DRAWINGS">FIG. 1</figref> shows a schematic diagram of a network topology; and

0022<figref idref="DRAWINGS">FIG. 2</figref> shows a schematic diagram of a network element according to the invention; and

0023<figref idref="DRAWINGS">FIG. 3</figref> shows a flow diagram of a method according to the invention.

DETAILED DESCRIPTION

0024Referring to <figref idref="DRAWINGS">FIG. 1</figref>, a connectionless network for example an IP network is shown and comprises a number of network elements <b>3</b> such as routers or switches for example, which are connected to other network elements <b>3</b> by links or pathways <b>4</b> according to an overall network topology. The manner in which the elements are connected to each other will depend on for example their geographical location as well as available physical transmission lines or links between these locations.

0025At the periphery of the network <b>2</b>, access points or gateways <b>5</b> connect the network <b>2</b> to customers or other networks such as access networks <b>8</b>. Customers B are also connected to the network <b>2</b> by network elements <b>3</b>. User traffic between one access point land another on the network <b>2</b> is routed via the network elements <b>3</b> in a series of hops. Each network element contains a forwarding table which directs incoming traffic out to another network element directly connected to the current network element, the ongoing network element <b>3</b> being selected by the forwarding table dependant on the traffics final destination, as is well known in the art. The forwarding tables tend to be reasonably static with a connectionless network in the absence of faults and are set up according to the network topology (and possibly expected traffic flows) so that for example traffic from A to B will initially enter the network <b>2</b> at network element <b>3</b><i>a</i>. The forwarding table of network element <b>3</b><i>a </i>determines the traffics final address as B and routes the traffic onto network element <b>3</b><i>x</i>. Similarly the forwarding table of element <b>3</b><i>x </i>maps traffic destined for B onto network element <b>3</b><i>y</i>, and from there on to element <b>3</b><i>b </i>where it then leaves the network to complete its journey to B. A typical route from A to B through network <b>2</b> is then shown as <b>6</b>. Because of other traffic flows through the network <b>2</b>, such as that between elements <b>3</b><i>w </i>and <b>3</b><i>z </i>for example, congestion points or bottlenecks may rise within the network for example at element <b>3</b><i>y. </i>

0026The invention provides a method of implementing alternative routing for priority customers whereby traffic for these customers is re-routed to avoid network bottlenecks (such as <b>3</b><i>y</i>). These priority customers may be high revenue generating customers for the network operator for example, or they may pay a premium for this alternative or express routing service.

0027The invention also provides a method of implementing alternative routing as part of the set up for a “calling event”. Due to a current affairs phenomenon for example, there may be an expectation of heavy traffic in the certain part of the network and this traffic flow can be ameliorated by implementing various alternative routes to more evenly distribute traffic flow through the network.

0028In the present example, considering B as a priority customer or focus of the “calling event” such as an E commerce site or website for example, traffic routed to and from B across the network <b>2</b> is diverted around bottlenecks or high congestion network elements <b>3</b> within the network <b>2</b>. For example traffic between A and B upon reaching element <b>3</b><i>x </i>is diverted to element <b>3</b><i>u </i>instead of element <b>3</b><i>y </i>where the rest of the traffic from element <b>3</b><i>x </i>destined for B is sent. Similarly this “priority” traffic for B arriving at element <b>3</b><i>u </i>is directed from there to element <b>3</b><i>b </i>forming an express route <b>7</b> between elements <b>3</b><i>x </i>and <b>3</b><i>b</i>. This express route <b>7</b> avoids the congested element <b>3</b><i>y</i>, and thereby provides a faster route for traffic between A and B. In a similar fashion, traffic from B to A entering the network at element <b>3</b><i>b </i>is directed to element <b>3</b><i>u </i>and then on to element <b>3</b><i>x </i>where it joins the rest of the traffic from B destined for A.

0029The express route <b>7</b> comprises reserved or dedicated bandwidths on specific paths or connections between network elements to bypass known congestion points on the network. The express routes may be uni or bidirectional depending on the service required. For example where the express routing service is provided for a web page where the traffic is highly asymmetrical, it is likely that a unidirectional path will be sufficient. The amount of bandwidth reserved for each path and direction will depend on what the express routing service is provided for and what the customer is prepared to pay for. The example express route <b>7</b> shown may be used for other high priority traffic for example that between network element <b>3</b><i>t </i>and B.

0030There are a number of mechanisms for reserving bandwidth for express routes. For example it may be known that while the capacity of a particular link <b>4</b> is 50 Mb/s the typical loading on this link is only 10 Mb/s. In these circumstances it would be possible for example to reserve four priority routes of 10 Mb/s for four priority customers. Other method of reserving bandwidth on links within a network are known such as “TCP trunking” for example.

0031The express route <b>7</b> is implemented by network elements <b>3</b><i>b </i><b>3</b><i>u </i>and <b>3</b><i>x </i>as follows. For priority traffic flowing front A to B, the forwarding table of element <b>3</b><i>x </i>is modified to include a specific IP address for customer B which maps traffic corresponding to this address to network element <b>3</b><i>u </i>instead of element <b>3</b><i>y</i>. Because network elements implement a “find longest match first” algorithm, traffic having a destination address corresponding to B will be routed directly to element <b>3</b><i>u </i>whereas other traffic which is being routed to element <b>3</b><i>b </i>but not to B will be routed from <b>3</b><i>x </i>to element <b>3</b><i>y. </i>

0032Because routers typically just look at the destination address of a data packet, implementation of the express route <b>7</b> in the forward direction towards the customers site B is relatively straight forward. The reverse direction however is not so straight forward where packets from B are destined for A for example.

0033<figref idref="DRAWINGS">FIG. 2</figref> shows a schematic diagram of network element <b>3</b><i>b </i>according to the invention which comprises a forwarding table <b>20</b> and a filter <b>21</b>. Incoming data packets from customer B are routed onto network elements connected to element <b>3</b><i>b </i>such as <b>3</b><i>s</i>, <b>3</b><i>u</i>, and <b>3</b><i>y</i>, according to its forwarding table <b>20</b>. Each traffic packet comprises a destination address <b>30</b> which is mapped by the forwarding table <b>20</b> to an output connection on the network element corresponding to one of the network elements directly connected to it as is known in the art. For example where the packet address, shown in IP format, corresponds to a destination A, this would normally be routed to network element <b>3</b><i>y </i>by the forwarding table <b>20</b>.

0034To implement the express route <b>7</b> the, network element <b>3</b><i>b </i>includes a filter <b>21</b> which identifies source addresses <b>29</b> associated with a high priority customer B and re-routes them by the express routes <b>7</b> to element <b>3</b><i>u</i>. The filter function <b>21</b> may be implemented in hardware or software depending on the speed required. The filter <b>21</b> re-routes packets with a source address <b>29</b> corresponding to the priority customer B within the network element <b>3</b><i>b </i>to a special queue for express lane traffic. As is known with network elements such as routers and switches, the various queues within these elements are allocated percentage opportunities for output from the element <b>3</b><i>b </i>and this output;opportunity percentage can be tuned according to the needs of the network and the priority express route <b>7</b>.

0035In an alternative embodiment, the filter <b>21</b> may be placed between the forwarding table and the output to element <b>3</b><i>y</i>, where traffic destined for B is then specifically rerouted to element <b>3</b><i>u. </i>

0036As a further alternative, the express route <b>7</b> may be implemented using MPLS (Multi Protocol Label Switching) pathways set up for traffic to and from customer B. In the example shown in <figref idref="DRAWINGS">FIG. 1</figref>, MPLS labels will be used for the path <b>7</b> between elements <b>3</b><i>x </i>and <b>3</b><i>b</i>. The express route <b>7</b> differs from normal MPLS routing in that the MPLS pathway is set up for particular priority customers and not between specified nodes or elements within the network. At the start of each MPLS path, methods similar to those described previously are used to select the correct path which is to be used and assign the label to the packet which guides it along the path.

0037The express route technique allows a carrier to offer an enhanced service to particular customers which expect to receive and/or transmit data traffic from any arbitrary source/destination, for example a web server or e-commerce site. Without the express route, traffic to and from the customers site will pass through any or all of the bottlenecks or congestion points of the carriers network and may be subject to unexpected delay or loss. In particular, as the traffic converges or diverges from the customers site, the concentration of the traffic may interact with other traffic to generate a specific bottleneck which is not under the control of the customer. With express routes <b>7</b> implemented in the network the traffic can be picked up and routed on dedicated paths with reserved resources to points in the carriers network where it is dispersed sufficiently to avoid the sort of congestion described above. The amount of bandwidth reserved can be negotiated by the customer as appropriate for the traffic expected, and the performance of the customers applications become more controllable.

0038Preferably therefore, one end of the express route is implemented near the customers network access point.

0039The Express Route technique differs from a Virtual Private Network or Extranet implementation in that the Express Route is concerned with providing a service for a predetermined user having a plurality of customers on the network. The Express Route provides a reserved bandwidth for priority traffic (data packets) destined for the user from his customers and/or originating from the user and destined for his customers. This allows the user to provide a faster service for his customers and is a service which the network operator may charge for.

0040The Data Express Route solves a difficult problem than either a VPN (Virtual Private Network) or an Extranet. In both of these cases the source and destination for all possible traffic through the network are known in advance and implemented as “points of presence” where the VPN or Extranet traffic is injected into or extracted from the network.

0041The Express Route provides a solution for predetermined users who wish to send and receive traffic from any other customer attached to the network, and hence can only know in general terms where the traffic will occur in the network. The Data Express Route. provides collectors or concentrators (for example filters or forwarding table modifications) at strategic points in the network which are not specific to any particular customer to divert the selected priority traffic into the Express Route.

0042<figref idref="DRAWINGS">FIG. 3</figref> shows a method of determining and using express routes <b>7</b> within a connectionless network <b>2</b>. It is first necessary to identify carrier nodes or elements where customer traffic is concentrated. This is typically done using network manager and analysis packages such as the trail manager package described in applicant's co-pending application Ser. No. 09/219,374. Using these sorts of packages, it is possible to determine typical traffic levels on various links within the network and from this to determine alternative links for priority customer express routes <b>7</b>. Network elements at either end of the selected express route <b>7</b> are modified as described above, either by modifying the forwarding table of the network element at the distal end of the route <b>7</b> or by incorporating a filter <b>21</b> within the network element adjacent the priority customers site. Intermediate elements (eg <b>3</b><i>u </i>in <figref idref="DRAWINGS">FIG. 1</figref>) may also require modification either by modifying the forwarding table or introducing a filter <b>21</b> depending on how they would normally route traffic including the express route packets incident on them. For example, if traffic into element <b>3</b><i>u </i>destined for B would normally be routed to <b>3</b><i>b </i>by the element in an unmodified state, then there is no need to modify it. With an MPLS path, the standard MPLS required modifications will be implemented on element <b>3</b><i>u </i>as is known in the art.

0043At the customers site element or access point the traffic is extracted from the express route <b>7</b> and directed to the customer. The traffic outgoing from the customer is filtered onto the relevant express route <b>7</b> to the appropriate network element for the traffics intended destination. At this point the traffic is extracted from the express route <b>7</b> and redirected to the intended destination in the normal way.

0044The foregoing describes the present invention including preferred embodiments thereof. Alterations and modifications as would be obvious to those skilled in the art are intended to be incorporated within the scope hereof.