text:
#include "stp/cpp_interface.h"
#include "stp/ToSat/AIG/ToSATAIG.h"
#include "stp/STPManager/STPManager.h"
#include "stp/STPManager/STP.h"
#include "stp/Parser/LetMgr.h"
#include <cassert>

using std::cerr;
using std::cout;
using std::endl;

namespace stp
{
void Cpp_interface::checkInvariant()
{
  assert(bm.getAssertLevel() == cache.size());
  assert(bm.getAssertLevel() == symbols.size());
}

void Cpp_interface::init()
{
  assert(nf != NULL);
  alreadyWarned = false;

  cache.push_back(Entry(SOLVER_UNDECIDED));
  symbols.push_back(ASTVec());

  if (bm.getVectorOfAsserts().size() == 0)
    bm.Push();

  print_success = false;
  ignoreCheckSatRequest = false;
}

Cpp_interface::Cpp_interface(STPMgr& bm_, NodeFactory* factory)
    : bm(bm_), letMgr(new LETMgr(bm.ASTUndefined)), nf(factory)
{
  init();
}

void Cpp_interface::startup()
{
  CONSTANTBV::ErrCode c = CONSTANTBV::BitVector_Boot();
  if (0 != c)
  {
    cout << CONSTANTBV::BitVector_Error(c) << endl;
    FatalError("Bad startup");
  }
}

const ASTVec Cpp_interface::GetAsserts(void)
{
  return bm.GetAsserts();
}

const ASTVec Cpp_interface::getAssertVector(void)
{
  return bm.getVectorOfAsserts();
}

UserDefinedFlags& Cpp_interface::getUserFlags()
{
  return bm.UserFlags;
}

void Cpp_interface::AddAssert(const ASTNode& assert)
{
  bm.AddAssert(assert);
}

void Cpp_interface::AddQuery(const ASTNode& q)
{
  bm.AddQuery(q);
}

ASTNode Cpp_interface::CreateNode(stp::Kind kind, const stp::ASTVec& children)
{
  return nf->CreateNode(kind, children);
}

ASTNode Cpp_interface::CreateNode(stp::Kind kind, const stp::ASTNode n0,
                                  const stp::ASTNode n1)
{
  if (n0.GetIndexWidth() > 0 && !alreadyWarned)
  {
    cerr << "Warning: Parsing a term that uses array extensionality. "
            "STP doesn't handle array extensionality." << endl;
    alreadyWarned = true;
  }
  return nf->CreateNode(kind, n0, n1);
}

ASTNode Cpp_interface::CreateZeroConst(unsigned int width)
{
  return bm.CreateZeroConst(width);
}

ASTNode Cpp_interface::CreateOneConst(unsigned int width)
{
  return bm.CreateOneConst(width);
}

ASTNode Cpp_interface::CreateBVConst(string& strval, int base, int bit_width)
{
  return bm.CreateBVConst(strval, base, bit_width);
}

ASTNode Cpp_interface::CreateBVConst(const char* const strval, int base)
{
  return bm.CreateBVConst(strval, base);
}

// FIXME: unsigned long long int is disgusting! use intN_t from cstdint.h
ASTNode Cpp_interface::CreateBVConst(unsigned int width,
                                     unsigned long long int bvconst)
{
  return bm.CreateBVConst(width, bvconst);
}

ASTNode Cpp_interface::LookupOrCreateSymbol(const char* const name)
{
  return bm.LookupOrCreateSymbol(name);
}

void Cpp_interface::removeSymbol(ASTNode s)
{
  bool removed = false;

  for (size_t i = 0; i < symbols.back().size(); i++)
    if (symbols.back()[i] == s)
    {
      symbols.back().erase(symbols.back().begin() + i);
      removed = true;
    }

  if (!removed)
    FatalError("Should have been removed...");

  letMgr->_parser_symbol_table.erase(s);
}

void Cpp_interface::storeFunction(const string name, const ASTVec& params,
                                  const ASTNode& function)
{
  Function f;
  f.name = name;

  ASTNodeMap fromTo;
  for (size_t i = 0, size = params.size(); i < size; ++i)
  {
    ASTNode p = bm.CreateFreshVariable(params[i].GetIndexWidth(),
                                       params[i].GetValueWidth(),
                                       "STP_INTERNAL_FUNCTION_NAME");
    fromTo.insert(std::make_pair(params[i], p));
    f.params.push_back(p);
  }

  ASTNodeMap cache;
  f.function = SubstitutionMap::replace(function, fromTo, cache, nf);
  functions.insert(std::make_pair(f.name, f));
}

ASTNode Cpp_interface::applyFunction(const string name, const ASTVec& params)
{
  if (functions.find(name) == functions.end())
    FatalError("Trying to apply function which has not been defined.");

  Function f;
  f = functions[string(name)];

  ASTNodeMap fromTo;
  for (size_t i = 0, size = f.params.size(); i < size; ++i)
  {
    if (f.params[i].GetValueWidth() != params[i].GetValueWidth())
      FatalError("Actual parameters differ from formal");

    if (f.params[i].GetIndexWidth() != params[i].GetIndexWidth())
      FatalError("Actual parameters differ from formal");

    fromTo.insert(std::make_pair(f.params[i], params[i]));
  }

  ASTNodeMap cache;
  return SubstitutionMap::replace(f.function, fromTo, cache, nf);
}

bool Cpp_interface::isBitVectorFunction(const string name)
{
  return ((functions.find(name) != functions.end()) &&
          functions.find(name)->second.function.GetType() == BITVECTOR_TYPE);
}

bool Cpp_interface::isBooleanFunction(const string name)
{
  return ((functions.find(name) != functions.end()) &&
          functions.find(name)->second.function.GetType() == BOOLEAN_TYPE);
}

ASTNode Cpp_interface::LookupOrCreateSymbol(string name)
{
  return bm.LookupOrCreateSymbol(name.c_str());
}

bool Cpp_interface::LookupSymbol(const char* const name, ASTNode& output)
{
  return bm.LookupSymbol(name, output);
}

bool Cpp_interface::isSymbolAlreadyDeclared(char* name)
{
  return bm.LookupSymbol(name);
}

void Cpp_interface::setPrintSuccess(bool ps)
{
  print_success = ps;
}

bool Cpp_interface::isSymbolAlreadyDeclared(string name)
{
  return bm.LookupSymbol(name.c_str());
}

ASTNode* Cpp_interface::newNode(const Kind k, const ASTNode& n0,
                                const ASTNode& n1)
{
  return newNode(CreateNode(k, n0, n1));
}

ASTNode* Cpp_interface::newNode(const Kind k, const int width,
                                const ASTNode& n0, const ASTNode& n1)
{
  return newNode(nf->CreateTerm(k, width, n0, n1));
}

ASTNode* Cpp_interface::newNode(const ASTNode& copyIn)
{
  return new ASTNode(copyIn);
}

void Cpp_interface::deleteNode(ASTNode* n)
{
  delete n;
}

void Cpp_interface::addSymbol(ASTNode& s)
{
  symbols.back().push_back(s);
  letMgr->_parser_symbol_table.insert(s);
}

void Cpp_interface::success()
{
  if (print_success)
  {
    cout << "success" << endl;
    flush(cout);
  }
}

void Cpp_interface::resetSolver()
{
  bm.ClearAllTables();
  GlobalSTP->ClearAllTables();
}

void Cpp_interface::popToFirstLevel()
{
  while (symbols.size() > 1)
    pop();

  // I don't understand why this is required.
  while (bm.getAssertLevel() > 0)
    bm.Pop();
}

void Cpp_interface::pop()
{
  if (symbols.size() == 0)
    FatalError("Popping from an empty stack.");
  if (symbols.size() == 1)
    FatalError("Can't pop away the default base element.");

  bm.Pop();

  // These tables might hold references to symbols that have been
  // removed.
  resetSolver();

  cache.erase(cache.end() - 1);
  ASTVec& current = symbols.back();
  for (size_t i = 0, size = current.size(); i < size; ++i)
    letMgr->_parser_symbol_table.erase(current[i]);

  symbols.erase(symbols.end() - 1);
  checkInvariant();
}

void Cpp_interface::push()
{
  // If the prior one is unsatisiable then the new one will be too.
  if (cache.size() > 1 && cache.back().result == SOLVER_UNSATISFIABLE)
    cache.push_back(Entry(SOLVER_UNSATISFIABLE));
  else
    cache.push_back(Entry(SOLVER_UNDECIDED));

  bm.Push();
  symbols.push_back(ASTVec());

  checkInvariant();
}

void Cpp_interface::ignoreCheckSat()
{
  ignoreCheckSatRequest = true;
}

void Cpp_interface::printStatus()
{
  for (size_t i = 0, size = cache.size(); i < size; ++i)
  {
    cache[i].print();
  }
  cerr << endl;
}

// Does some simple caching of prior results.
void Cpp_interface::checkSat(const ASTVec& assertionsSMT2)
{
  if (ignoreCheckSatRequest)
    return;

  bm.GetRunTimes()->stop(RunTimes::Parsing);

  checkInvariant();
  assert(assertionsSMT2.size() == cache.size());

  Entry& last_run = cache.back();
  if ((last_run.node_number != assertionsSMT2.back().GetNodeNum()) &&
      (last_run.result == SOLVER_SATISFIABLE))
  {
    // extra asserts might have been added to it,
    // flipping from sat to unsat. But never from unsat to sat.
    last_run.result = SOLVER_UNDECIDED;
  }

  // We might have run this query before, or it might already be shown to be
  // unsat. If it was sat,
  // we've stored the result (but not the model), so we can shortcut and return
  // what we know.
  if (!((last_run.result == SOLVER_SATISFIABLE) ||
        last_run.result == SOLVER_UNSATISFIABLE))
  {
    resetSolver();

    ASTNode query;

    if (assertionsSMT2.size() > 1)
      query = nf->CreateNode(AND, assertionsSMT2);
    else if (assertionsSMT2.size() == 1)
      query = assertionsSMT2[0];
    else
      query = bm.ASTTrue;

    SOLVER_RETURN_TYPE last_result = GlobalSTP->TopLevelSTP(query, bm.ASTFalse);

    // Store away the answer. Might be timeout, or error though..
    last_run = Entry(last_result);
    last_run.node_number = assertionsSMT2.back().GetNodeNum();

    // It's satisfiable, so everything beneath it is satisfiable too.
    if (last_result == SOLVER_SATISFIABLE)
    {
      for (size_t i = 0; i < cache.size(); i++)
      {
        assert(cache[i].result != SOLVER_UNSATISFIABLE);
        cache[i].result = SOLVER_SATISFIABLE;
      }
    }
  }

  if (bm.UserFlags.quick_statistics_flag)
  {
    bm.GetRunTimes()->print();
  }

  (GlobalSTP->tosat)->PrintOutput(last_run.result);
  bm.GetRunTimes()->start(RunTimes::Parsing);
}

// This method sets up some of the globally required data.
Cpp_interface::Cpp_interface(STPMgr& bm_)
    : bm(bm_), letMgr(new LETMgr(bm.ASTUndefined)), nf(bm_.defaultNodeFactory)
{
  nf = bm.defaultNodeFactory;
  startup();
  stp::GlobalParserInterface = this;

  Simplifier* simp = new Simplifier(&bm);
  ArrayTransformer* at = new ArrayTransformer(&bm, simp);
  AbsRefine_CounterExample* abs = new AbsRefine_CounterExample(&bm, simp, at);
  ToSATAIG* tosat = new ToSATAIG(&bm, at);

  stp::GlobalParserBM = &bm_;

  GlobalSTP = new STP(&bm, simp, at, tosat, abs);
  init();
}

void Cpp_interface::deleteGlobal()
{
  delete GlobalSTP;
}

void Cpp_interface::cleanUp()
{
  letMgr->cleanupParserSymbolTable();
  cache.clear();
  symbols.clear();
}
}

