Method of address compression for cell-based and...

Details Method of address compression for cell-based and... Method of address compression for cell-based and...

1999-07-30

2003-04-15

Patel, Ajit (Department: 2664)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S401000

Reexamination Certificate

active

06549536

ABSTRACT:

1 BACKGROUND OF THE INVENTION
1.1 Address Compression Problem Definition
Notably, for each Communication Protocol, an Incoming Address Space (the maximum number of channels a specific protocol can handle) is defined. In this document reference is made to the so-called addressing space of 2
N
bits as the set of Incoming Addresses.
On the other hand, a telecom equipment is able to deal only with some managed channels. The number of simultaneously manageable channels is finite and is a typical design target. Each managed channel must be addressable by means of an internal identifier, that is a subset of the Incoming Address. In this document reference is made to the space of 2
Ncpr
bits of the internal identifiers as the set of Compressed Addresses.
In a telecom equipment, a function mapping some points belonging to the universe of Incoming addresses (2
N
bits) to a set of Compressed Identifiers (2
Ncpr
bits) should be implemented. This function is called the Address Compression Function.
Due to network management reasons, the Incoming Address Space is very large. On the other hand, the number of channels that must be managed simultaneously nowadays by telecommunication apparatuses is also very large. Moreover, data link speed is increasing at an impressive pace: in ten years from 64 Kbit/s to 155 Mbit/s and now to 1.2 Gbit/s.
Because of this, the efficiency of the design of the Address Compression Function is today a key factor in equipment like routers and switches. Altogether, designing has become critical because, due to the increased data speed, the time that can be spared to perform the Address Compression Function is reduced. On the other hand, the increasing number of manageable channels augments costs because of the increasing number of resources needed to perform the Address Compression Function.
1.1.1 Address Compression Problem Definition
The aim of the algorithm is to compress a defined set of addresses S, the set of addresses to be compressed, belonging to the set U, the whole addressing space, as shown in FIG.
1
. For each of these addresses the algorithm must identify one and only one address belonging to C, the set of compressed address (i.e. perform a transformation S→C).
n dimension of the whole addressing space (U≡{a
0
, . . . , a
2
n
})
n
cpr
dimension of the space of compressed addresses (C≡{a
0
, . . . , a
2
ncpr
})
where: n
cpr
<n, C⊂U.
The cardinality of S must equals the cardinality of C.
1.1.2 Address Compression Function and IP Application
The most fundamental operation in any IP routing product is the Routing Table search process.
A packet is received with a specific Destination Address (DA), identified by a unique 32-bit field in current IP Version 4 implementations. The router must search a forwarding table using the IP Destination Address as its key and determine which entry in the table represents the best route for the packet to take in its journey across the network to its destination.
A <<flat>> forwarding table would have a size of 2
32
addresses, that means 4 Gbytes of address space (16 Gbytes of data). The DA must be compressed to point to a reasonable table size.
The route search operation is the single most time-consuming operation that must be performed in routers today, and typically defines the upper bound, on the router's ability to forward packets.
The problem has grown even more challenging in recent years.
Data links now operate routinely at 100 MBits/second, and generate nearly 150,000 packets-per-second requiring routing.
New protocols, such as RSVP, require route selection based not only on Destination Address, but potentially also Protocol Number, Source Address, Destination Port and Source Port.
IP Version 6 will increase the size of the address field from 32 bits to 128 bits, with network prefixes up to 64 bits in length. Expanded use of IP Multicasting requires that searches include large numbers of Class D (Multicast Group) addresses with large numbers of users.
Moreover, the ever-expanding number of networks and hosts on Internet is making routing table sizes larger and larger.
1.1.3 Address Compression Function and ATM Applications
ATM data equipment, to be compliant with ITU and ATM-forum specifications, must be able to receive ATM cells for any admissible value of the header fields VPI.VCI. The total length of these fields is 24 bits (16.7 millions of admissible values).
On the other hand, the ATM equipment is designed to manage a number of internal channels (at least) equal to the maximum number of engageable channels. This number depends on the application: from one to hundreds in the case of terminals; some thousands (4K, 64K) in case of core network equipment.
In the following description, the univocal (shorter) internal channel identifier, will be referred to as Channel Identifier (CID).
It is evident the requisite that the processing be able to map from any possible value of VPI.VCI (24 bits) to any possible CID (e.g. 12 bits).
1.2 Algorithm Classes
A compression function able to map from a string of length N bits to a (unique) string of length Ncpr (Ncpr<N) can be implemented in various ways.
Two main classes exist: the algorithms with an unpredictable duration belong to a first class; the others, with a predictable duration, belong to the second one.
For those belonging to the first class, it is not possible to know for how much time (microprocessor instructions or clock cycles) the algorithm will run before hitting the compressed identifier. It will depend on the number of active connections. These algorithms are normally easier to implement, do not require lots of resources and can be sped-up only by improving RAM access time of the memories where the search tables are located.
For the algorithms of the second class, (predictable duration algorithms) it is possible to know, UNDER ANY CONDITION, how much time (microprocessor instructions or clock cycles) the algorithm will run before hitting the compressed identifier. These algorithms often require a lot of resources.
An algorithm belonging to the second class ensures that the maximum search time is less than the time used to receive the shortest packet
1
, this guarantees the maximum allowable throughput of the equipment.
1
64 bytes for IP, 53 bytes for ATM
1.2.1 Unpredictable Duration Algorithms
IP routers companies have developed the algorithms belonging to this class some years ago. It is possible to call them <<classical route search techniques>>. The main algorithms will be explained for an IP context to provide the reader with useful historical background.
1.2.1.1 The Patricia Tree
This is the most popular algorithm used in router “slow paths”. The forwarding table, (associating each prefix entry with an exit port and next-hop MAC address) is stored in a “Binary Root Tree” form.
The table is organized in a series of “nodes”, each of which contains a route of different length, and each of which has two “branches” to subsequent nodes in the tree. At the ends of the branches there are “leaves”, which either represent full 32-bit host routes (for devices attached directly to the router) or most-specific routes available to a particular subnet.
The algorithm is able to map ANY incoming vector to a unique outcoming identifier. Unfortunately, in the worst case, the algorithm will have to travel all the way to the end of the tree to find a leaf, and the time needed cannot be absolutely predictable.
The Patricia Tree approach does not scale well to level-2 packet switching: a worst-case lookup involves a large number of memory accesses, taking far more time than that available at gigabit rates. Moreover, hardware implementation is rather complex. This algorithm was developed for general-purpose software implementations.
1.2.1.2 Hashing Tables
“Hashing” is an alternative approach. Unlike the Patricia Tree, hashing operates strictly on an exact-match basis, and assumes that the number of <<channels>> (IP Destination Addresses, VPI/VCIout) the system must handle at any on

Affiliated with

Also associated with

Rating

Method of address compression for cell-based and... 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 address compression for cell-based and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of address compression for cell-based and... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3040190