Longest prefix match

Last updated

Longest prefix match (also called Maximum prefix length match) refers to an algorithm used by routers in Internet Protocol (IP) networking to select an entry from a routing table. [1]

Because each entry in a forwarding table may specify a sub-network, one destination address may match more than one forwarding table entry. The most specific of the matching table entries the one with the longest subnet mask is called the longest prefix match. It is called this because it is also the entry where the largest number of leading address bits of the destination address match those in the table entry. [2]

For example, consider this IPv4 forwarding table (CIDR notation is used):

192.168.20.16/28 192.168.0.0/16

When the address 192.168.20.19 needs to be looked up, both entries in the forwarding table "match". That is, both entries contain the looked up address. In this case, the longest prefix of the candidate routes is 192.168.20.16/28, since its subnet mask (/28) is longer than the other entry's mask (/16), making the route more specific.

Forwarding tables often contain a default route, which has the shortest possible prefix match, to fall back on in case matches with all other entries fail.

See also

Related Research Articles

An Internet Protocol address is a numerical label such as 192.0.2.1 that is connected to a computer network that uses the Internet Protocol for communication. An IP address serves two main functions: network interface identification, and location addressing.

The Internet Control Message Protocol (ICMP) is a supporting protocol in the Internet protocol suite. It is used by network devices, including routers, to send error messages and operational information indicating success or failure when communicating with another IP address, for example, an error is indicated when a requested service is not available or that a host or router could not be reached. ICMP differs from transport protocols such as TCP and UDP in that it is not typically used to exchange data between systems, nor is it regularly employed by end-user network applications.

<span class="mw-page-title-main">Internet Protocol version 4</span> Fourth version of the Internet Protocol

Internet Protocol version 4 (IPv4) is the fourth version of the Internet Protocol (IP). It is one of the core protocols of standards-based internetworking methods in the Internet and other packet-switched networks. IPv4 was the first version deployed for production on SATNET in 1982 and on the ARPANET in January 1983. It is still used to route most Internet traffic today, even with the ongoing deployment of Internet Protocol version 6 (IPv6), its successor.

<span class="mw-page-title-main">Router (computing)</span> Device that forwards data packets between computer networks

A router is a networking device that forwards data packets between computer networks. Routers perform the traffic directing functions between networks and on the global Internet. Data sent through a network, such as a web page or email, is in the form of data packets. A packet is typically forwarded from one router to another router through the networks that constitute an internetwork until it reaches its destination node.

Classless Inter-Domain Routing is a method for allocating IP addresses and for IP routing. The Internet Engineering Task Force introduced CIDR in 1993 to replace the previous classful network addressing architecture on the Internet. Its goal was to slow the growth of routing tables on routers across the Internet, and to help slow the rapid exhaustion of IPv4 addresses.

Open Shortest Path First (OSPF) is a routing protocol for Internet Protocol (IP) networks. It uses a link state routing (LSR) algorithm and falls into the group of interior gateway protocols (IGPs), operating within a single autonomous system (AS).

<span class="mw-page-title-main">Routing table</span> Data table stored in a router that lists the routes to network destinations

In computer networking, a routing table, or routing information base (RIB), is a data table stored in a router or a network host that lists the routes to particular network destinations, and in some cases, metrics (distances) associated with those routes. The routing table contains information about the topology of the network immediately around it.

<span class="mw-page-title-main">Network address translation</span> Protocol facilitating connection of one IP address space to another

Network address translation (NAT) is a method of mapping an IP address space into another by modifying network address information in the IP header of packets while they are in transit across a traffic routing device. The technique was originally used to bypass the need to assign a new address to every host when a network was moved, or when the upstream Internet service provider was replaced, but could not route the network's address space. It has become a popular and essential tool in conserving global address space in the face of IPv4 address exhaustion. One Internet-routable IP address of a NAT gateway can be used for an entire private network.

<span class="mw-page-title-main">Subnet</span> Logical subdivision of an IP network

