Network routing table

Details Network routing table Network routing table

1999-12-09

2003-12-16

Chin, Wellington (Department: 2664)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S395320

Reexamination Certificate

active

06665297

ABSTRACT:

The present invention relates generally to routing packets in a network such as the Internet, and particularly to a network routing table that ensures that a destination address of a packet is mapped to a route in a fixed amount of time.
BACKGROUND OF THE INVENTION
In packet networks, information is transferred through the network from a source computer to a destination computer using packets called datagrams. The datagrams include data from the source and a destination address. The datagrams are routed through the network based on the destination address. The source and destination computers are called hosts. The network is an interconnection of hosts and routers. Typically routers have many network interfaces or ports connecting to other routers and hosts. The routers have input ports for receiving incoming datagrams and output ports for transmitting outgoing datagrams. The routers route the datagrams to a host or to another router based on the destination address. The routers store information about routes in a routing table.
In the Internet protocol (IP), a route is either an indirect route or a direct route. When a route is an indirect route, the next destination is another router. A routing table entry indicates the next router's IP address and related information, such as the network interface connecting to the next router. When a route is a direct route, the next destination is the destination host. In this case, the routing table entry indicates the network interface to which the destination host is connected.
A hop is a direct interconnection between two routers, two hosts, or a router and a host. An indirect route has more than one hop to a host, while a direct route has one hop to the host. A next hop is the router or host at the distant end of the hop. A next hop's IP address is the IP address of the router or host at the distant end of the hop.
The information in a route entry in a routing table includes at least the following: a destination IP address, a prefix length, a next hop's IP address and address port information. The IP address has thirty-two bits. The prefix length specifies the number of leading bits of the IP address defining a network portion of the address. The remaining bits define a host portion of the address. The network portion of the address is often referred to as the IP network address. The entire IP address is usually referred to as the IP host address. For example, using standard Internet dotted decimal notation, 172.16.10.20/24 would indicate an IP prefix length of 24 bits, a network address of 172.16.10.0, and an IP host address of 172.16.10.20.
IP routing is based on either the IP network address or the IP host address. Routes specified with IP network addresses are called network routes. Routes specified with IP host addresses are called host routes. IP routers handle both network and host routes.
When a router receives a datagram with a destination address for a host that is not connected to that router, the router routes the datagram to another router. Each router has a routing table defining routes or ports to use to route the datagram. The routing table stores routing table entries. Each routing table entry includes at least a destination IP address, the prefix length of that destination IP address, the next hop's IP address for that destination, and the network interface (port) to be used for sending a datagram to the next router or host. When a routing table entry is a direct route to a host, the next hop's IP address is typically stored as 0.0.0.0. When the route is a host route, the prefix length is set equal to thirty-two.
When searching for a route in the routing table, the router uses the destination IP address of each datagram as the search key. Although all datagrams include a destination IP host address, no datagrams include the prefix length information. Therefore, routers need to determine which portion of the IP host address includes the IP network address for network routes.
To determine a route, one prior art routing table architecture uses a hash table. In hash-based routing tables, two tables and one special route entry are typically used. The first table, rt_host, is used for host routes and stores IP host addresses and output ports. The second table, rt_net, is used for network routes and stores IP network addresses and their route information. The special route entry specifies a default route. When a datagram is being routed, the router searches the first table, rt_host, for host routes, if any. The router performs the search by comparing the destination address to the IP host addresses in the routing table. When no IP host address in the first table matches the destination address, the first table does not specify the host route and the search fails. When the search of the first table fails to find a host route, the router searches the second table, rt_net, to determine a network route, if any, using the destination address and the IP network addresses stored in the second table. When no IP network address in the second table matches the destination address, the second table does not specify the network route and the search fails. When the search of the second table fails to find a network route, the router uses the default route, if specified.
The first and second tables, rt_host and rt_net, respectively, are usually implemented as hash tables. For the first table, rt_host, routers use the entire destination IP host address in the incoming datagram as a hash key to determine a starting pointer to a linked list in the first table. A linear search is performed through the linked list to determine whether the destination IP host address matches any entry in the linked list. If so, this matching entry, which has the host route, is returned.
For the second table, rt_net, routers use a set of leading bits of the destination IP host address in the incoming datagram as a hash key to determine a starting pointer to a linked list in the second table. The set of leading bits of the destination IP host address is the destination IP network address. Routers determine the prefix length from the traditional IP address class information. The router uses the prefix length to determine the number of leading bits of the destination IP network address to apply as the hash table key. A linear search is then performed through the linked list to determine whether the destination IP network address matches any entry in the linked list. If so, this matching entry, which contains the network route, is returned.
In the second table, rt_net, the linked list is pre-sorted by IP prefix length in descending order. When the second table, rt_net, is searched, the first match will select the longest match of the network portion of the destination address.
The hash-based routing methods are slow because a linear search is performed through the linked list in the hash table. The amount of time to search for a route is a function of the number of entries in the linked list. Therefore, route lookup cannot be done in a predetermined, fixed amount of time. In other words, searches have no fixed upper bound on the amount of time to perform the search.
In a second prior art routing table architecture, a radix or Patricia tree routing table is used. In radix tree routing, the radix tree routing table traverses a binary tree of network and host IP addresses to find a match to the destination address. A radix tree search can minimize the number of bits to be tested to distinguish among a set of bit strings. However, a radix tree search cannot search for a route in deterministic time. Since radix tree routing allows back tracking, radix tree searching can also be slow.
A third routing table architecture is shown in U.S. Pat. No. 5,386,413. In the '413 patent, all possible values to be compared with the incoming address are split into multiple content addressable memory (CAM) banks. Each CAM bank uses a single mask in conjunction with the incoming address to select at most one associated output value in the bank. For IP rout

Affiliated with

Also associated with

Rating

Network routing table does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Network routing table, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Network routing table will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3116897