redpajama_set_name: RedPajamaGithub


text:
CA2842555A1 - Methods and systems for network address lookup engines - Google Patents
Methods and systems for network address lookup engines Download PDF
Warren J. Gross
Naoya Onizawa
2014-02-07 Application filed by McGill University filed Critical McGill University
H04L45/00—Routing or path finding of packets in data switching networks
H04L45/74—Address processing for routing
H04L45/745—Address table lookup or address filtering
H04L45/46—Cluster building
Internet routers are a key component in today's Internet. Each router forwards received packets toward their final destinations based upon a Longest Prefix Matching (LPM) algorithm select an entry from a routing table that determines the closest location to the final packet destination among several candidates. Prior art solutions to LPM lookup offer different tradeoffs and that it would be beneficial for a design methodology that provides for low power large scale IP lookup engines addressing the limitations within the prior art.
According to embodiments of the invention a low-power large-scale IP lookup engine may be implemented exploiting clustered neural networks (CNNs). In addition to reduced power consumption embodiments of the invention provide reduced transistor count providing for reduced semiconductor die footprints and hence reduced die cost.
U = 11 4 1.1 10 1. __ 4 11 $ = ___ CROSS-REFERENCE TO RELATED APPLICATIONS
[001] This patent application claims the benefit of U.S. Provisional Patent Application 61/761,998 filed on February 7, 2013 entitled "Methods and Systems for Network Address Lookup Engines."
[002] This invention relates to address look-up engines and more particularly to address look-up engines with low power, die area efficiency, and compatibility with high speed packet datarates.
[003] In 2011 Cisco Systems 5th Annual Visual Networking Index Forecast the networking giant forecast that global Internet traffic will reach approximately 1 zettabyte a year by 2015 ( 966 x ). Breaking this down this equates to approximately 80 exabytes per month in 2015, up from approximately 20 exabytes per month in 2010, or 245 terabytes per second.
This global Internet traffic will arise from approximately 3 billion people using approximately 6 billion portable and fixed electronic devices. At the same time average broadband access speeds will have increased to nearly 30 megabits per second from the approximately 7 megabits per second in 2011. This Internet traffic and consumer driven broadband access being supported through a variety of local, metropolitan, and wide area networks together with long haul, trunk, submarine, and backbone networks operating at OC-48 (2.5Gb/s), OC-192 (10Gb/s), OC-768 (40Gb/s) with coarse and dense wavelength division multiplexing to provide overall channel capacities in some instances in excess of 1Tb/s.
[004] Dispersed between and within these networks are Internet routers which have become key to the Internet backbone. Such routers including, but not limited to, edge routers, subscriber edge routers, inter-provider border routers, and core routers.
Accordingly, the overall data handled by these Internet routers by 2015 will be many times the approximately 1 zettabyte actually provided to users who will have expectations not only of high access speeds but low latency. Accordingly, Internet routers require fast IP-lookup operations -1-.
utilizing hundred thousands of entries or more. Each router forwarding received packets toward their final destinations based upon a Longest Prefix Matching (LPM) algorithm to select an entry from a routing table that determines the closest location to the final packet destination among several candidates. As an entry in a routing table may be specify a network, one destination address may match more than one routing table entry.
The most specific table entry, the one with the highest subnet mask, being called the longest prefix match. With the length of a packet being up to 32 bits for Internet Protocol version 4 (IPv4) and 144 bits for Internet Protocol version 6 (IPv6) it is evident that even at 0C-48 (2.5Gb/s) with maximum length IPv6 packets over 17 million packets are received per second. These packets containing binary strings and wildcards.
10051 The hardware of the LPM has been designed within the prior art using several approaches including, but not limited to:
- Ternary Content-Addressable Memory (TCAM), see for example Gamache et. al.
in "A fast ternary CAM design for IP networking applications" (Proc. 12th IEEE
ICCCN, pp. 434 ¨ 439), Noda et. al. in "A cost-efficient high-performance dynamic TCAM with pipelined hierarchical searching and shift redundancy architecture"
(IEEE JSSC, Vol. 40, No. 1, pp. 245 ¨ 253), Maurya et. al. in "A dynamic longest prefix matching content addressable memory for IP routing" (IEEE TVLSI, Vol.
19, No. 6, pp. 963 ¨972), and Kuroda et. al. "A 200Msps, 0.6W eDRAM-based search engine applying full-route capacity dedicated FIB application" (Proc. CICC
2012, pp.
1-4);
- Trie-based schemes, see for example, Eatherton et al. "Tree bitmap:
hardware/software IP lookups with incremental updates" (SIGCOMM Comput.
Commun. Rev., Vol. 34, No. 2, pp. 97-122), and Bando et al "Flashtrie: Beyond Gb/s IP route lookup using hash-based prefix-compressed trie" (IEEE/ACM Trans.
Networking, Vol. 20, No. 4, pp. 1262 ¨1275); and - Hash-based schemes, see for example Hasan et. al. in "Chisel: A storage-efficient, collision-free hash-based network processing architecture" (Proc. 33rd ISCA, pp. 203-215, June 2006) and Dharmapurilcar et al. in "Longest prefix matching using bloom filters" ( IEEE/ACM Trans. Networking 2006, Vol. 14, No. 2, pp. 397 ¨409).
[0061 Unlike random access memory (RAM) which RAM returns the data word stored at a supplied memory address a Content Addressable Memory (CAM) searches its entire memory to see if a data word supplied to it is stored anywhere within it. If the data word is found, the CAM returns a list of the one or more storage addresses where the word was found. A
Ternary Content Addressable Memory (TCAM) allows a third matching state of "X"
(or "Don't Care") in addition to "0" and "1" for one or more of the bits within the stored data word, thus adding flexibility to the search. Beneficially TCAMs perform the search of all entries stored in the TCAM cells in parallel and allow therefore for high-speed lookup operations. However, the large area of the cell, exploiting 16 transistors versus the 6 transistors in a static RAM (SRAM) cell and the brute-force searching methodology result in large power dissipation and inefficient hardware architectures for large forwarding tables. In contrast trie-based schemes exploit ordered tree data structures to store prefixes and locations based on this binary-tree structure that is created based on portions of stored Internet Protocol (IP) addresses. Searching is performed by traversing the tree until an LPM is found and may be implemented in hardware using SRAMs, rather than TCAMs, which potentially lowers power dissipation. However, deep trees require multi-step lookups slowing the determination of the LPM. Hash-based schemes use one or more hash tables to store prefixes where the benefit is scalability as table size is increased with length-independent searching speed.
However, hash-based schemes have a possibility of collisions that requires post-processing to decide on only one output and requires reading many hash tables for each length of stored strings thereby slowing the process.
[007] According, it would be evident that prior art solutions to LPM lookup offer different tradeoffs and that it would be beneficial for a design methodology that provides for low power large scale IP lookup engines addressing the limitations within the prior art. With carriers looking to add picocells, for example with ranges of a few hundred metres, to augment microcells and base stations in order to address capacity demands in dense urban environments for example power consumption becomes an important factor against conventional IP router deployment scenarios. According to embodiments of the invention a low-power large-scale IP lookup engine may be implemented exploiting clustered neural networks (CNNs). In addition to reduced power consumption embodiments of the invention provide reduced transistor count providing for reduced semiconductor die footprints and hence reduced die cost.
[008] Beneficially low cost TCAMs would allow for their deployment within a variety of other applications where to date they have not been feasible due to cost as well as others where their deployment had not been previously considered. For example, TCAMs would enable routers to perform additional functions beyond address lookups, including, but not limited to, virus detection and intrusion detection.
[0091 Other aspects and features of the present invention will become apparent to those ordinarily skilled in the art upon review of the following description of specific embodiments of the invention in conjunction with the accompanying figures.
[00101 It is an object of the present invention to address limitations in the prior art for address look-up engines and more particularly to providing address look-up engines with low power, die area efficiency, and compatibility with high speed packet datarates [00111 In accordance with an embodiment of the invention there is provided a device comprising a clustered neural network processing algorithms storing ternary data.
[00121 In accordance with an embodiment of the invention there is provided a device comprising:
a first plurality of input clusters forming a first predetermined portion of a clustered neural network, each input cluster comprising of a first predetermined number of input neurons; and a second plurality of output clusters forming a second predetermined portion of the clustered neural network, each output cluster comprising a second predetermined number of output neurons; wherein, the clustered neural network stores a plurality of network addresses and routing rules relating to the network addresses as associations.
[00131 In accordance with an embodiment of the invention there is provided a method comprising:
providing an address lookup engine for a routing device employing a clustered neural network capable of processing ternary data;
teaching the address lookup engine about a plurality of addresses and their corresponding rules for routing data packets received by the routing device in dependence upon at least an address forming a predetermined portion of the data packet; and routing data packets using the address lookup engine.
[0014] Other aspects and features of the present invention will become apparent to those ordinarily skilled in the art upon review of the following description of specific embodiments of the invention in conjunction with the accompanying figures.
[0015] Embodiments of the present invention will now be described, by way of example only, with reference to the attached Figures, wherein:
100161 Figure 1 depicts a prior art IP lookup engine exploiting TCAMs;
[0017] Figure 2A and 2B depict an IP lookup engine exploiting CNNs without wildcards in learning and retrieving processes;
[0018] Figures 3A to 3C depict an IP lookup engine according to an embodiment of the invention exploiting wildcards in local storing, dummy neuron activation, and global storing processes;
[0019] Figures 4A to 4C depict a retrieving process for use within an IP
lookup scheme with wildcards according to an embodiment of the invention;
[0020] Figures 5A to 5D depict a retrieving process for use within an IP
[00211 Figure 6 depicts ambiguity probability versus number of learnt messages for an IP
engine according to an embodiment of the invention;
[0022] Figure 7 depicts a first implementation architecture for an IP lookup engine according to an embodiment of the invention;
[0023] Figure 8 depicts circuit schematics for a dummy generator and input selection block forming portions of an IP lookup engine according to the first implementation architecture in Figure 7;
[0024] Figure 9 depicts a circuit schematic for a decoding module forming part of an IP
lookup engine according to the first implementation architecture in Figure 7;
[0025] Figure 10 depicts a second implementation architecture for an IP lookup engine according to an embodiment of the invention;
[0026] Figures 11A and 11B depict circuits schematics for memory blocks providing local storing (MLS) and global storing (MGS) forming portions of an IP lookup engine according to the second implementation architecture in Figure 10;
[0027] Figures 12A and 12B depict circuits schematics for input replacement based upon ILSW and dummy generator based upon MILSW forming portions of IP lookup engines according to the second implementation architecture in Figure 10 for ILSW and MILSW
variants;
[0028] Figures 13A and 13B depict circuits schematics for decoding modules based upon ILSW and MILSW respectively forming portions of IP lookup engines according to the second implementation architecture in Figure 10 for ILSW and MILSW variants;
[0029] Figures 14A and 14B depict circuits schematics for ambiguity elimination block and output selector forming portions of IP lookup engines according to the second implementation architecture in Figure 10;
[0030] Figure 15 depicts the average and maximum number of ambiguous entries versus the number of stored addresses for ILSW and MILSW IP lookup engines according to embodiments of the invention;
[0031] Figure 16 depicts the maximum Nõ,, versus number of stored tables (N) with correlated table patterns for ILSW and MILSW IP lookup engines according to embodiments of the invention;
[0032] The present invention is directed to address look-up engines and more particularly to address look-up engines with low power, die area efficiency, and compatibility with high speed packet datarates.
[0033] The ensuing description provides exemplary embodiment(s) only, and is not intended to limit the scope, applicability or configuration of the disclosure. Rather, the ensuing description of the exemplary embodiment(s) will provide those skilled in the art with an enabling description for implementing an exemplary embodiment. It being understood that various changes may be made in the function and arrangement of elements without departing from the spirit and scope as set forth in the appended claims.
[0034] Within the specification a variety of subscripts in respect to mathematical descriptions of embodiments of the invention are employed. Where possible the standard format of Rs , where R is a variable and S is an integer, is employed. However, where Rs is itself a subscript to another term then these are denoted as RS for clarity to avoid multiple levels of subscripts which are difficult to interpret in the published patent application.
100351 1. BACKGROUND
100361 As noted supra =embodiments of the invention for low-power large-scale IP lookup engines are implemented exploiting clustered neural networks (CNNs). A CNN is a neural network which stores data using only binary weighted connections between several clusters, see for example Gripon et al. in "Sparse neural networks with large learning diversity" (IEEE
Trans. Neural Networks, Vol. 22, No. 7, pp. 1087-1096). Compared with a classical Hopfield Neural Network (HNN), see for example Hopfield in "Neural networks and physical systems with emergent collective computational abilities" (Proc. Nat. Academy of Sciences, Vol. 79, No. 8, pp. 2554-2558), the CNN requires less complex functions while learning (storing) larger number of messages. A hardware implementation for a CNN has been reported by Jarollahi et. at. in "Architecture and implementation of an associative memory using sparse clustered networks" (Proc. ISCAS 2012, pp. 2901-2904).
[0037] However, within an IF lookup engine there is the requirement for ternary not binary logic as LPM searching algorithms exploit three values, namely "0", "1", "don't care", which would make them incompatible with prior art CNNs. Accordingly, as described below in respect of embodiments of the invention, the inventors have extended the CNN
concept to process ternary logic. Further, unlike TCAMs that store IP addresses themselves, hardware embodiments of the invention store the associations between IP addresses and output rules, increasing memory efficiency. The output rule may, in some embodiments of the invention, be determined through low complexity hardware using associations read from SRAMs, thereby reducing the search power dissipation compared with that of prior art TCAMs that require brute-force searches. As both IF addresses and their rules can be stored as associations in the proposed IP lookup engine, the additional SRAM that stores rules within a conventional TCAM-based IP lookup engine is not required.
1003812. PRIOR ART TCAM BASED IP LOOKUP SCHEME
[0039] Figure 1 depicts an IP lookup scheme using a TCAM and a SRAM according to the prior art of Pagiamtzis et. at. in "Content-addressable memory (CAM) circuits and architectures: a tutorial and survey" (IEEE JSSC 2006, Vol. 41, No. 3, pp. 712-727). Ternary content-addressable memories (TCAMs) contain large number of entries from hundreds to several hundred thousand. Each entry contains binary address information and a wildcard (X) in TCAMs, while only binary information is stored in binary CAMs. The size of the entry is several dozen to hundreds, e.g. 128, 144 bit.s, for IPv6, see for example Huang et at. in "A 65 nm 0.165 fl/bit/search 256x144 TCAM macro design for IPv6 lookup tables"
(IEEE
JSSC 2011, Vol. 46, No. 2, pp. 507-519). In operation an input address is broadcast onto all entries through search lines and one or more entries are matched. A priority encoder finds the longest prefix match among these matched entries and determines a matched location that is an address of a SRAM containing rules. Since the matched location in the TCAM
corresponds to an address of the SRAM, the corresponding rule is read.
100401 As depicted in Figure 1, an input address is 42.120.10.23 and this matches two entries, 42.120.10.23 and 42.120.10.X as X is a wildcard. Although two matched locations are activated, the matched location corresponding to 42.120.10.23 is selected.
Finally, a "rule D" is read from the SRAM. TCAMs perform high-speed matching based on one clock cycle with a small number of entries. However there are some drawbacks when the number of entries is large, such as network routing. Since the search lines are connected to all entries, large search-line buffers are required, causing large power dissipation. The power dissipation of the search lines is the main portion of the overall power dissipation. In terms of die footprint, the number of transistors in a TCAM cell is 16, while it is 6 in a SRAM cell, resulting in an area inefficient hardware implementation.
[0041) 3. IP LOOKUP BASED ON CLUSTERED NEURAL NETWORK
100421 3.1 IF Lookup Scheme without Wildcards [0043] As noted supra IP lookup engines according to embodiments of the invention are based upon extending the prior art binary CNN, see for example Gripon.
Referring to Figure 2A there is depicted an IP lookup scheme without wildcards (ILS) which provides the functions of a TCAM and a SRAM by storing associations between the IP
addresses and their corresponding rules. There are c input clusters and c' output clusters. Each input cluster consists of 1 neurons and each output cluster consists of /' neurons. As depicted in the example within Figure 2, c = 4 and / =16 are set in the input cluster, while c'= 1 and l'=16 are set in the output cluster. The input address has 16(c . log, I) bits and the output port has 4(c'. log2 /1) bits.
[0044] 3.1.1 Learning Process: In the learning process (also referred to as a storing process), TP addresses and their corresponding rules (also referred to as ports) are stored. Suppose that I
a k -th (15 k 5N) learning address mk is composed Of c -sub-messages m1 ...m, and a k -th learning rule mik is composed of c'-sub-messages miki...m'ke . N is the number of stored addresses. The length of the address is c* log,! bits and that of the rule is c'= log2 P bits. The address is partitioned into c -sub-messages mv (1 5 j 5 c), whose size is K .--log2 / bits. Each sub-message is converted into a /-bit one-hot signal, which activates the corresponding neuron in the input cluster, the / -bit one-hot signal having one of' the 1 bits "1" and the others are "0". The rule is also partitioned into c' -sub-messages mk,A1 5 j' 5 c), whose size is Fe = log2 /' bits. Each sub-message is converted into a P -bit one-hot signal, which activates the corresponding neuron in the output cluster. During the learning process of M messages m1 ...m,, that include input addresses and rules, the corresponding patterns (activated neurons) C(m) are learnt. Depending on these patterns, connections w(,,, JA.4) between irth neuron of j, -th input cluster and i2 -th neuron of j2 -th output cluster are stored according to Equation (1).
1,f C(M)ji = i, ni,,,, X12,i2) 1---- 3 m (Eni{ ) cnli 21 . =..mi 2 (1) m }
0, otherwise *I
where C(M) is a function that maps a message to a neuron.
[0045] This process is called "Global learning". Suppose that M messages are uniformly distributed. An expected density d defined as memory utilization for "Global learning" is given by Equation (2).
1 m , d'=1¨(1 ¨ --) (2) [00461 For example, d'= 0.3 means that stored bits of "1" are 30% of the whole bits in the memory. The density is related to a probability of ambiguity of output rules as described below.
[00471 3.1.2 Retrieving Process: Within the retrieving process, an output neuron (rule) is retrieved using a c * k -bit input messages. The input message me,, is partitioned into c -sub-, messages m1,(1 j c), which are converted into /-bit one-hot signals. In each input cluster, one neuron that corresponds to the 1-bit one-hot signal is activated.
The value of each neuron v(nit.ii Xit < /, ji c) in the input cluster is given by Equation (3) below.
MInj1 = 1 )= {=1 i ' (3) = 0, otherwise [0048] This process is called "Local decoding". Then, values of neurons v(n' i2 j2) in the output cluster, where 411õ. Xi2 <1, j e) is the j2-th neuron of the -th input cluster, are updated using Equation (4).
/-I c WOLi()0242)11(nnJi (4) [0049] In each output neuron, the maximum value vm,õ,h is found and then output neurons are activated using the Equations (5) and (6) respectively.
= max4112,12) (5) If ,J2)= j2 v(re )2) = ti' (6) 0, otherwise [0050] The process described by processes covered by Equations (4) through (6) are called "Global decoding". In the example shown in Figure 2B, the input message is 5.3Ø4. After applying Equation (4), the value of the / -th neuron in the output cluster is 4 and becomes the maximum value. Hence, the rule "1" is retrieved.
[0051] For learnt messages, there may be ambiguity in that more than two neurons (rules) are retrieved in the output cluster after "Global decoding". The probability of ambiguity P b is given by Equation (7).
13õõth =1¨ (1¨ cr. (7) [0052] P.m is calculated based on learnt messages that are uniformly distributed. If the learnt messages are correlated, then the inventors through simulations described below have established that these correlated patterns do not affect Paw, significantly.
[0053] If the number of stored addresses (M) is increased, an input address might activate an output neuron that does not correspond to the input address because of the multiplicity of stored connections.
100541 3.2 IF Lookup Scheme with Wildcards 100551 3.2.1 Learning [00561 As an IP routing table contains wildcards ( X ), the IP lookup scheme is extended to store wildcards in the table. Referring to Figures 3A to 3C there is depicted a learning process according to an embodiment of the invention for an IF lookup scheme with wildcards (ILSW). There are two different connections: wi(, jx,. d..) and w(,idixi2d2)-w'(,ix,..i.) which represent connections between activated neurons in the input clusters, while wo(J242) represents connections between activated neurons in the input and output clusters. In the learning process for W(,1d12i2) 0 11(i2) < 1 : 1 5_ A ( j 2) ... C) depicted in Figure 3A, an address learnt is partitioned into c -sub-messages with size lc = log2 / bits.
If the sub-message is binary information, it is converted into an /-bit one-hot signal, which activates the corresponding neuron in the input cluster. If it is a wildcard, no neuron is activated in the input cluster. The output neurons are activated to store connections using the same, or comparable, algorithm to that employed within the II' lookup scheme without wildcards as depicted in Figure 2. During the learning of M messages M1',...,MAI ' that include only input connections and depending on the corresponding patterns (activated neurons) CH, connections Nox,,,i,) between i -th neuron of I -th input cluster and i' -th neuron of j' -th input cluster are stored based upon Equation (8).
3m e tml. -mill 1 j+l=j' 1, if W(11,11)02,i2)= Om) I = =1 {, C (171) I = . = it (8) 0, otherwise [00571 This process is called "Local learning".
[00581 Figure 3B shows a process of a wildcard replacement for connections between the input and the output clusters W(11, 11)(j2,2) (0 5. i, <l :0 5 i2 <1': 1 5 ji 5 c :15 j2 5 c') wherein dummy neurons are activated when learnt messages include wildcards.
Suppose that the last half of learnt messages have wildcards distributed randomly. If a sub-message is a ' wildcard, the wildcard is replaced by dummy information that is binary one.
The dummy information is determined by a function using the first half of the learnt messages. According to an embodiment of the invention, the function is realized by X0Ring two sub-messages of the first half of learnt messages. The k -th learning sub-messages mki that contain wildcards (X) are replaced as md according to Equation (9).
fm m A,= X
kH) kRAXmod-29 { m and(J > c b) (9) m otherwise [0059] Alternatively, this may be thought of that if a sub-address is a wildcard the wildcard is replaced by a dummy sub-address generated m4 (1 c), where 15_k _5N.
Accordingly, if we suppose that the first ck sub-addresses are known and the last (c ¨ cb) sub-addresses are either known or are wildcards. The dummy sub-address is generated using a function that employs the first ck sub-addresses.
[0060] In the example shown in Figure 3B, the learnt message 1.9.10.X has a wildcard. The wildcard is replaced by X0Ring 9 1 that are the two sub-messages in the first two input clusters, hence the wildcard becomes 8. After making dummy neurons, process (1) is performed by using mdk instead of mk in order to make connections between the input and output clusters and then these connections are stored. For example, the dummy sub-message (sub-address) is converted to an /-bit one-hot signal that activates the corresponding dummy neuron in an input cluster associated with the wildcard. Accordingly, the M
stored messages are now defined by Mõ...,M iv which include the updated input addresses and output rule (poit) and connections between the input and the output activated neurons are stored as shown in Figure 3C and are given by Equation (10).
3M {M, aniciC000 =
- (10) W(ildl)(12,j2) A
andC01)12 = i2 otherwise [0061] 3.2.2 Retrieving [0062] In the retrieving process, the proposed IP lookup scheme with wildcards (ILSW) checks whether input messages m4(1 j SC) are stored or not using stored connections. If an activated neuron corresponding to an input sub-message m in the j, -di input cluster doesn't have a connection to an activated neuron in the precedent input cluster, mi3O can be decided as "non-stored messages". Hence, the activated neuron is de-activated and alternatively a dummy neuron is activated according to the rules in Equations (10) and (11).
This process initially partitions an input message m into c sub-messages which are themselves converted into /-bit one hot signals and hence where an activate neuron corresponding to an input sub-address NI in the jrth input cluster has no connection to an activated neuron in the (j, ¨1) -th input then the cluster NI may be treated as a non-stored message and is not used but rather a dummy sub-messsage is generated according to Equations (10) and (11) respectively. First, the number of connections con j, in the ji -th input cluster is given by Equation (11).
con ji tw ) r (11) omu-i [00631 If con j, is less than (j, ¨1), the input sub-messages are not stored.
Then, the input sub-messages mõ,j, are replaced as wog, by dummy information as determined by Equation (12).
conj, < ji ¨1 ms,41, = {.0 m , (12) Mil-- 2+1 and(j, > eh) minil5otherwise [0064] These rules in Equations (11) and (12) define processes are referred to as "Input selection" or "Input replacement". Then, +mil ) is obtained based on using Equation (3) by using msmil instead of . In the example shown initially in Figure 4A an input message 5.3.10.6 is added with an output rule 5. Subsequently as depicted in Figure 4B
an input message 1.9.10.6 is input. Since the activated neuron "6" in the 4th input cluster doesn't have a connection to the activated neuron "10" in the 3rd input cluster, the activated neuron is de-activated. Instead, a dummy neuron "4" in the 4th input cluster is activated.
[00651 The subsequent process is "Global decoding" based upon exploiting the processes defined in Equations (4) through (6) respectively. As the first-half input clusters have only binary information, the summation of wo jix,amv(nõ j, ) from the first-half ones must be the half of the number of input clusters, if output neurons are a candidate rule.
In the IP lookup scheme with wildcards (ILSW), Equation (4) is re-defined by Equation (13).
1-1 es enal212 = EEwo,,,00,õ,v0õ,,,0 (13) ii-0 ji-i [0066] Accordingly, ena12j2 must be equal to cb if an input address is stored by 4711,i1) being equal to 1. If ena,2,j2 is less than cb the corresponding output neuron is not related to the input address. Hence the summation in Equation (4) is redefined by Equations (14) and (15).
1-1 c sumi2J2 = E E 141(11.)1X12, j2)V(nit,J1) (14) 11.0 c j1.¨+1 s f ena = ¨c 4n1,242). { umi2d2,1 ..., /2 j2 2 0, otherwise (15) [0067] After these processes are executed the processes established by Equations (5) and (6) are executed. Referring to Table 1 the learnt messages as a result of the "Local decoding" and "Global decoding" processes described supra in respect of Figures 3 and 4 are presented showing the IP address, IP address with dummy and the associated rule.
IP Address IP Address with Dummy Rule 5.3Ø6 5.3Ø6 1 1.9.10.12 1.9.10.12 14 1.9.10.X 1.9.10.8 8 .
Table 1: Learnt Messages from Process Depicted in Figures 3 and 4 [00681 3.3 Global Decoding with Max Functions [0069] 3.3.1 Learning [0070] The proposed ILSW described supra in Section 3.2 requires a max function in the Global decoding, which results in large hardware overheads in terms of speed.
The reason for a max function being required is that the maximum value of v(n'12 J2) is varied depending on input messages, where v(n',2 J2) can be up to (c ¨ CO. In the Input replacement, an input sub-. .
, message that is not stored might be wrongly treated as a "stored sub-address", especially when many addresses are stored. In this case, the input sub-address activates the wrong neuron, which is not later replaced by the dummy neuron. Once the wrong neuron is activated in the input cluster, there may not exist a connection to an output candidate.
As a result, the maximum value of v(',212 )would be less than (c ¨ cb) that needs to be detected using the max function.
[0071] To eliminate the max function, the maximum value has to be stable.
Referring to Figures 5A to 5D there is depicted a retrieving process according to an embodiment of the invention exploiting a modified proposed IP lookup scheme with wildcards (MILSW). In the retrieving process, ms,,, which contains dummy sub-addresses is generated using Equations (10) and (11). In addition, additional dummy sub-addresses maõ,(15j c) are generated using the processed defined by Equation (16).
mainj, = ino-co ni in(j¨ch+tXmodcb)A9 (h> c6) (16) m otherwise [0072] In Equation (16) all dummy sub-addresses related to an input address are generated.
Using mso, and main, input neurons and all dummy neurons in the input clusters are activated based on (3) instead of using mo, . In this case, all the stored connections for Global storing relating to the input address are retrieved. Hence the maximum value of v(ri',2 J2) is (c ¨ cb) in Equation (15). The summation and max function are replaced by an AND-OR
function when the maximum value is fixed, see for example the inventors in Ozinawa et al "Clockless Stochastic Decoding of Low-Density Parity-Check Codes: Architecture and Simulation Model" (J. Signal Processing Systems, pp.2523-2526, 2013, hereinafter Ozinawal). As a result the output neuron (',2 2) is given by Equation (17).
v(re 12.12 A./e1=1 v1. (17) [0073I In the example shown in Figures 5A to 5D one additional entry is stored in Table 1 with an input address is 5.3.10.6 and its output port is 5, where cb , is equal to 3. In Figures 5A to 5D the solid lines indicate connections for Local storing and the dashed lines indicate connections for Global storing. When an input address is 1.9.10,6, a neuron "6" in the 4th input cluster is wrongly activated because a connection between the neuron "6"
in the 4th input cluster and a neuron 10" in the 3rd input cluster exists as shown in Figure 5B.
Regardless of the activated neuron "6", a dummy neuron "S" is activated following (16) using two sub-addresses in the first two clusters shown in Figure 5C. Using all activated input neurons including the wrongly activated and the dummy neurons, the output neuron is activated as shown in Figure 5D. In this case, the maximum value of v(n',2 j2) is 4 that is the number of input clusters (c). In contrast, when (12) is used, the maximum value is 3 that cannot be detected using the AND-OR function because the dummy neuron "8" in the 4th cluster is not activated.
[0074] 3.3.2 Probability of Generating Ambiguous Outputs [0075] The MILSW also has a probability of generating ambiguous outputs at each entry similar to that of the ILS in (7). For the probability, an expected density for local storing is described. In local storing, the density is different depending on positions of stored sub-messages because the message lengths excluding wildcards range from (c ¨ck )log2 I to log21 bits. Now suppose the number of sub-messages excluding wildcards are uniformly distributed then the density from the j -th input cluster to the (j +1)-th cluster for Local storing is given by the Equation (18).
)./.,(c-j)/(c-c,+1) d = 1 ¨ (1 ¨ = (18) NON In the MILSW, there are two types of "wrongly" activated neurons in the input clusters from (c ¨ cb) to c. These two types of the activated neurons affect the probability. In the first type related to (12), when a sub-message that is not stored is wrongly treated as a "stored sub-message", the corresponding neuron is wrongly activated. The average number of wrongly activated neurons per input cluster in the first type (oh) is given by Equation (19).
1 ,& 1 col 1.- ________________ kild,(1¨dk +1)) (19) C ¨ cb + 1 j=cb [0077] In the second type related to (16), a dummy neuron is activated even if a correct neuron that is actually stored is activated in the same input cluster. In this case, the dummy neuron is "wrongly" activated. The average number of wrongly activated neurons per input cluster in the second type ( (02) is given by Equation (20).
co2 2: _______________________________________________ (20) c +1 1,4 100781 Hence, the average number of activated neurons per input cluster from c6 to c(c).) as given by Equation (21). As the activated neurons including "wrongly" activated neurons affect the probability (p1) in MILWS, where p, is obtained by modifying (7) to yield Equation (22) where c, is the number of independent activated neurons in the input clusters, which is affected by the function used in (9), (12) and (16).
[0079] 3.4 Ambiguity Analysis [0080] The probability of generating ambiguous outputs at each entry ( Ph.6) is evaluated using a condition of 1=512 , c =16, 1'=1024, and c'=1. Suppose two different ch are used as 4 and 8. The functions of generating dummy sub-addresses in (16) are designed using XOR
functions and are summarized as an example in Table 2. The functions are the same in (9), (12) and (16). As the dummy sub-addresses are generated using the first ch sub-addresses, some functions can be the same in ch = 4. Supposing the number of stored sub-addresses excluding wildcards are uniformly distributed then c, is about 14.3 in the case of ch = 4.
f in ch = 8 fin ch = 4 maw, Min0 M
ma,,,, Mint -ma ,,,2 Min2 Min2 = 4 -ma,õ3 m1113 Min3 Main4 Min4 Mini) (I) Mint 9 M in2 63) M in3 maõ,3 Mint e Min2 (1) in 6.3 e Min0 ma ,,,6 M4n6 Min2 M in3 MMO Mini Min? M,,,3 9 Min Mint (1) Min2 ma,,,, M in e Min0 (3) Mint M in2 maõ,, Mint M in2 e i,,2 Min3 =
maw M in2 Min3 M M M.
1n2 in3 m0 ma,õ11 Min3 fa) Min4 Min3 9 rnino Mint ma ,,,,2 Min4 183) Min5 Min Minl , .
maõ,13 M Min6 triMi MIA2 mama M in6 61) M in7 i,,2 _ maino m ED m ha In8In3 mini) Table 2: Example of Dummy Sub-Message Generation in (16) [0081] Figure 6 shows the probability of ambiguity Pow, versus the number of learnt messages (M) in the IP lookup schemes (1= 512,c =16,/'=1024,c'=1). 1aõ,,6 is the probability that more than two neurons are activated for learnt messages. In this condition, the proposed IP lookup schemes store 144-bit (c *log21) addresses (messages) for IPv6 headers. The maximum length is 36 bits for c6 = 4 and 72 bits for cb =8.
Further when the stored length is 36 bits, the wildcard length is 108 bits.
[0082] Põõ,b without wildcards is defined by Equation (7). iamb with wildcards was evaluated by simulations. Unlike IPv4, since packet traces for the long prefix table are not available to the public and the prefix table is still small, see for example "Border Gateway Protocol (BGP)" (http://bgp.potaroo.net), addresses were chosen randomly for the evaluation. The stored addresses are uniformly distributed. Random-length wildcards appear in the last half of addresses (72 bits). If the range of addresses that have wildcards is changed, the prefix length can be changed.
[0083] It is evident from Figure 6 that Põ,,, is strongly dependent of M.
Within the ff' lookup scheme according to embodiments of the invention with wildcards, if a dummy neuron is the same neuron as that already stored, then both outputs (rules) might be retrieved, which slightly increases Pm,,,, compared with that of the IP lookup scheme without wildcards.
Adding dummy neurons however as can be seen is very effective at lowering P õ, b. This reduction is about five orders of magnitude reduction of that without dummy neurons at M = 78,643. As evident in Figure 5 the IP lookup scheme according to an embodiment of the invention with wildcards can store 100,000 144-bit IP addresses with a negligibly low probability of P..6 (<10' ).
[0084] was also simulated when the learnt messages are correlated. The word length in the IP lookup scheme with wildcards is 64 bits (1 = 256,c = 8,/'=1024,c'=1), The first 8 bits of the learnt messages are selected from 64 fixed patterns of 256 (28). The rest of the learnt , messages are uniformly distributed. Random-length wildcards appear in the last half of addresses (32 bits). At M =10,000 , Pao, using the correlated patterns was 5.30 x le while Poo, using uniformly distributed patterns is 1.69 xle.
[0085] Unlearnt input messages are detected as "mismatch" via a two-step process. In the first step, the number of local connections cono in Equation (10) is checked in "Input selection". If it is not the same as ((c/2)-1), an unlearnt input message can be detected as "mismatch" because all local connections related to the input message are not stored ("Mismatch 1"). If an unlearnt input message is detected as "match" by other stored connections, the number of global connections ena,2,j2 is checked at "Global decoding". Nall ena12,j2 are not the same as (c/2), an unlearnt input message can be detected as "mismatch"
because all global connections between the input message and all output rules are not stored ("Mismatch 2").
[008614. HARDWARE IMPLEMENTATION
[0087] 4.1 Implementation I
[00881 Referring to Figure 7 there is depicted an overall structure 700 of an IP lookup engine according to an embodiment of the invention with wildcards. The learning process is "Local learning" using Equation (8) and "Global learning" as presented in respect of Equations (9) and (1). The retrieving process employed exploits the following process:
1) each input-sub message is replaced by a dummy message if it is not stored ("Input selection") according to Equations (10) and (10;
2) connections between c activated neurons in the input clusters are read from a memory block 1 ("Local decoding") established in dependence of Equation (3); and 3) an output neuron is retrieved based on connections between neurons of the input and the output clusters in a memory block 2 in using processes established by Equations (12) to (14), (5), and (6) respectively ("Global decoding").
[00891 There are ((c ¨1)/2)-bit SRAMs for "Local learning" and c' 11' -bit SRAMs for "Global learning". ln "Local learning", a sub-input k -th learning address m4 and the subsequent one m are converted into one-hot /-bit signals at row and column decoders, respectively. Then, a (w(,1)(1.)) is stored in the memory block 1 if both are not a wildcard. In "Global learning", the last half of an input address is replaced by dummy information using a dummy generator that includes (c/2) sub-dummy generators if each sub-input address is a wildcard. The architecture of a sub-dummy generator being depicted by first circuit 800 in Figure 8. The sub-dummy generator contains 1 2-input XOR gates and multiplexors. Using the sub-input address with dummy information mdkj, and the corresponding rule m'dki2 , a ( wod1x12,j2)) is stored in the memory block 2.
00901 In the retrieving process, an input address mõ, is partitioned into c -sub-messages and ((c ¨ 01) connections ( Ivo jx,,, id are read from the memory block 1.
J4.1) in Equation (10) are selected in a multiplexor of an input-selection module. The input-selection module being depicted by second circuit 850 in Figure 8. Then, the last half of the input address is replaced by dummy information if these corresponding connections are not found.
The output msõ, that contains the first half of the input address and the generated last half of input address is sent to the memory block 2. The one-hot decoder transforms msõ, to v(nõ..0).
In the memory block 2, (c'/') connections ( w(,1.fix,,,i2)) are read by msõ, and are sent to a decoding module shown in Figure 9. The decoding module contains (a) global decoder, c' max-function blocks and c' ambiguity checkers, where c' is set to 1 in Figure 9. In the global decoder, (c/2) 2-input AND gates and (c/2)-input AND gate generate an enable signal to a (c/2)-input adder, where these circuits are corresponding to (12)-(14). There are a /'-input max -function block that decides an activated neuron +242)=1. The ambiguity checker checks that two neurons are activated simultaneously.
100911 4.2 Implementation 2 [0092] Referring to Figure 10 there is depicted an overall structure of another implementation of an IP lookup engine. A memory block for local storing (MLS) stores 4 connections in (8) and one for global storing (MGS) stores connections in (10). These memory modules are designed using SRAMs. A local decoding module in (3) is a one-hot decoder included in the memory blocks. An ambiguity elimination block includes a small TCAM that stores the ambiguous entries in the ILSW (MILSW), wherein it should be noted that the ambiguous entry generates more than one output port. If the ILSW
(MILSW) retrieves multiple output ports, the ambiguous entry is matched to an input search address. In this case, the output of the IP lookup engine is selected from the ambiguity elimination block in an output selector. Otherwise, it is selected from the ILSW (MILSW). The ILSW takes 2 clock cycles and the MILSW takes 3 clock cycles for the retrieving process.
The ambiguity elimination block takes 2 clock cycles.
[0093] Figure 11 shows the MLS contains (c ¨ 1)12-bit sub-memory blocks and the MGS
contains c * c' //' -bit sub-memory blocks. Both the ILSW and the MILSW use the same memory block. In the storing process, suppose that the stored connections are preliminarily generated in an external processing unit (e.g. a central processing unit (CPU) or microprocessor). In Local storing, / bits of co' are serially sent from the CPU and are stored in the SRAM shown in Figure 11A, where it takes at least / clock cycles to store all co'(,..aem depending on the number of inputs / outputs (I/0s) of the implemented semiconductor circuit. In Global storing, it also takes at least / clock cycles to store all 01,j1)02,j2) [0094] In the retrieving process for the MLS, an input address mi,, is partitioned into c sub-addresses and the corresponding connections are read in (11). Figure 12A
depicts a circuit diagram of the input-replacement module based on the ILSW. The updated input address ( ms,õ ) is generated using the stored connections read from the MLS in (12) at the first clock cycle. At the second clock cycle, a flip-flop is enabled to store msõ,j, and transfers it to the MGS. Figure 12B depicts a circuit diagram of the dummy generator for the MILSW.
Accordingly, maw, is generated before ms,, in (16) at the first clock cycle and is transferred to the MGS using the same path of ms,1 at the second clock cycle. At the 3rd clock cycle, msõ,31 is transferred to the MGS. Hence, CO(i1..11)0242) are read twice from the MGS using maItyl and then MSmil =
[0095] Now referring to Figure 13A there is depicted the decoding module based on the ILSW which operates at the 2nd clock cycle. Using the connections read from the MGS, (13), (14) and (15) are calculated using a cb -input AND gate and a (c ¨ cb ) -input adder. Then, only activated output neuron or neurons are selected using a max function in (5) and (6).
Figure 13B depicts the corresponding decoding module based on the MILSW that operates at the 2nd and the 3rd clock cycles. As 0old1xi2i2) is read twice from the MGS, the word selected by mamil is stored in registers and then is ORed with the word selected by msJ, .
[0096] Figure 14A depicts a circuit diagram of the ambiguity elimination block. This block is identical for both the ILSW and the MILSW and consists of q TCAM words (e.g. q = 20) that contain the ambiguous entries ( me). The value of q is larger than or equal to the maximum number of ambiguous entries. In the storing process, suppose that me and the corresponding output ports (m'c) are sent from a CPU and are stored in the TCAM and registers, respectively. In the retrieving process, TCAM and registers, respectively. In the retrieving process, min is searched in the TCAM and a matched word is found when the ILSW (MILSW) generates multiple output ports. The matched word selects its corresponding port from the registers through a one-hot encoder and a multiplexer and then m, is transferred to an output selector shown in Figure 14B. The signal (mismatch) is low when the matched word is found in the TCAM and high when it is not found. If the matched word is found, meu, is selected as an output port in the output selector. Otherwise, the output port is selected from the global decoding module.
(009715. EVALUATION
[0098] 5.1. Number of Ambiguous Entries [0099] Depicted in Figure 15 are the average ( Nemb ) and the maximum number (max(Nemb )) of the ambiguous entries versus the number of stored addresses (N) in the ILSW
and the MILSW. Again it is noted that an ambiguous entry activates more than one output neuron.
The same parameters as employed in Figure 7 were used, where cb = 8. These results are obtained using simulations, where each simulation point uses 12,000 trials to calculate Nemb , and max(Neõ,b ) Noõ,b increases with increasing N because it increases the density. The ILWS has lower Nam?, than that of the MILWS. The reason for this being that the MILWS
may "wrongly" activate additional dummy neurons in (16).
[00100] Referring to Figure 16 the max(Nõ,) versus N is plotted when stored addresses are correlated. PcoR is the number of correlated bits divided by the total number of bits at the first two sub-addresses expressed as a percentage. The simulation conditions are the same as the previous simulation. A high Pc011 increases the number of shared connections among stored entries. max(N) increases as the number of shared connections is increased.
[00101] 5.2 Hardware Results and Performance Comparisons of Embodiments of Invention [00102] The proposed IP lookup engine described in respect of Section 4.2 Implementation 2 and Figures 10 to 14 respectively was designed based upon the Taiwan Semiconductor Manufacturing Company Ltd. (TSMC) '65rim CMOS technology. The MLS
and the MGS both exploit 15 SRAM blocks (256kb) and 32 SRAM blocks (256kb), respectively. The small TCAM in the compensation block has q =20 entries. For the purpose of comparison, a reference TCAM was also designed. The TCAM cell is designed using a NAND-type cell that consists of 16 transistors, as per Pagiamtzis et al in "Content-Addressable Memory (CAM) Circuits and Architectures: A Tutorial and Survey"
(IEEE J.
Solid State Circuits, Vol. 41, No. 3, pp.712-727). Each entry has 144 TCAM
cells and is designed based on a hierarchy design style for high-speed matching operations, see for example Hanzawa et al in "A Large-Scale and Low-Power CAM Architecture featuring a One-Hotspot Block Code for IP-Address Lookup in a Network Router" (IEEE J.
Solid State Circuits, Vol. 40, No. 4, pp.853-861).
[00103] Referring to Table III performance comparisons under HSPICE
simulation of the 11.,SW and MILSW with the reference TCAM design and that of a previous design embodiment of the inventors are presented, see Onizawa et al "Low-Power Area-Efficient Large-Scale IP Lookup Engine based on Binary Weighted Clustered Networks"
(Proc. 50th IEEE Design Automation Conference, 2013, hereinafter Ozinawa2). The reference TCAM is designed to store 100,000 144-bit entries and is divided into 20 sub-TCAMs that each have 5,000 entries in order to achieve a power reduction for the search lines. A
priority encoder attached to the TCAM has 100,000 inputs and 17-bit outputs.
[00104] For storing process, the previous implementation of the inventors, see Ozinawa2, and the IP lookup engines according to embodiments of' the invention 1= 512 clock cycles to store all tables in the MLS and the MGS. The previous method has the probability of generating ambiguous output ports (<10' )., The proposed methods according to embodiments of the invention remove the probability using the small TCAM.
As the small TCAM can compensate up to q = 20 error entries, N is increased by 83.5% and 70.0%
based on the ILSW and the MILSW, respectively compared to the previous method.
[00105] For the retrieving process, in the 1LSW, the worst-case delay is 1.31 ns in the block that includes the max-function block. This delay is 89.1% of the previous method (Ozinawa2) that includes an ambiguity checker after Global decoding. The delay of the max-function block is 65.8 % of the whole delay. In the MILWS, as the max-function block is removed, the worst-case delay is 0.62 ns. As throughput may be defined by (address length) /
(worst-case delay) / (retrieving clock cycles) the MILSW offers increased throughput compared to the previous method (Ozinawa2) and the ILSW.
[001061 However, the dynamic power dissipation of the MILSW is increased compared to that of the ILSW because the MILSW reads connections twice from the MGS.
However, the energy dissipations of the 1LSW and the MILSW are 2.7% and 4.8%
of that of the reference TCAM which is significant. The main reason of the energy reduction is the use of SRAMs instead of the power-hungry TCAM based on the brute-force search. A
lookup speed of the ILSW and the MILSW can be 229 Gb/s and 323 Gb/s over 40 Gb/s (0C-768) where the packet size is supposed to be 75 bytes. In terms of die footprint a further reduction is achieved as each TCAM cell contains 16 transistors while each SRAM cell contains 6 transistors. Accordingly, the required memory size of a CMOS implementation of a circuit operating according to an embodiment of the invention is 11.75 Mb, which 30.6 % of the equivalent area of the reference TCAM design.
Reference Ozinawa2 ILSW MILSW
TCAM
Number of Tables 100,000 100,000 183,500 170,000 Throughput (Gbps) 52.0 48.3 54.8 77.7 Dynamic Power (W) 3.030 0.140 0.156 0 363 Static Power (W) 0.240 0.090 0.090 0.090 Energy Metric (fait/search) 0.584 0.028 0.016 0.028 Probability of Generating 10-8 Ambiguous Outputs q (number of entries in TCAM) 0 20 20 Memory (Mb) 14.4 11.75 (SRAM) (TCAM) Equivalent Size (SRAM) (Mb) 38A 11.75 Number of Transistors 256M 77M
Table 3: Performance Comparisons [00107] 5.3 Performance Comparison Relative to Prior Art [00108] Referring to Table 4 there are presented performance comparisons of embodiments of the invention with related works within the prior art. The design of Gamache is a straightforward implementation using TCAMs whilst Hayashi et al in "A 250-Mb Full Ternary CAM with Low-Voltage Matchline Sensing Scheme in 65-nm CMOS"
(IEEE J. Solid State Circuits, Vol. 48, No. 11, pp. 2671-2680) requires a very large (18Mb) memory implementation under a 65nm CMOS technology. In contrast Noda employs eDRAMs to reduce the size of TCAM cells for low power dissipation, however this tends to be a complex process. In Maurya several entries are shared using special-purpose CAM cells to reduce the number of entries required whilst Kuroda realizes the prefix match by reading candidates from eDRAMs, thereby yielding an energy metric which is very small.
However, as the memory size is 0(2") where n is the word length, this leads to an unacceptably large memory of 1,039 Mb for long words (e.g. 144 bits). The trie-based method of Bando (PC
trie-4) realizes a memory-efficient IP lookup engine using a prefix-compressed trie and also uses a hash function to reduce memory accesses to off-chip memory in order to achieve high throughput. Hasan exploits a hash-based method which reduces power dissipation using a collision-free hash function compared with the TCAM in Gamache. Compared with these methods, the IP lookup engines ILSW and MILSW according to an embodiments of the invention realize low energy metrics while dealing with large number of long entries and also achieving high throughout and small die footprint through a reasonable memory size.
E001091 It would be evident to one skilled in the art that small die footprints equate to reduced die costs thereby reducing the cost of an IP lookup engine according to an embodiment of the invention. Beneficially low cost TCAMs and IP lookup engines implemented according to embodiments of the invention would therefore not only allow for their deployment within a variety of other applications where to date they have not been feasible due to cost but also others where their deployment had not been previously considered. For example, low cost TCAMs would enable routers to perform additional functions beyond address lookups, including, but not limited to, virus detection and intrusion detection.
TCAM TCAM DTCA IPCAM eDRA Trie Hash MILSW
Length 512 72 144 32 23 63 32 144 (bits) (128) A
(Note _ 1) No. of 21,504 262,144 32368 65,536 16x106 318,043 524,288 Entries (Note 170,000 2) Throughput 76.8 18 20.6 32 4.6 12.6 64 77.7 (Gbps) 12.26 9.6 2.0 7.33 0.6 --- 5.5 0.363 Energy 5.53 1.98 2.96 0.159 0.007 ¨ 1.64 0.028 Metric Memory 10.5 18 4.5 2 432 31.19 60 11.75 (Mb) - =
Equiv. Size 28 48 ¨ 7.33 ¨ --- ---SRAM
(Mb) Equiv. Size 7.88 96 4.5 32.99 i039 11.75 for 144-bit Length (Mb) Technology 130 65 130 65 40 FPGA 130 65 (nm) Table 4: Performance Comparison of Embodiment of the Invention with Prior Art Note 1: Method can be extended to 128 bits for IPv6 Note 2: 1.38M ¨ IPCAM word is approximately equivalent to 22 TCAM words.
Note 3: TCAM I ¨ Gamache, TCAM2 ¨ Hayashi, DTCAM ¨ Noda, IPCAM Maurya, EDRAM ¨ Kuroda, Trie ¨ Bando, Hash - Hasan 1001101 Specific details are given in the above description to provide a thorough understanding of the embodiments. However, it is understood that the embodiments may be practiced without these specific details. For example, circuits may be shown in block diagrams in order not to obscure the embodiments in unnecessary detail. In other instances, well-known circuits, processes, algorithms, structures, and techniques may be shown without unnecessary detail in order to avoid obscuring the embodiments.
[00111] In addition to the IP lookup search engines and context driven search engines discussed supra other applications of embodiments of the invention include, but are no limited, CPU fully associative cache controllers and translation lookaside buffers, database search engines, database engines, data compression, artificial neural networks, and electronic intrusion prevention system.
1001121 Implementation of the techniques, blocks, steps and means described above may be done in various ways. For example, these techniques, blocks, steps and means may be implemented in hardware, software, or a combination thereof. For a hardware implementation, the processing units may be implemented within one or more application specific integrated circuits (ASICs), digital signal processors (DSPs), digital signal processing devices (DSPDs), programmable logic devices (PLDs), field programmable gate arrays (FPGAs), processors, controllers, micro-controllers, microprocessors, other electronic units designed to perform the functions described above and/or a combination thereof.
[00113] Also, it is noted that the embodiments may be described as a process which is depicted as a flowchart, a flow diagram, a data flow diagram, a structure diagram, or a block diagram. Although a flowchart may describe the operations as a sequential process, many of the operations can be performed in parallel or concurrently. In addition, the order of the operations may be rearranged. A process is terminated when its operations are completed, but could have additional steps not included in the figure. A process may correspond to a method, a function, a procedure, a subroutine, a subprogram, etc. When a process corresponds to a function, its termination corresponds to a return of the function to the calling function or the main function.
1001141 Furthermore, embodiments may be implemented by hardware, software, scripting languages, firmware, middleware, microcode, hardware description languages and/or any combination thereof. When implemented in software, firmware, middleware, scripting language and/or microcode, the program code or code segments to perform the necessary tasks may be stored in a machine readable medium, such as a storage medium. A
code segment or machine-executable instruction may represent a procedure, a function, a subprogram, a program, a routine, a subroutine, a module, a software package, a script, a class, or any combination of instructions, data structures and/or program statements. A code segment may be coupled to another code segment or a hardware circuit by passing and/or receiving information, data, arguments, parameters and/or memory contents.
Information, arguments, parameters, data, etc. may be passed, forwarded, or transmitted via any suitable means including memory sharing, message passing, token passing, network transmission, etc.
[00115] For a firmware and/or software implementation, the methodologies may be implemented with modules (e.g., procedures, functions, and so on) that perform the functions described herein. Any machine-readable medium tangibly embodying instructions may be used in implementing the methodologies described herein. For example, software codes may be stored in a memory. Memory may be implemented within the processor or external to the processor and may vary in implementation where the memory is employed in storing software codes for subsequent execution to that when the memory is employed in executing the software codes. As used herein the term "memory" refers to any type of long term, short term, volatile, nonvolatile, or other storage medium and is not to be limited to any particular type of memory or number of memories, or type of media upon which memory is stored.
[00116] Moreover, as disclosed herein, the term "storage medium" may represent one or more devices for storing data, including read only memory (ROM), random access memory (RAM), magnetic RAM, core memory, magnetic disk storage mediums, optical storage mediums, flash memory devices and/or other machine readable mediums for storing information. The term "machine-readable medium" includes, but is not limited to portable or fixed storage devices, optical storage devices, wireless channels and/or various other mediums capable of storing, containing or carrying instruction(s) and/or data.
[00117] The methodologies described herein are,., in one or more embodiments, performable by a machine which includes one or more processors that accept code segments containing instructions. For any of the methods described herein, when the=
instructions are executed by the machine, the machine performs the method. Any machine capable of executing a set of instructions (sequential or otherwise) that specify actions to be taken by that machine are included. Thus, a typical machine may be exemplified by a typical processing system that includes one or more processors. Each processor may include one or more of a CPU, a graphics-processing unit, and a programmable DSP unit. The processing system further may include a memory subsystem including main RAM and/or, a static RAM, and/or ROM. A bus subsystem may be included for communicating between the components.
If the processing system requires a display, such a display may be included, e.g., a liquid crystal display (LCD). If manual data entry is required, the processing system also includes an input device such as one or more of an alphanumeric input unit such as a keyboard, a pointing control device such as a mouse, and so forth.
[001181 The memory includes machine-readable code segments (e.g. software or software code) including instructions for performing, when executed by the processing system, one of more of the methods described herein. The software may reside entirely in the memory, or may also reside, completely or at least partially, within the RAM and/or within the processor during execution thereof by the computer system. Thus, the memory and the processor also constitute a system comprising machine-readable code.
[001191 In alternative embodiments, the machine operates as a standalone device or may be connected, e.g., networked to other machines, in a networked deployment, the machine may operate in the capacity of a server or a client machine in server-client network environment, or as a peer machine in a peer-to-peer or distributed network environment. The machine may be, for example, a computer, a server, a cluster of servers, a cluster of computers, a web appliance, a distributed computing environment, a cloud computing environment, or any machine capable of executing a set of instructions (sequential or otherwise) that specify actions to be taken by that machine. The term "machine" may also be taken to include any collection of machines that individually or jointly execute a set (or multiple sets) of instructions to perform any one or more of the methodologies discussed herein.
1001201 The foregoing disclosure of the exemplary embodiments of the present invention has been presented for purposes of illustration and description. It is not intended to be exhaustive or to limit the invention to the precise forms disclosed. Many variations and modifications of the embodiments described herein will be apparent to one of ordinary skill in the art in light of the above disclosure. The scope of the invention is to be defined only by the claims appended hereto, and by their equivalents.
1001211 Further, in describing representative embodiments of the present invention, the specification may have presented the method and/or process of the present invention as a particular sequence of steps. However, to the extent that the method or process does not rely on the particular order of steps set forth herein, the method or process should not be limited to the particular sequence of steps described. As one of ordinary skill in the art would appreciate, other sequences of steps may be possible. ,Therefore, the particular order of the steps set forth in the specification should not be construed as limitations on the claims. In addition, the claims directed to the method and/or process of the present invention should not be limited to the performance of their steps in the order written, and one skilled in the art can readily appreciate that the sequences may be varied and still remain within the spirit and scope of the present invention.
1. A device comprising;
a clustered neural network processing algorithms storing ternary data.
2. The device according to claim 1 wherein;
the ternary data comprises data having values of either 0, 1, or don't care.
3. The device according to claim 1;
wherein the device only stores data as binary weighted connections between clusters of the clustered neural network.
input data to the device comprises a network address of a plurality of network addresses according to a predetermined standard, each network address relating to a destination of a packet of data received at a system comprising at least the device; and output data from the device comprises a rule for routing the packet of data;
wherein the plurality of addresses and their associated rules are stored as associations within the device without the requirement for an additional rule specific memory.
a first plurality of input clusters forming a first predetermined portion of a clustered neural network, each input cluster comprising of a first predetermined number of input neurons;
and a second plurality of output clusters forming a second predetermined portion of the clustered neural network, each output cluster comprising a second predetermined number of output neurons; wherein, the clustered neural network stores a plurality of network addresses and routing rules relating to the network addresses as associations.
6. The device according to claim 5 wherein, the clustered neural network operates using ternary data, the ternary data comprising data having values of either 0, 1, or don't care.
8. A method comprising;
9. The method according to claim 8 wherein, providing the address lookup engine comprises:
providing a first plurality of input clusters forming a first predetermined portion of the clustered neural network, each input cluster comprising of a first predetermined number of input neurons; and providing a second plurality of output clusters forming a second predetermined portion of the clustered neural network, each output cluster comprising a second predetermined number of output neurons; wherein, the clustered neural network stores a plurality of network addresses and routing rules relating to the network addresses as associations.
CA 2842555 2013-02-07 2014-02-07 Methods and systems for network address lookup engines Abandoned CA2842555A1 (en)
CA 2842555 Abandoned CA2842555A1 (en) 2013-02-07 2014-02-07 Methods and systems for network address lookup engines
US8316124B1 (en) 2008-09-29 2012-11-20 Amazon Technologies, Inc. Managing network data display
US7865594B1 (en) 2008-09-29 2011-01-04 Amazon Technologies, Inc. Managing resources consolidation configurations
US7930393B1 (en) 2008-09-29 2011-04-19 Amazon Technologies, Inc. Monitoring domain allocation performance
US8117306B1 (en) 2008-09-29 2012-02-14 Amazon Technologies, Inc. Optimizing content management
US9343185B2 (en) * 2013-09-26 2016-05-17 International Business Machines Corporation Electronic circuit for fitting a virtual address range to a physical memory containing faulty address
US10027739B1 (en) 2014-12-16 2018-07-17 Amazon Technologies, Inc. Performance-based content delivery
US10225365B1 (en) 2014-12-19 2019-03-05 Amazon Technologies, Inc. Machine learning based content delivery
US10311372B1 (en) * 2014-12-19 2019-06-04 Amazon Technologies, Inc. Machine learning based content delivery
US10225326B1 (en) 2015-03-23 2019-03-05 Amazon Technologies, Inc. Point of presence based data uploading
US7191178B1 (en) * 2002-02-11 2007-03-13 Louisiana Tech University Research Foundation Method for allocation of web pages using neural networks
US7707217B2 (en) * 2005-01-24 2010-04-27 3Com Corporation Trie search engines and ternary CAM used as pre-classifier
McAuley et al. 1993 Fast routing table lookup using CAMs
Dharmapurikar et al. 2005 Fast and scalable pattern matching for content filtering
Liu 2002 Efficient Mapping of Range Classifier into Ternary-CAM.
US20140215478A1 (en) 2014-07-31 Work migration in a processor
US6985483B2 (en) 2006-01-10 Methods and systems for fast packet forwarding
US7581059B2 (en) 2009-08-25 Controlling a searchable range within a network search engine
US20060101195A1 (en) 2006-05-11 Layered memory architecture for deterministic finite automaton based string matching useful in network intrusion detection and prevention systems and apparatuses
Wang et al. 2012 Scalable name lookup in NDN using effective name component encoding
US8571023B2 (en) 2013-10-29 Methods and Apparatus Related to Packet Classification Based on Range Values
So et al. 2013 Named data networking on a router: Fast and DoS-resistant forwarding with hash tables
Liu 2002 Routing table compaction in ternary CAM
US20040240484A1 (en) 2004-12-02 Transposing of bits in input data to form a comparand within a content addressable memory
Ravikumar et al. 2005 EaseCAM: An energy and storage efficient TCAM-based router architecture for IP lookup
Baboescu et al. 2005 A tree based router search engine architecture with single port memories
US7019674B2 (en) 2006-03-28 Content-based information retrieval architecture
Lu et al. 2006 A memory-efficient parallel string matching architecture for high-speed intrusion detection
US8880554B2 (en) 2014-11-04 Method and apparatus for high performance, updatable, and deterministic hash table for network equipment
JP5529976B2 (en) 2014-06-25 Systolic Array Architecture for fast ip lookup
US7606968B2 (en) 2009-10-20 Multi-level content addressable memory
Song et al. 2008 A memory efficient multiple pattern matching architecture for network security
Varvello et al. 2012 Caesar: A content router for high speed forwarding
US20120275466A1 (en) 2012-11-01 System and method for classifying packets
Yu et al. 2009 BUFFALO: Bloom filter forwarding architecture for large organizations
US20100083345A1 (en) 2010-04-01 Methods and apparatus related to packet classification associated with a multi-stage switch
Song et al. 2009 Ipv6 lookups using distributed and load balanced bloom filters for 100gbps core router line cards

redpajama_set_name: RedPajamaCommonCrawl


text:
//
//  AppConstants.h
//  PaySay
//
//  Created by Pradeep Narendra on 6/5/16.
//  Copyright © 2016 Pradeep. All rights reserved.
//

#ifndef AppConstants_h
#define AppConstants_h

// Enum to identify Status
typedef NS_ENUM(NSInteger, DashboardStatus) {
    kNotCompleted = 1,
    kCompleted
};

// Enum to identify Tasks Status
typedef NS_ENUM(NSInteger, TasksStatus) {
    kTaskToStart = 1,
    kTaskOnTrack,
    kTaskDelayed,
    kTaskCompleted
};

// Enum to identify Phase
typedef NS_ENUM(NSInteger, PhaseType) {
    kFirstPhase = 1,
    kSecondPhase,
    kIRSDCType
};

/******** access token key *********/
#define ACCESS_TOKEN @"accessToken"

#define kDeviceToken @"kDevicePushToken"

#define RGBACOLOR(r,g,b,a) [UIColor colorWithRed:(r)/255.0f green:(g)/255.0f blue:(b)/255.0f alpha:(a)]

#define OS_VERSION_EQUALS_OR_AFTER(version) [[[UIDevice currentDevice].systemVersion componentsSeparatedByString:@"."][0] intValue] >= version

#define OS_VERSION_BEFORE(version) [[[UIDevice currentDevice].systemVersion componentsSeparatedByString:@"."][0] intValue] < version

#define CLIENT_KEY @"CRDNwxmwHj688CuVjLEcq7ZudupVUIbke2Jflda7"
#define CLIENT_SECRET @"rbkopL6SLTPbmoEAViDglnwPQdVv4aC62UC6vxC16PiA4HIT5wY9nfgttRSiZgVEOZY7zfxfUk1tLNATq3i9Itbmuwb7sHK8gBC5epLxNqCIju6zYE6eS4MEFAbCZGjc"

static NSString *const kUsernameKey = @"username";
static NSString *const kGrantTypeKey = @"grant_type";
static NSString *const kClientIdKey = @"client_id";
static NSString *const kClientSecretKey = @"client_secret";

static NSString *const kEmailKey = @"email";
static NSString *const kPasswordKey = @"password";
static NSString *const kStationName = @"stationName";
static NSString *const kDesignation = @"designation";
static NSString *const kFirstName = @"firstName";
static NSString *const kLastName = @"lastName";
static NSString *const kIRSDC = @"irsdc";

static NSString *const kAuthKey = @"authKey";
static NSString *const kMessageKey = @"message";
static NSString *const kMessageIDKey = @"messageId";
static NSString *const kStationIdKey = @"stationId";
static NSString *const kTaskIdKey = @"taskId";

static NSString *const kStationSubActivityIdKey = @"stationSubActivityId";
static NSString *const kStationRemarksIdKey = @"remarksId";
static NSString *const kStatusKey = @"status";

static NSString *const kImagesKey = @"images";
static NSString *const kRemarks = @"remarks";
static NSString *const kNameKey = @"name";
static NSString *const kPhoneNumberKey = @"phone_number";

static NSString *const kRegistraionId = @"registration_id";

static NSString *const kOtp = @"otp";

static NSString *const kAmountKey = @"amount";
static NSString *const kBillNumberKey = @"bill_number";
static NSString *const kBasketKey = @"basket";
static NSString *const kUseRewardsKey = @"use_rewards";

static NSString *const kService = @"service";
static NSString *const kRechargeNumber = @"recharge_number";
static NSString *const kOperatorCode = @"operator_code";

static NSInteger kBubbleRadius  = 6.f;

static NSInteger kTableCellHeight = 48.0f;

static NSInteger kTableSectionCellHeight = 50.0f;

// User defaults keys
static NSString *const kSelectedStationIndex = @"SelectedStationIndex";
static NSString *const kSelectedDesignationIndex = @"SelectedDesignationIndex";
static NSString *const kRemeberMeKey = @"RememberMeKey";

static NSString *const kStationInfoSegueIdentifier = @"StationInfoSegue";
static NSString *const kSubTaskHeaderViewNibName = @"SubActivitiesHeaderView";
static NSString *const kSubTasksCellIdentifier = @"SubTasksCellIdentifier";
static NSString *const kSubStreamStatusCellIdentifier = @"subStreamStatusCellIdentifier";
static NSString *const kQueriesResponseSegueIdentifier = @"QueriesResponseSegue";

// Proxima nova bold
static NSString *const kProximaNovaSemibold = @"ProximaNova-Semibold";
static NSString *const kProximaNovaBold = @"ProximaNova-Bold";
static NSString *const kProximaNovaLight = @"ProximaNova-Light";
static NSString *const kProximaNovaRegular = @"ProximaNova-Regular";

#endif /* AppConstants_h */


Our comprehensive Mollichaff range offers a choice of high quality chaffs to add bulk and fibre to your horse's diet, as well as a complete feed aimed at laminitics and a complete forage replacer aimed at veterans.
Our specialist chaff range has five tasty options and is made from top quality oat and wheat straws, alfalfa and dried grass. It is dust-extracted, chopped and lightly dressed with a unique low sugar coating, using a special process that covers every part of the chaff evenly to make it very palatable.
This gives our chaffs an open texture, unlike heavily molassed chaffs which can be sticky and lumpy.
A high quality chaff with the addition of real apple pieces and apple essence.
Made from the highest quality straw - chopped and dust extracted.
Contains a unique, low sugar dressing.
Mollichaff Calmer is a highly palatable, complete fibre feed designed for horses and ponies prone to nervousness or excitability. It contains a balanced blend of fibre pellets, oat straw, dried grass, herbs, soya oil, vitamins, minerals, limestone and trace elements. Along with a carefully formulated combination of camomile, lemon balm and mint, Mollichaff Calmer supplies elevated levels of magnesium, as a diet deficient in magnesium can result in increased muscle contraction, making the horse less able to relax and more likely to become excitable or 'fizzy'.
Mollichaff Donkey is a highly palatable mix containing a balanced blend of fibre pellets, oat straw, and soya oil with camomile, mint and lemon balm. It also contains a broad spectrum vitamin and mineral supplement, which includes limestone and magnesium. Magnesium is often deficient in UK soils and is an important factor in the nutritional support of many metabolic processes in the donkey as well as helping to maintain a healthy nervous system. Deficiency in this mineral may be associated with glucose intolerance and insulin resistance, both of which are important in the nutritional management of laminitis.
Limestone provides additional calcium for strong bones and healthy growth.
Mollichaff Donkey is low in sugar, starch and energy and carries the HoofKind logo to denote that it is suitable for laminitic donkeys, mules, horses or ponies.
When Mollichaff Donkey is fed at the recommended levels, it needs no further supplementation other than good quality forage, or it can be used as a total forage replacer. At least 1.5% of bodyweight should be fed in total food per day, including forage, even to overweight donkeys.
HoofKind is a highly palatable mix containing a balanced blend of oat straw, alfalfa, fibre pellets, soya oil, vitamins, minerals, trace elements, antioxidants and therapeutic levels of biotin.
HoofKind is low in starch and sugar, high in fibre and does not contain any cereals.
HoofKind provides a low level but high quality protein and restricted calories and so provides limited, controlled energy from high quality digestible fibre and oil-based ingredients, making it an excellent feed for 'fizzy' horses and good doers, as well as laminitics.
HoofKind contains a broad spectrum vitamin and mineral supplement, and when fed at the recommended levels to horses at rest or in light work, HoofKind needs no further supplementation other than good quality forage such as High Fibre or Timothy HorseHage.
HoofKind contains additional therapeutic levels of biotin. Independent, scientific studies have found that supplementing an average horse's diet with 15mg of biotin per day can greatly increase both the growth rate and the hardness of the hoof. Mollichaff HoofKind has been specifically formulated to ensure that these levels are met. For an average 500kg horse, feeding the required 2.5kg per day will provide the required 15mg of biotin.
HoofKind contains added magnesium. Magnesium is often deficient in UK soils and is an important factor in the nutritional support of many metabolic processes in the horse. Deficiency may be associated with glucose intolerance and insulin resistance, both of which are important in the nutritional management of laminitis. Magnesium also plays an important role in maintaining a healthy nervous system, and may help in the nutritional support of anxious or "spooky" horses.
Additional natural plant-based antioxidants are also included in HoofKind. Antioxidants help mop-up free radicals and assist in the nutritional support of prevention of damage to cells and cell membranes. The antioxidants in HoofKind have been specially selected for the nutritional maintenance of the immune system, the respiratory system, the circulatory system and the all-important hooves and laminae.
Contains a unique coating, combining high levels of soya oil with a low sugar dressing, to give a bloom to the coat and added condition.
Mollichaff Veteran contains added limestone to provide additional calcium for strong bones. Salt provides two important electrolytes – sodium and chloride. Also contains added limestone to provide additional calcium.
For guidance on how much to feed, please contact us for a ration suggestion based upon your horse or pony's individual needs.
Veteran contains only natural ingredients.
A high quality chaff combining straw and a low sugar dressing with the addition of calcium.
Made from the highest quality wheat straw - chopped and dust extracted.
Contains a unique, low sugar coating.
A high quality chaff made from the best oat straw with the addition of a variety of herbs found in the horse's natural environment.
Contains a balanced mixture of Garlic, Mint, Rosemary and Golden Rod. Garlic helps to maintain healthy respiratory and digestive systems as well as being a natural fly repellent.
Mint improves palatability, and again helps maintain healthy respiratory and digestive systems.
Rosemary aids digestion and stimulates appetite. Golden Rod also stimulates appetite and helps maintain a healthy skin and coat.
Has a unique, low sugar dressing.


text:
News / Metro
Friendship association elects new chairman
Yang Meiping
Sha Hailin has been elected chairman of the Shanghai People's Association for Friendship with Foreign Countries.
Sha Hailin, vice chairman of the standing committee of Shanghai People's Congress and former Chinese ambassador to the Republic of Ireland, was elected new chairman of the Shanghai People's Association for Friendship with Foreign Countries on Saturday.
The association also elected its new board of directors on Saturday.
Founded in September 1956, the Shanghai People's Association for Friendship with Foreign Countries has made great achievements in enhancing mutual understanding and friendship between Shanghai and the peoples of other countries.
The new board pledged to keep expanding and deepening Shanghai's foreign exchanges with the rest of the world.
Source: SHINE Editor: Yang Meiping
Over 600 notices served as garbage sorting regulations take effect
Disposable items alert for restaurants
Theater academy celebrates the founding of the Communist Party
Orchestra academy celebrates 5th anniversary
Garbage sorting made easy
Graduates have designs on the future
New move to attract talent to Pudong
Interactive play performed at Mao's Shanghai home
AI system listens to patients' concerns
Archives tell Party's story


Residents of coastal Southern California are increasingly making the decision to move away to find affordable housing — a trend many economists blame on a housing shortage driving rents and home prices sharply higher during the economic recovery.
One couple wanted to stay in the area but couldn't find a house they both liked and could reasonably afford — despite a dual income of around $150,000. Sounds like a healthy income to me.
To escape high prices, people — often younger and with lower- or middle-class incomes — are looking toward the Inland Empire and nearby states for additional square footage and a lower mortgage payment. It is just too expensive to live in California.
"[Migration] is settling back into longer-term patterns," said Jed Kolko, chief economist with employment website Indeed.com who analyzed the data.
In 2016, about 75,000 more people left Los Angeles County than moved here from other places in the United States, the data show. That rate of "negative domestic migration" is 21% more than a year earlier, and nearly double the level seen in 2012 when moves away from the county had bottomed out.
A similar trend exists in Orange County, where the median hom price of $645,000 is higher than the peak last decade, a level not yet hit in L.A. County.
But as young people leave, some businesses and economists are becoming concerned.
"How do we grow our economy when we can't recruit the workers who can come here and have a decent quality of life?" Levine said.
It's a problem that extends beyond Southern California.
If affordability doesn't improve, lower- and middle-income households will increasingly leave California.
Whatever your home size goal you can get more house and better communities in the Phoenix area. You can find the home of your dreams here. Phoenix is affordable.


Abu Dhabi-UAE National Reference Laboratory (NRL), a Mubadala Investment company, and Manzil Healthcare Services (Manzil), a leading provider of professional, individualized homecare and rehabilitation services based in Abu Dhabi, have signed two agreements aimed at supporting the growing demand for personalized home healthcare in the UAE.
As part of the collaboration, NRL will provide high quality laboratory services for Manzil patients, while Manzil will supply specialized healthcare professionals to support NRLs sample collection services, thus improving diagnosis and treatment outcomes in outpatients.
The public-private partnership will help to reduce pressure on the UAEs healthcare infrastructure at a time of growing demand for professional home healthcare for adult and pediatric patients, driven by the growing incidence of non-communicable diseases, birth defects, and other life-changing medical incidents such as strokes. It also supports the UAEs Vision 2021 National Agenda, which aims to make the UAE among the best countries in the world in terms of quality of healthcare.


BACKGROUND & AIMS: Study objectives were to test (a) whether increased incidence of metabolic acidosis (MA) was caused by introduction of a new commercially available fortifier for breast milk, (b) if so, whether its modification would decrease the incidence of MA and (c) to analyze the impact of MA on growth. METHODS: Double-blind randomized design. Healthy breast-fed infants (≤34 gestational weeks). Primary outcome measure was incidence of MA (BE < -6.0 mmol/L). Secondary outcome measures were growth, bone mineral content (BMC), vital signs, treatment with sodium hydrogen carbonate and Ca and laboratory parameters (pH, pCO₂, HCO₃⁻, electrolytes). RESULTS: Part 1 (comparison of standard (SF) and new fortifier (NF)): Interim analysis showed MA in 1 out of 7 (SF) and 7 out of 8 (NF) infants, p = 0.01; therefore the study was interrupted; subsequently the fortifier was adapted by modifying mineral components. Part 2 (comparison of SF and reformulated fortifier (RF)): MA occurred in 3 out of 15 (SF) and 6 out of 19 (RF), p = 0.7. When data of all infants studied, those with MA had lower mean weight gain (median: 9 vs. 21 g/kg/d, p < 0.01) and lower BMC (1.6% vs. 1.9% BMC/lean, p = 0.04) at discharge. CONCLUSIONS: When fed fortified breast milk, mild MA spontaneously may develop in 20-30% of VLBW infants. A fortifier with an inappropriate composition may increase the severity and frequency of MA. Our data show that weight gain and BMC seem to be related to acid-base homeostasis. It may be speculated that inadequate growth of fully fed preterm infants is triggered more often by imbalances of acid-base status than previously expected.


All initial applications for processing a "Business Tax/Certificate of Use" - (formally known as a Business Occupational License) must be submitted to our office within 15 days of tenant occupancy or start date on Division of Corporation - "Sunbiz". Any changes to an existing business must be submitted to our office within 15 days of the change. All applications must be submitted by a representative of the business who is knowledgeable with the business operations, location and who is also authorized to make payment for all applicable fees due.
**Palm Beach County Application is required to be submitted with city application.
Please call 561-393-7937 if you have any questions.
Please come in to the one-stop center at 200 NW 2 Avenue, office hours are 8 A.M. to 4 P.M., Monday, Tuesday, Thursday, Friday and on Wednesday until 3 P.M.
Sign in for Business Tax and we will ensure that all state license requirements have been met; zoning requirements are in compliance and are signed off on the Palm Beach County Business Tax Application.
Inspections are required for your "Certificate of Use" and need to be scheduled. Further instructions will be given and all appropriate fees will be collected.
Any change requires an application to be filed within 15 days of the change(s) to avoid paying a penalty.