A subnetwork or subnet is a logical subdivision of an IP network. The practice of dividing a network into two or more networks is called subnetting.

<span class="mw-page-title-main">Content-addressable memory</span> Special type of computer memory used in certain very-high-speed searching applications

Content-addressable memory (CAM) is a special type of computer memory used in certain very-high-speed searching applications. It is also known as associative memory or associative storage and compares input search data against a table of stored data, and returns the address of matching data.

6to4 is an Internet transition mechanism for migrating from Internet Protocol version 4 (IPv4) to version 6 (IPv6) and a system that allows IPv6 packets to be transmitted over an IPv4 network without the need to configure explicit tunnels. Special relay servers are also in place that allow 6to4 networks to communicate with native IPv6 networks.

<span class="mw-page-title-main">Supernetwork</span> Aggregation of Internet Protocol networks

A supernetwork, or supernet, is an Internet Protocol (IP) network that is formed by aggregation of multiple networks into a larger network. The new routing prefix for the aggregate network represents the constituent networks in a single routing table entry. The process of forming a supernet is called supernetting, prefix aggregation, route aggregation, or route summarization.

A default gateway is the node in a computer network using the Internet protocol suite that serves as the forwarding host (router) to other networks when no other route specification matches the destination IP address of a packet.

In computer networking, the default route is a configuration of the Internet Protocol (IP) that establishes a forwarding rule for packets when no specific address of a next-hop host is available from the routing table or other routing mechanisms.

Cisco Express Forwarding (CEF) is an advanced layer 3 switching technology used mainly in large core networks or the Internet to enhance the overall network performance. Although CEF is a Cisco proprietary protocol other vendors of multi-layer switches or high-capacity routers offer a similar functionality where layer-3 switching or routing is done in hardware instead of by software and the (central) CPU.

In network routing, the control plane is the part of the router architecture that is concerned with establishing the network topology, or the information in a routing table that defines what to do with incoming packets. Control plane functions, such as participating in routing protocols, run in the architectural control element. In most cases, the routing table contains a list of destination addresses and the outgoing interface(s) associated with each. Control plane logic also can identify certain packets to be discarded, as well as preferential treatment of certain packets for which a high quality of service is defined by such mechanisms as differentiated services.

<span class="mw-page-title-main">Forwarding plane</span>

In routing, the forwarding plane, sometimes called the data plane or user plane, defines the part of the router architecture that decides what to do with packets arriving on an inbound interface. Most commonly, it refers to a table in which the router looks up the destination address of the incoming packet and retrieves the information necessary to determine the path from the receiving element, through the internal forwarding fabric of the router, and to the proper outgoing interface(s).

<span class="mw-page-title-main">IPv6 address</span> Label to identify a network interface of a computer or other network node

An Internet Protocol Version 6 address is a numeric label that is used to identify and locate a network interface of a computer or a network node participating in a computer network using IPv6. IP addresses are included in the packet header to indicate the source and the destination of each packet. The IP address of the destination is used to make decisions about routing IP packets to other networks.

route (command) Computer operating system command

In computing, route is a command used to view and manipulate the IP routing table in Unix-like and Microsoft Windows operating systems and also in IBM OS/2 and ReactOS. Manual manipulation of the routing table is characteristic of static routing.

IP routing is the application of routing methodologies to IP networks. This involves not only protocols and technologies but includes the policies of the worldwide organization and configuration of Internet infrastructure. In each IP network node, IP routing involves the determination of a suitable path for a network packet from a source to its destination in an IP network. The process uses static configuration rules or dynamically obtained from routing protocols to select specific packet forwarding methods to direct traffic to the next available intermediate network node one hop closer to the desired final destination, a total path potentially spanning multiple computer networks.

References

  1. Comer, Douglas (2008). Computer Networks and Internets (5th ed.). Pearson/Prentice Hall. p. 368. ISBN   978-0-13-606698-9.
  2. Wright, Robert (1998). IP Routing Primer. Cisco Press. p. 352. ISBN   978-1578701087.