Method of managing and using multiple virtual private...

Details Method of managing and using multiple virtual private... Method of managing and using multiple virtual private...

1999-12-15

2003-07-15

El-Hady, Nabil (Department: 2154)

Electrical computers and digital processing systems: multicomput

Computer-to-computer data routing

C709S242000, C709S245000, C709S249000, C711S206000, C711S207000

Reexamination Certificate

active

06594704

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to the field of telecommunications, and more particularly to an improved system and method of searching.
BACKGROUND OF THE INVENTION
As is known, the Internet is a packet network, where each data packet is passed from a network device referred to as a router to the next in the chain, until it reaches its destination. Typically, as a packet moves through the network, each router performs packet forwarding decisions independent of other routers and other packets. Internet Protocol (IP) is the networking language of the Internet, and routers are the principal engines of IP. IP routers have to perform a per-packet lookup in a routing table to determine where IP packets are to be forwarded.
Within a router, a route entry essentially consists of two parts—an address prefix to next hop mapping (at the IP layer) and the knowledge of what link is available to that next hop. These two pieces of information are sufficient to route packets. A packet enters the router with a destination address in the IP header. The router performs a lookup of its routing table with this destination address as the key. The routing table itself is essentially an address prefix to next hop mapping. Hence, given a destination address, the router selects an address prefix entry in the routing table to determine the next hop router that this packet must be handed to. The routing table entry also indicates what link to send the packet out on (to this next hop).
Typically the router receives millions of packets per second and for efficient and fast forwarding, the need for a high speed destination prefix lookup is essential. The destination address in a given packet may match multiple prefixes in the routing table and so the router is required to find the most specific match from a large number of patterns.
Several schemes for better router data throughput and faster packet forwarding have been proposed in recent years in order to perform Internet Protocol (IP) lookups in an optimized manner. Most applications require the retrieved information be associated with the best matching prefix (BMP), if any, of the input string. For example, if the string “MART” is the input string to a database, and the database holds information associated with the strings “M”, “MA”, and “MAL”, the best matching prefix to “MART” is the string “MA”, and the information associated with “MA” should be returned. Note that “M” is also a prefix of “MART”, but “MA” is a better (i.e. longer) prefix than “M”. BMP searching is typically performed by a database having a hierarchical, tree-like structure. This type of database is often called a trie. A trie database allows both exact matching (i.e. searching for a string that is exactly equal to the input string) as well as best prefix.
IP lookups that use BMP can be performed in either software or hardware. An example of a software approach, as mentioned above, is to involve a tree-based method using Patricia, i.e., radix, trees, or binary trees. An example of a hardware approach is to involve the use of Content Addressable Memories (CAMs).
A typical router has two main forwarding functions, i.e., address lookup (to lookup a destination address) and message switching (sending the packet to the correct output link). The problem of accomplishing address lookups at gigabit speeds is ever increasing. With the emergence of high-speed links, like OC-48 and higher (An OC-48 link can deliver packets at up to 2.5 million packets per second assuming an average of 1,000 bit per packet) to the router, it is essential that packet forwarding keep up with this rate. Otherwise packet forwarding (route lookup, etc.) could act as a bottleneck essentially degrading the performance of the router.
Complicating matters is greater usage of virtual private networks. A virtual private network (VPN) is a private data network that makes use of the public telecommunication infrastructure, maintaining privacy through the use of a tunneling protocol and security procedures. A virtual private network can be contrasted with a system of owned or leased lines that can only be used by one company. The idea of the VPN is to give the company the same capabilities at much lower cost by using the shared public infrastructure rather than a private one. Phone companies have provided secure shared resources for voice messages. A virtual private network makes it possible to have the same secure sharing of public resources for data. Companies today are looking at using private virtual networks for both extranets and wide-area intranets.
An extranet is a private network that uses the Internet protocols and the public telecommunication system to securely share part of a business's information or operations with suppliers, vendors, partners, customers, or other businesses. An extranet can be viewed as part of a company's intranet that is extended to users outside the company.
An intranet is a private network that is contained within an enterprise. It may consist of many interlinked local area networks and also use leased lines in the wide area network. Typically, an intranet includes connections through one or more gateway computers to the outside Internet. The main purpose of an intranet is to share company information and computing resources among employees. An intranet can also be used to facilitate working in groups and for teleconferences. An intranet may use TCP/IP, HTTP, and other Internet protocols and in general look like a private version of the Internet.
As is well known, implementation of multiple VPNs in a single router has typically complicated address lookup since each VPN must have its own routing table, necessitating a large amount of table space within a single router to implement these individual routing tables. Also, dividing the available table space into dedicated areas for each VPN creates fragmentation and therefore inefficient use of the available space.
What is needed is a new and improved system and method of managing multiple VPN routing tables within a single shared space to maintain efficiency and speed of lookups, and correspondingly, efficiency and speed of packet forwarding.
SUMMARY OF THE INVENTION
In accordance with the principles of the present invention a method of maintaining multiple routing tables within a global table of a network router is provided including the steps of providing the router with a route table generator to maintain the global table, and a forwarding engine to perform table lookups, the performing of table lookups in one of the multiple routing tables of the global table using a key, the key representing an index into the one of said multiple routing tables within said global table, the key created by combining a virtual private network identification (VPN ID) and a packet destination address, and maintaining a plurality of table entries in the global table by using the key as a pointer to one of said table entries.


REFERENCES:
patent: 5386413 (1995-01-01), McAuley et al.
patent: 5606650 (1997-02-01), Kelley et al.
patent: 5809563 (1998-09-01), Yamada et al.
patent: 6160811 (2000-12-01), Partridge et al.
patent: 6205488 (2001-03-01), Casey et al.
patent: 6226751 (2001-05-01), Arrow et al.
patent: 6339595 (2002-01-01), Rekhter et al.
patent: 6426955 (2002-07-01), Gossett Dalton, Jr. et al.
patent: 6438612 (2002-08-01), Ylonen et al.
patent: 6526056 (2003-02-01), Rekhter et al.
patent: 2003/0018876 (2003-01-01), Zahir et al.

Affiliated with

Also associated with

Rating

Method of managing and using multiple virtual private... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method of managing and using multiple virtual private..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of managing and using multiple virtual private... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3007583