Compressing Two-Dimensional Routing Tables

We consider an algorithmic problem that arises in the context of routing tables used by Internet routers. The Internet addressing scheme is hierarchical, where a group of hosts are identified by a prefix that is common to all the hosts in that group. Each host machine has a unique 32-bit address. Thus, all traffic between a source group s and a destination group d can be routed along a particular route c by maintaining a routing entry (s, d, c) at all intermediate routers, where s and d are binary bit strings. Many different routing tables can achieve the same routing behavior. In this paper we show how to compute the most compact routing table. In particular, we consider the following optimization problem: given a routing table D with N entries of the form (s, d, c) , determine a conflict-free routing table with fewest entries that has the same routing behavior as D. If the source and destination fields have up to w bits, and there are at most K different route values, then our algorithm runs in worst-case time O( NK w2) .     

Persistent detection and recovery of state inconsistencies

Soft-state is a well established approach to designing robust network protocols and applications. However it is unclear how to apply soft-state approach to protocols that must maintain a large amount of state information in a scalable way. For example the Border Gateway Protocol (BGP) is used to maintain the global routing tables at core Internet routers, and the table size is typically above 180,000 entries and continues to grow over time. In this paper, we propose a novel approach, Persistent Detection and Recovery (PDR), to enable large-state protocols and applications to maintain state consistency using a soft-state approach. PDR uses state compression and receiver participation mechanisms to avoid per-state refresh overhead. We evaluate PDR’s effectiveness and scalability by applying its mechanisms to maintain the consistency of BGP routing tables between routers. Our results show that the proposed PDR mechanisms are effective and efficient in detecting and correcting route insertion, modification, and removal errors. Moreover, they eliminate the need for routers to exchange full routing tables after a session reset, thus enabling routers to recover quickly from transient session failures.     

GPU-accelerated name lookup with component encoding

Named Data Networking (NDN) aims at redesigning the current Internet: using names to identify the wanted contents instead of using IP addresses to locate the end hosts, with the goal of substantially improving the data retrieval efficiency. Different from IP routers, NDN routers forward packets by names. An NDN name is composed of a number of length-variable components, causing the name to be tens or even hundreds of characters in length. Meanwhile, NDN routing tables could be several orders of magnitude larger than the current IP routing tables. This kind of complex name constitution plus the huge-sized name table makes wire speed name lookup an extremely challenging task.     

XOR-Based Schemes for Fast Parallel IP Lookups

An IP router must forward packets at gigabit speed in order to guarantee a good quality of service. Two important factors make this task a challenging problem: (i) for each packet, the longest matching prefix in the forwarding table must be quickly computed; (ii) the routing tables contain several thousands of entries and their size grows significantly every year. Because of this, parallel routers have been developed which use several processors to forward packets. In this work we present a novel algorithmic technique which, for the first time, exploits the parallelism of the router also to reduce the size of the routing table. Our method is scalable and requires only minimal additional hardware. Indeed, we prove that any IP routing table T can be split into two subtables T₁ and T₂ such that: (a) |T₁| can be any positive integer k ≤ |T| and |T₂| ≤ |T| - k + 1; (b) the two routing tables can be used separately by two processors so that the IP lookup on T is obtained by simply XOR-ing the IP lookup on the two tables. Our method is independent of the data structure used to implement the lookup search and it allows for a better use of the processors L2 cache. For real routers routing tables, we also show how to achieve simultaneously: (a) |T₁| is roughly 7% of the original table T; (b) the lookup on table T₂ does not require the bestmatching prefix computation.     

Universal routing schemes

Summary.  In this paper, we deal with the compact routing problem, that is implementing routing schemes that use a minimum memory size on each router. A universal routing scheme is a scheme that applies to all n-node networks. In [31], Peleg and Upfal showed that one cannot implement a universal routing scheme with less than a total of Ω(n ^1+1/(2s+4)) memory bits for any given stretch factor s≧1. We improve this bound for stretch factors s, 1≦s<2, by proving that any near-shortest path universal routing scheme uses a total of Ω(n ²) memory bits in the worst-case. This result is obtained by counting the minimum number of routing functions necessary to route on all n-node networks. Moreover, and more fundamentally, we give a tight bound of Θ(n log n) bits for the local minimum memory requirement of universal routing scheme of stretch factors s, 1≦s<2. More precisely, for any fixed constant ɛ, 0<ɛ<1, there exists a n-node network G on which at least Ω(n ^ɛ) routers require Θ(n log n) bits each to code any routing function on G of stretch factor <2. This means that, whatever you choose the routing scheme, there exists a network on which one cannot compress locally the routing information better than routing tables do. Received: August 1995 / Accepted: August 1996     

