Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-02-26
2001-02-20
Rao, Scema S. (Department: 2738)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S400000, C370S408000, C709S238000, C709S241000
Reexamination Certificate
active
06192051
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention is related to the field of data networks, and more particularly to the routing of data packets from a source node to a destination node within a network.
One primary function of data networks is the routing of data packets or frames from a source network node to one or more destination network nodes. When a network device receives a packet or frame, the device examines the packet or frame in order to determine how the packet or frame is to be forwarded. Similar forwarding decisions are made as necessary at multiple intermediate network devices until the packet or frame is received at a desired destination node. This type of operation is in contrast to networks employing switching techniques, in which routes are pre-established as “circuits” and each network device simply forwards each received packet on its associated circuit. One example of a routed network is the Internet, which employs a protocol known as the Internet Protocol (IP) for routing data packets through the Internet.
There is a growing demand for Internet and other data network services. As a result, there is an increasing volume of routed data traffic such as IP traffic being carried on high-bandwidth data channels, such as the well-known T1 and T3 signals used to carry data and digitized voice in the public telephone system. Along with this increase in routed traffic is an increased demand for high-throughput routers that can make forwarding decisions at very high rates.
To accomplish the task of routing data packets through a network from a source node to a destination node, data networks commonly employ a distributed routing procedure. Network routers maintain routing tables to carry out the routing function. When a packet arrives at a router, an address contained within the packet (for example the destination address) is used to retrieve an entry from the routing table that indicates the next hop, or next node, along a desired route to the destination node. The router then forwards the packet to the indicated next hop node. The process is repeated at successive router nodes until the packet arrives at the desired destination node.
The routing tables in the routers are maintained according to any of a variety of distributed routing protocols. For example, one well-known routing protocol is known as OSPF, which is an acronym for “Open Shortest Path First”. The routers collect information about the activation and deactivation of network links among neighboring nodes, and the information is communicated among the routers according to the routing protocol. Routes are created, updated, and deleted as needed according to network conditions. All of the pertinent routing-related information is contained collectively within the routing tables maintained at the routers.
A routing table entry includes a 2-part mapping between an address such as a destination address and an associated next hop address. It is common for the destination address portion to include a subnet mask value indicating that some of the address bits are to be matched precisely and others need not be. An example of an entry in an Internet Protocol (IP) routing table is the following:
128.4.0.0/16 100.0.0.0
This entry uses the known convention of representing a 32-bit IP address as a string of four bytes (most significant to least significant) separated by decimal points, where the value of each byte is given as a decimal equivalent. This entry indicates that any packet having a destination address whose 16 most significant bits are equal to 128.4 (1000000 0000100 binary), should be routed to the network node having IP address 100.0.0.0 (01100100 00000000 00000000 00000000 binary). An example of a matching destination address is 128.4.10.9; an example of a non-matching address is 128.120.0.0.
The example above illustrates the concept of aggregation of IP addresses for routing purposes. All IP addresses whose upper 16 bits are equal to 128.4 are routed to the same next hop node. Since IP addresses are 32-bit values, there are 2
(32−16)
=2
16
=64K such addresses. These addresses are said to be aggregated in the routing table. It will be appreciated that shorter subnet masks correspond to greater aggregation, while longer subnet masks correspond to less aggregation. In addition, this format for a routing entry can also be used for route summarization, a technique similar to aggregation that is used by routing protocols.
The mapping from the set of all possible destination addresses to the set of all possible next hops can be represented as a binary tree, in which each bit of the destination address dictates which branch is taken at a corresponding level in the search for the next hop. For an n-bit address, a tree of height n is required. A fully populated tree has 2
n
distinct leaves at the end of 2
n
distinct search paths, where each leaf corresponds to a next hop value. However, a tree representing a set of routing entries typically contains far fewer leaves. The number of leaves required is influenced by the number of entries in the routing table, and also the degree to which network addresses are aggregated. If the network address space is divided into a relatively large number of sub-spaces each of which is assigned a different route, more leaves are needed than when the network address space is divided into a smaller number of sub-spaces having distinct routes. Most networks exhibit substantial address aggregation, so that even in large networks the mapping tree used for routing at a given node tends to be “sparse”, i.e. not very fully populated. For example, the routing entry given above corresponds to a single leaf at location
16
of the tree, and it covers the range of 64K addresses from 128.4.0.0 through 128.4.255.255.
The simplest way conceptually to look up a next hop address is to use a conventional random-access memory having a binary address input and a data storage location associated with each unique address value. A next hop value is stored at the storage location corresponding to each address. The next hop is looked up in the memory by simply retrieving the value stored at the memory location indicated by the address included in a received packet. When a group of addresses are aggregated, such as in the above example, the next hop value used by the aggregation would be replicated at each aggregated address in the memory. Thus in the foregoing example the entry 100.0.0.0 would appear at locations 128.4.0.0 through 128.4.255.255 of such a memory.
While conceptually simple, such an approach is not practically feasible for typical network address spaces. The amount of memory required based on typical network address lengths is prohibitively large. For example, 4 billion memory locations are required to fully decode 32-bit IP addresses. Also, this approach is inefficient when the tree is even modestly sparse. For these reasons, network routers have generally employed alternative means of storing and retrieving the tree elements.
Many contemporary routers employ what is referred to as a Patricia tree representation of the mapping from destination addresses to next hops. During a search, a Patricia tree is traversed in binary fashion in the direction from most significant to least significant address bits. The Patricia tree structure achieves significantly greater storage efficiency than the simplistic approach described above. However, worst-case searches can potentially require 32 memory references. Thus the performance of a router using a Patricia tree is undesirably sensitive to network topology and address assignments.
The logical partitioning and layout of functional components within the router also affect router performance. A common configuration for a contemporary router is a collection of line cards interconnected by a switching fabric. Each line card has one or more ports each attached to a corresponding physical network medium. When a packet arrives at a line card port, a forwarding engine on the line card determines which port the packet should be forwarde
Heyda Russell L.
Lipman Michael E.
Rao Scema S.
Redstone Communications, Inc.
Tsegaye Saba
Weingarten, Schurgin Gagnebin & Hayes LLP
LandOfFree
Network router search engine using compressed tree... 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 router search engine using compressed tree..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Network router search engine using compressed tree... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2571701