Memory Types (Chapter 2)

• Differences between RAM and CAM.

  • RAM: takes address and returns data

  • CAM: takes data and returns address. Search can be done in a single clock cycle

    

• Differences between CAM and TCAM.

  • TCAM is similar to CAM, but has not only 0 and 1 states, but also X state (don’t care). T means “ternary” .

• Prioritization in TCAMs. Use case in Internet Routing

  • If there are several matches (which is usually a case due to X states) the first match will be returned. We can use it to implement the longest prefix matching, by placing the entries in the descending order by their lengths

• Is prioritization also possible with CAM?

  • No, because CAM has no “don't care” entries, and can not used for prefix matching with wildcards, only for direct searches

• One pro and one contra for TCAM

  • Makes very fast longest prefix matching possible
  • But requires much energy, has high cost and low density

• How long takes the search in CAM?

  • Always 1 clock cycle

Prefix Search (Chapter 2)

• What is a Binary Trie?

  • Data Structure that can be used for longest prefix matching

    

    

• Which data structure can be used for speed optimization of Binary Trie?

  • Hash Tables. Map IP address to the output port. Can be used as cache for previous search results. For each received IP packet: Does an entry for destination IP address exist in hash table? If yes, then return port. If not, then perform trie lookup and put result in hash table.

• What is a path comperssion?

  • Store for each node a bit index that has to be examined next. With path compression we can save us all nodes that do not correspond to a specific prefix.

    

    

• What is a multibit trie?

  • Like Binary Trie, but split the prefixes not by single bits, but by bit chunks of fixed length (strides). Some preparation of prefix table is needed - it has to be expanded to fit the stride sizes.

  

  

• Multibit Trie with stride k=3 is given. Insert a prefix. How many nodes should be modified in worst case?

  • In normal case only one new node. More insertion can be required only if some prefix expansion should be performed. For example, for prefix 1** we have to insert the nodes for 100, 101, 110 and 111

Routers (Chapter 2)

• What is Head-of-Line-Blocking in router?

  • Waiting packet at head of the buffer blocks packet behind it that could be serviced
  • Package want to go to potentially free output port, but there are packages in the buffer queue that want to go to busy port, and packages in their queue have to wait.

  

• Name three basic structures of switch fabric

  • Bus / ring structure: ideal for multicas and broadcast

  

  • Crossbar (grid): buffers are needed on crosspoints

    

  • Multi-level switching networks

    

• How to prevent blocking in routers?

  • Overprovisioning: Internal circuits in switch fabric operate at a higher speed than the individual input ports
  • Buffering: Queue packets at appropriate locations until resources are available
  • Backpressure: Send signal to data sender to reduce sending rate
  • Parallel switch fabrics: Allows parallel transport of multiple packets to output ports