Learning the valid incoming direction of IP packets

Packet forwarding on the Internet is solely based on the destination address of packets, and it is easy to forge the source address of IP packets without affecting the delivery of the packets. To solve this problem, one can have routers check whether or not every packet comes from a correct direction based on its source address field. However, due to routing asymmetry in today’s Internet, a router cannot simply reverse its forwarding table to determine the correct incoming direction of a packet.In this paper, we present the source address validity enforcement protocol, SAVE, which allows routers to learn valid incoming directions for any given source address. SAVE is independent from—and can work with—any specific routing protocol. By only interfacing with the forwarding table at routers, SAVE allows routers to properly propagate valid source address information from source address spaces to all destinations, and allows each router en route to build and maintain an incoming tree to associate each source address prefix with a corresponding incoming interface. The incoming tree is further valuable in handling routing changes: although a routing change at one router could affect the incoming direction of source address spaces from many locations, only the router that sees the change needs to send out new updates. Finally, SAVE has a good performance with low overhead.     

Space-Efficiency for Routing Schemes of Stretch Factor Three

We deal with deterministic distributed routing algorithms on arbitrary n-node networks. For each router, we want to minimize the amount of routing information that must be stored in order to implement the local routing algorithm, even if the names of the routers can be chosen in advance. We take also into account the length of the routing paths and consider the stretchfactor, which is the maximum ratio between the length of the paths computed by the routing algorithm and the distance between the source and the destination. We show that there exists an n-node network on which every routing algorithm of stretch factor s<3 requires at least a total of Ω(n²) bits of routing information. We show a similar result for networks of diameter 2.     

A routing-table-based adaptive and minimal routing scheme on network-on-chip architectures

In this paper, we present a routing algorithm that combines the shortest path routing and adaptive routing schemes for NoCs. In specific, routing follows the shortest path to ensure low latency and low energy consumption. This routing scheme requires routing information be stored in a series of routing tables created at the routers along the routing path from the source to the destination. To reduce the exploration space and timing cost for selecting the routing path, a routing list and routing table for each node are created off-line. Routing table is updated on-line to reflect the dynamic change of the network status to avoid network congestion. To alleviate the high hardware implementation cost associated with the routing tables, a method to help reduce the size of the routing tables is also introduced. Compared to the existing routing algorithms, the experimental results have confirmed that the proposed algorithm has better performance in terms of routing latency and power consumption.     

Fast binary and multiway prefix searches for packet forwarding

Backbone routers with tens-of-gigabits-per-second links are indispensable communication devices to deploy on the Internet. The IP lookup operation is the most critical task that must be improved in routers. In this paper, we first present a systematic method to compare prefixes of different lengths. The list of prefixes can then be sorted and stored in a sequential array, which is contrary to the linked lists used in most of trie-based structures. Next, fast binary and multiway prefix searches assisted by auxiliary prefixes are proposed. We also developed a 32-bit representation to encode the prefixes of different lengths. For the large routing tables currently available on the Internet, the proposed multiway prefix search can achieve the worst-case number of memory accesses of three and four if the sizes of the CPU cache lines are 64 bytes and 32 bytes, respectively. The IPv4 simulation results show that the proposed prefix searches outperform the existing IP lookup schemes in terms of lookup times and memory consumption. The simulations using IPv6 routing tables also show the performance advantages of the proposed binary prefix searches. We also analyze the performance of the existing lookup schemes by concurrently considering the lookup speed, the update speed, and the memory consumption. Although the update speed of the proposed prefix search is worse than the dynamic routing table schemes with log(N) complexity for a table of N prefixes, our analysis shows that the overall performance of the proposed binary prefix search outperforms all the existing schemes.     

支持域间分布式分组过滤的BGP扩展

可信任是下一代互联网的重要特征.目前,互联网的路由系统只按照分组的目的IP地址转发分组,携带虚假源IP地址的伪造分组也会被传输到目的地,这会在威胁接收方安全的同时,隐藏发送方的真实身份.可信任互联网的路由系统不仅需要能够正确地转发分组,而且能够验证分组来自正确的发送方.基于路由的域间分布式分组过滤是过滤伪造分组的有效方法.提出了BGP的路由选择通知功能扩展,为域间分组过滤提供过滤标准.在扩展的支持下,边界路由器能够鉴别进入本自治系统的分组的真实性,过滤掉伪造其他自治系统地址的分组.模拟结果表明,路由选择通知不会对BGP正常的路由功能产生负面影响,选择合理的路由选择时钟参数,可以在同时取得较小带宽开销和较快收敛速度的情况下,为域间分布式分组过滤提供支持.     

Randomized multipacket routing and sorting on meshes

We consider the problem of routing and sorting ond-dimensionaln×...× mesh connected computers. Each of the processing units initially holdsk packets. We present randomized algorithms that solve these problems with (1+o(1))·max{2·d·n,k·n/2} communication steps. On a torus these problems are solved twice as fast. Thus we match the bisection bound up to lower-order terms, for allk≥4·d. Earlier algorithms required some additional Θ(n) steps or more, and were more complicated. With 2·d·n extra steps our algorithm can also route in the cut-through routing model.     

高速地址Cache--散列表的应用

路由交换机由IP包进行转发时，需要查找路由表获得转发路径。但在网络层上实现此功能是一个耗费时间的过程，特别是在一个比较大的网络中进行路由交换时，其路由表会相当庞大，路由查找就成了交换机的一个瓶颈。为了解决这个问题，可采用高速地址缓存来加快路由查找过程。其基本思路是第一次IP包的路由确定后，以后的包直接转发。在具体实现中，需要有一个高速地址缓存路由信息，以便使后续的到达同一目的地的IP包块快速通过路交换机。对高速地址缓存的实现进行了探讨。     

基于前缀扩展的快速路由查找算法

该文对路由器中的快速路由查找算法进行了研究。针对路由查找算法在查找速度、算法空间复杂度以及插入和删除表项的难度算方法存在的问题,提出了一种快速路由查找算法。该算法通过构造两级索引表结构来减小路由查找的访存次数以提高查找速度;利用前缀扩展的特性并采用特殊的数据结构来构建索引表,能支持动态插入、删除和更新路由;采用压缩技术对二级索引表进行压缩,从而大大减小了路由所需的存储空间。该算法最多四次访存,最少两次访存就完成一次路由查找。由于采用了压缩方法,所需存储空间很小,该算法不仅适合于软件实现,也适合于硬件实现。查找速度快、存储空间小并支持动态插入和删除是该算法的主要特点。     

高速地址Cache-散列表的应用

路由交换机对IP进行转发时，一般需要查找路由表获得转发路径。但在网络层上实现此功能是一个耗费时间的过程，特别是在一个比较大网络中进行路由交换时，其路由表会相当庞大，路由查找就成了交换机的一个瓶颈。为了解决这个问题，可采用高速地址缓存来加快路由查找过程。其基本思路是第一次IP包的路由确定后，以后的包直接转发，在具体实现中，需要有一个高速地址缓存为暂存路由信息，以便使后续的到达同一目的地的IP包块通过路由交换机。文章对高速地址缓存的实现进行了探讨。     

Two-layer channel routing with vertical unit-length overlap

We show that anyn-net 2-terminal channel routing problem of densityd can be wired on a two-layer grid of widthw =d +O(d ^2/3) when vertical wire segments are allowed to overlap for a distance of length 1. This is a considerable asymptotic improvement over the best known, and optimal, channel width of 2d-1 for models in which no vertical overlap is allowed [RBM, PL]. Our result also improves the 3d/2+O(1) channel width achieved by a recent algorithm [G] for the same vertical overlap model. The algorithm presented in this paper produces at most 4 overlaps of unit length between any two nets, usesO(n) contacts, and can be implemented to run inO(nd ^2/3) time. We also generalize the algorithm to multi-terminal channel routing problems for which our algorithm uses a width ofw = 2d +O(d ^2/3).This work was supported by the Office of Naval Research under Contract N00014-84-K-0502 and by the National Science Foundation under Grant DMC-84-13496.     

IP Routing table compaction and sampling schemes to enhance TCAM cache performance

Routing table lookup is an important operation in packet forwarding. This operation has a significant influence on the overall performance of the network processors. Routing tables are usually stored in main memory which has a large access time. Consequently, small fast cache memories are used to improve access time. In this paper, we propose a novel routing table compaction scheme to reduce the number of entries in the routing table. The proposed scheme has three versions. This scheme takes advantage of ternary content addressable memory (TCAM) features. Two or more routing entries are compacted into one using don’t care elements in TCAM. A small compacted routing table helps to increase cache hit rate; this in turn provides fast address lookups. We have evaluated this compaction scheme through extensive simulations involving IPv4 and IPv6 routing tables and routing traces. The original routing tables have been compacted over 60% of their original sizes. The average cache hit rate has improved by up to 15% over the original tables. We have also analyzed port errors caused by caching, and developed a new sampling technique to alleviate this problem. The simulations show that sampling is an effective scheme in port error-control without degrading cache performance.     

Packet Routing in Networks with Long Wires

In this paper, we examine the packet routing problem for networks with wires of differing length. We consider this problem in a network independent context, in which routing time is expressed in terms of "congestion" and "dilation" measures for a set of packet paths. We give, for any constant ε > 0, a randomized on-line algorithm for routing any set of N packets in O((C lg^ε(Nd) + D lg(Nd))/lg lg(Nd)) time, where C is the maximum congestion and D is the length of the longest path, both taking wire delays into account, and d is the longest path in terms of number of wires. We also show that for edge-simple paths, there exists a schedule (which could be found off-line) of length O((cd_max + D) (lg(d_max)/lg lg (d_max))), where d_max is the maximum wire delay in the network. These results improve upon previous routing results which assume that unit time suffices to traverse a wire of any length. They also yield improved results for job-shop scheduling as long as we incorporate a technical restriction on the job-shop problem.     

An Internet without the Internet protocol

The growth of the Internet has brought about many challenges for its critical infrastructure. The DNS infrastructure, which translates mnemonic host names into IP addresses understood by the routers, is frequently the target of cache poisoning attacks. Internet routers are also experiencing alarming growth in their routing table sizes, which may soon make it impossible for them to forward packets quickly enough to meet demand. Further, concerns about IPv4 address space exhaustion loom on the horizon despite the availability of IPv6. In this paper, we take a fresh look at Internet routing and propose a scheme that addresses all of these concerns cleanly. Our scheme forgoes IP addresses entirely and instead uses host names as identifiers in packets. The scalability of routing is ensured by encapsulating these packets in highly aggregated routing locators: we use autonomous system numbers (ASNs), which are already an integral part of inter-domain routing. We present data and experiments to show that a much simpler and scalable routing infrastructure can be designed for a future Internet by using fewer identifiers for its entities.     

A generalized greedy routing algorithm for 2-connected graphs

Geometric routing by using virtual locations is an elegant way for solving network routing problems. In its simplest form, greedy routing, a message is simply forwarded to a neighbor that is closer to the destination. One main drawback of this approach is that the coordinates of the virtual locations require Ω(nlogn) bits to represent, which makes this scheme infeasible in some applications.The essence of the geometric routing is the following: When an origin vertex u wants to send a message to a destination vertex w, it forwards the message to a neighbor t, solely based on the location information of u,w and all neighbors of u. In the greedy routing scheme, the decision is based on decreasing distance. For this idea to work, however, the decision needs not be based on decreasing distance. As long as the decision is made locally, this scheme will work fine.In this paper, we introduce a version of greedy routing which we call generalized greedy routing algorithm. Instead of relying on decreasing distance, a generalized greedy routing algorithm uses other criteria to determine routing paths, solely based on local information. We present simple generalized greedy routing algorithms based on st-coordinates (consisting of two integers between 0 and n−1), which are derived from an st-orientation of a 2-connected plane graph. We also generalize this result to arbitrary trees. Both algorithms are natural and simple to be implemented.     

All-to-all disjoint multipath routing using cycle embedding

In this paper, we evaluate the performance of disjoint multipath routing approaches for all-to-all routing in packet-switched networks with respect to packet overhead, path length, and routing table size. We develop a novel approach based on cycle embedding to obtain two node-disjoint paths between all source–destination pairs with reduced number of routing table entries maintained at a node (hence the reduced lookup time), small average path length, and less packet overhead. We study the trade-off between the number of routing table entries maintained at a node and the average length of the two disjoint paths by: (a) formulating the cycle-embedding problem as an integer linear program; and (b) developing a heuristic. We show that the number of routing table entries at a node may be reduced to at most two per destination using cycle-embedding approach if the average length of the disjoint paths are allowed to exceed the minimum by 25%.