basic arithmetic

• What are the representations for,
1. zero in 2's compliment
2. the most positive integer that can be represented using 2's compliment
3. the most negative integer that can be represented using 2's compliment
• Give the 8-digit hexadecimal equivalent of
1. 3710
2. -3276810
3. 110111101010110110111110111011112
• Do the following using 6-bit 2's complement arithmetic (a fancy way of saying, ordinary addition in base 2 keeping only 6 bits of your answer). Work using binary (base 2) notation. Remember that subtraction can be performed by negating the second operand and then adding it to the first operand.
1. 13 + 10
2. 15 - 18
3. 27 - 6
4. -6 - 15
5. 21 + (-21)
6. 31 + 12
• "Complement and add 1" doesn't seem to be an obvious way to negate a two's complement number. By manipulating the expression A+(-A)=0, show that "complement and add 1" does produce the correct representation for the negative of a two's complement number. Hint: express 0 as (-1+1) and rearrange terms to get -A on one side and XXX+1 on the other and then think about how the expression XXX is related to A using only logical operations (AND, OR, NOT).
• What range of numbers can be represented with an N-bit sign-magnitude number? With an N-bit two's-complement number?
• Create a Verilog module that converts an N-bit sign-magnitude input into an N-bit two's complement output.

Testing

You get the final chip back from the FAB. Now you do the smoke test(power up). Hopefully assuming that things are well (your chip does not go up in smoke) you do the first actual test of data using a sample and a simple test case. Unfortunately the chip does not seem to function as you it is intended to.

How do you know if your chip has a setup time or a hold time problem?

Significance of contamination delay in sequential circuit timing

Q: What is the significance of contamination delay in sequential circuit timing?
Fact: 70-80% of designers who deal with timing closure daily are unaware of this fact.

So, what is contamination delay anyway?
Look at the figure below. tcd is the contamination delay.

Without understanding contamination delay you "should not" complete timing estimation of any sequential circuit.

What do you mean by that?
Contamination delay tells you if you meet the hold time of a flip flop. To understand this better please look at the sequential circuit below.

The contamination delay of the data path in a sequential circuit is critical for the hold time at the flip flop where it is exiting, in this case R2.

mathematically,
th(R2) <= tcd(R1) + tcd(CL2) Contamination delay is also called tmin and Propagation delay is also called tmax in many data sheets.

Fifo

Q. Given the following FIFO and rules, how deep does the FIFO needs to be to prevent underflowing or overflowing?
RULES:
1) frequency(clk_A) = frequency(clk_B) / 4
2) period(en_B) = period(clk_A) * 100
3) duty_cycle(en_B) = 25%

This Q was picked from..
http://grumpytom.com/Interview_Questions/questions.html

Sol: The Q is completely wrong...
1) Underflow in a fifo cannot be prevented by depth calculation.
2) The calculation, the author has provided is unecessary for the question ;-)

FSM based Interview Question

• Calculate the size of the ROM if the sequential element is 'n' bits wide.
• What is the number of locations and the number of bits in each location?
• What is the least upper bound on the number of states in the above FSM?

research research & research again

1. research takes time. spend long hours performing design, simulations, experiments, testing, and writing.
3. resist the urge to keep reading the literature forever. You must do something. If you do not know where to begin, recreate some work found in the recent literature. In doing so, you are bound to come across open research questions.
4. you must perform the research. nobody will tell you every step to make. if they do they will take advantage of you. beware.
5. if you encounter a problem in your research, try to figure it out yourself. try approaching the problem from several different scenarios. if you cannot find success, schedule a meeting with your trusted mentor at your convenience. be sure to have specific questions prepared for this session.
follow these steps and you will invent something...

Approaches that can ease multi-clock designs

Problem 1: Metastability
Solution: Use appropriate synchronizers. (please read my earlier articles to understand the types)

Problem 2: Reset Synchronization
Solution: Proper care is to be taken when deasserting resets as they can make sequential elements to go into metastable state. Have a seperate synchronizer for the reset signal as it enters each clock domain.

Problem 3: Glitches across clock boundaries
Solution: Signals entering synchronizers should be driven directly by a flip flop from the previous clock domain and not a combination logic.

Problem 4: Insufficient hold time in the receiving clock domain
Solution: A signal passing from a fast clock domain to a slow clock domain must be stable for multiple clock cycles in the driving domain to ensure that the slower clock domain will not miss a transition entirely.

Problem 5: Loss of signal correlation
Solution: Ways in which loss of correlation can occur are bits of buses, various copies of single signal, hanshake signals and signal convergence. So use gray code to avoid loss of correlation.

Details:
• Do extensive structural analysis of the design in RTL form to trace all clocks and resets as this can identify
1. all asynchronous clock domains in the design
2. all control and data signals crossing between clock domains
3. any domain crossing signals that have missing or incorrect synchronizers
4. any synchronizer that has the potential for glitches on their inputs
5. any signals that have fanouts to multiple synchronizers
6. any idependantly synchronized signals that reconverge in the receiving clock domain
7. any clock domains whose reset signals are not properly synchronized
8. any gated or derived clocks with glitch potential
The above can be automated and can be run on designs of any complexity.

words of wisdom:
Human beings are organic. Organic matter in general are inefficient by nature and hence inorganic matter developed by such organic matter are also inefficient.
If we were efficient would there something called debugging?

Key points in Logic Design Timing

• In a synchronous design, all memory elements, flip-flops and latches, are synchronized be a master clock.
• A timing diagram is used to graphically describe what happens at each flip-flop or latch output on every clock cycle.
• Clock distribution circuits are designed to minimize the clock skew and jitter. Clock skew is point to point variation in the clock arrival time, while jitter is cycle to cycle variation.
• The critical path is the slowest logic path in the design.
• Flip-flops sample the input D and transfer it to the output Q at each rising or falling edge of the clock.
• The logic input D can not change during the set-up time before, and the hold time, after the clock edge.
• A set-up violation occurs when the input D arrives during or after the set-up time for the critical path under worst-case timing conditions. The usual fix for a set-up violation is to reduce the logic delay.
• A hold violation occurs when a signal races through two levels of logic, through the fastest path, before the hold time is over under best case timing conditions. The usual fix is to insert logic delay.
• Latches are level sensitive devices.
• Preventing set-up violations can be easier because latch D inputs can change while the clock is high. Exploiting this fact is called "cycle stealing".
• Preventing hold violations is much harder due to the inclusion of the clock high time. Thus latch-based designs are not recommended.
• Cell libraries are carefully characterized for timing. To calculate the delay through a cell library, you need to know the load capacitance.
• Timing analysis is performed during and after synthesis, and again before fabrication.

FSM Questions

• Design an FSM that has 1 i/p and 1 o/p. The o/p becomes 1 and remains 1 when at least two 0's and two 1's have occurred as i/p's.
• Design a "%3" FSM that accepts one bit at a time, most significant bit first, and indicates if the number is divisible by 3.
• If an FSM is redesigned using a state register with minimum number of bits after connecting the output of a 3-state FSM to the inputs of an 9-state FSM, what is the maximum number of bits needed?

Verilog Question

A 3:1 mux has three data inputs D0, D1 and D2, two select inputs S0 and S1 and one data output Y.

The value of output Y is calculated as follows:
Y = D0 if S0 = 0 and S1 = 0
Y = D1 if S0 = 1 and S1 = 0
Y = D2 if S1 = 1 (the value S0 doesn't matter)
1. Write a Verilog module for the 3:1 multiplexer using dataflow style modelling (assign) that implements the sum-of-products equation for Y.
2. Write a Verilog module for the 3:1 multiplexer that uses the "?" operator. Again use a dataflow style for your code (ie, use "assign" to set the values of your signals).
3. Write a Verilog module for the 3:1 multiplexer that uses the "case" statement. Remember that a "case" statement can only appear inside of a behavioral block.

sequential circuits

• In order for the circuit shown above to operate correctly what constraints on tH and tS are necessary? Express them in terms of tCD, tPD and the clock period.
• What is the minimum clock period at which this circuit can be clocked and still be guaranteed to work? Express your answer in terms of tH, tS, tCD and tPD. Assume that timing constraints that do not depend on the clock period are met.
• For just this question suppose there is skew in the CLK signal such that the rising edge of CLK arrives at the flip-flop labeled F1 1ns before it arrives at the other three flip-flops. Assume that hold times are not violated. How does this change the minimum clock period at which the circuit above can be clocked and still be guaranteed to work?

sequential circuit

• Assuming that the clock period is 25ns, what is the maximum setup time for the registers for which this circuit will operate correctly?
• Assuming that the clock period is 25ns, what is the maximum hold time for the registers for which this circuit will operate correctly?

sequential circuit

• What is the smallest value for the ROM's contamination delay that ensures the necessary timing specifications are met?
• Assume that the ROM's tCD = 3ns. What is the smallest clock period that ensures that the necessary timing specifications are met.

sequential circuit

• What is the smallest clock period for which the circuit still operates correctly?
• By removing the pair of inverters and connecting the Q output of the left register directly to the D input of the right register, if the clock period could be adjusted appropriately, would the optimized circuit operate correctly? If so, explain the adjustment to the clock period that would be needed.
• When the RESET signal is set to "1" for several cycles, what values are loaded into the registers? (Give values for S0 and S1)
• Assuming the RESET signal has been set to "0" and will stay that way, what value will with the registers have after the next clock edge assuming the current values are S0=1 and S1=1?
• Now suppose there is skew in the CLK signal such that the rising edge of CLK always arrives at the left register exactly 1ns before it arrives at the right register. What is the smallest clock period for which the FSM still operates correctly?

sequential circuit

Calculate timing parameters for the system as a whole taking into account d1 and d2. Don't make any assumption about the relative sizes of the two delays.

sequential circuit

Calculate the timing parameters (tS, tH, tCD, tPD, tCLK) for this system as a whole.

TCP Q&A

1. What is TCP?

Transmission Control Protocol (TCP) provides a reliable byte-stream transfer service between two endpoints on an internet. TCP depends on IP to move packets around the network on its behalf. IP is inherently unreliable, so TCP protects against data loss, data corruption, packet reordering and data duplication by adding checksums and sequence numbers to transmitted data and, on the receiving side, sending back packets that acknowledge the receipt of data.

Before sending data across the network, TCP establishes a connection with the destination via an exchange of management packets. The connection is destroyed, again via an exchange of management packets, when the application that was using TCP indicates that no more data will be transferred. In OSI terms, TCP is a Connection-Oriented Acknowledged Transport protocol.

TCP has a multi-stage flow-control mechanism which continuously adjusts the sender's data rate in an attempt to achieve maximum data throughput while avoiding congestion and subsequent packet losses in the network. It also attempts to make the best use of network resources by packing as much data as possible into a single IP packet, although this behaviour can be overridden by applications that demand immediate data transfer and don't care about the inefficiencies of small network packets.

The fundamentals of TCP are defined in RFC 793, and later RFC's refine the protocol. RFC 1122 catalogues these refinements as of October 1989 and summarises the requirements that a TCP implementation must meet.

TCP is still being developed. For instance, RFC 1323 introduces a TCP option that can be useful when traffic is being carried over high-capacity links. It is important that such developments are backwards-compatible. That is, a TCP implementation that supports a new feature must continue to work with older TCP implementations that do not support that feature.

2. How does TCP try to avoid network meltdown?

TCP includes several mechanisms that attempt to sustain good data transfer rates while avoiding placing excessive load on the network. TCP's "Slow Start", "Congestion Avoidance", "Fast Retransmit" and "Fast Recovery" algorithms are summarised in RFC 2001. TCP also mandates an algorithm that avoids "Silly Window Syndrome" (SWS), an undesirable condition that results in very small chunks of data being transferred between sender and receiver. SWS Avoidance is discussed in RFC 813. The "Nagle Algorithm", which prevents the sending side of TCP from flooding the network with a train of small frames, is described in RFC 896.

Van Jacobson has done significant work on this aspect of TCP's behaviour. The FAQ used to contain a couple of pieces of historically interesting pieces of Van's email concerning an early implementation of congestion avoidance, but in the interests of saving space they've been removed and can instead be obtained by anonymous FTP from the end-to-end mailing list archive at <ftp://ftp.isi.edu/end2end/end2end-1990.mail>. PostScript slides of a presentation on this implementation of congestion avoidance can be obtained by anonymous FTP from <ftp://ftp.ee.lbl.gov/papers/congavoid.ps.Z>.

That directory contains several other interesting TCP-related papers, including one (<ftp://ftp.ee.lbl.gov/papers/fastretrans.ps>) by Sally Floyd that discusses a algorithm that attempts to give TCP the ability to recover quickly from packet loss in a network.

3. How do applications coexist over TCP and UDP?

Each application running over TCP or UDP distinguishes itself from other applications using the service by reserving and using a 16-bit port number. Destination and source port numbers are placed in the UDP and TCP headers by the originator of the packet before it is given to IP, and the destination port number allows the packet to be delivered to the intended recipient at the destination system.

So, a system may have a Telnet server listening for packets on TCP port 23 while an FTP server listens for packets on TCP port 21 and a DNS server listens for packets on port 53. TCP examines the port number in each received frame and uses it to figure out which server gets the data. UDP has its own similar set of port numbers.

Many servers, like the ones in this example, always listen on the same well-known port number. The actual port number is arbitrary, but is fixed by tradition and by an official allocation or "assignment" of the number by the Internet Assigned Numbers Authority (IANA).

4. Where do I find assigned port numbers?

The IANA allocates and keeps track of all kinds of arbitrary numbers used by TCP/IP, including well-known port numbers. The entire collection is published periodically in an RFC called the Assigned Numbers RFC, each of which supersedes the previous one in the series. The current Assigned Numbers RFC is RFC 1700.

The Assigned Numbers document can also be obtained directly by FTP from the IANA at <ftp://ftp.isi.edu/in-notes/iana/assignments>.

5. What are Sockets? A socket is an abstraction that represents an endpoint of communication. Most applications that consciously use TCP and UDP do so by creating a socket of the appropriate type and then performing a series of operations on that socket. The operations that can be performed on a socket include control operations (suchas associating a port number with the socket, initiating or accepting a connection on the socket, or destroying the socket) data transfer operations (such as writing data through the socket to some other application, or reading data from some other application through the socket) and status operations (such as finding the IP address associated with the socket). The complete set of operations that can be performed on a socket constitutes the Sockets API (Application Programming Interface). If you are interested in writing programs that use TCP/IP then you'll probably need to use and understand the sockets API. Your system manuals may have a description of the API (try `man socket' if you're using a Unix system) and many books devote chapters to it. A FAQ list for sockets programming is available on the Web from its Canadian home at from a UK mirror at or by anonymous FTP from . The TLI (Transport Layer Interface) API provides an alternative programming interface to TCP/IP on some systems, notably those based on AT&T's System V Unix. The Open Group, a Unix standards body, defines a variation of TLI called XTI (X/Open Transport Interface). Note that both sockets and TLI (and XTI) are general-purpose facilities and are defined to be completely independent of TCP/IP. TCP/IP is just one of the protocol families that can be accessed through these API.
6. How can I detect that the other end of a TCP connection has crashed? Can I use "keepalives" for this?
Detecting crashed systems over TCP/IP is difficult. TCP doesn't require any transmission over a connection if the application isn't sending anything, and many of the media over which TCP/IP is used (e.g. Ethernet) don't provide a reliable way to determine whether a particular host is up. If a server doesn't hear from a client, it could be because it has nothing to say, some network between the server and client may be down, the server or client's network interface may be disconnected, or the client may have crashed. Network failures are often temporary (a thin Ethernet will appear down while someone is adding a link to the daisy chain, and it often takes a few minutes for new routes to stabilize when a router goes down) and TCP connections shouldn't be dropped as a result.

Keepalives are a feature of the sockets API that requests that an empty packet be sent periodically over an idle connection; this should evoke an acknowledgement from the remote system if it is still up, a reset if it has rebooted, and a timeout if it is down. These are not normally sent until the connection has been idle for a few hours. The purpose isn't to detect a crash immediately, but to keep unnecessary resources from being allocated forever. If more rapid detection of remote failures is required, this should be implemented in the application protocol. There is no standard mechanism for this, but an example is requiring clients to send a "no-op" message every minute or two. An example protocol that uses this is X Display Manager Control Protocol (XDMCP), part of the X Window System, Version 11; the XDM server managing a session periodically sends a Sync command to the display server, which should evoke an application-level response, and resets the session if it doesn't get a response (this is actually an example of a poor implementation, as a timeout can occur if another client "grabs" the server for too long).
7. Can the TCP keepalive timeouts be configured?
This varies by operating system. There is a program that works on many Unices (though not Linux or Solaris), called netconfig, that allows one to do this and documents many of the variables. It is available by anonymous FTP from . In addition, Richard Stevens' TCP/IP Illustrated, Volume 1 includes a good discussion of setting the most useful variables on many platforms.

IP Fragmentation Q&A

1. What is meant by IP fragmentation?
2. The breaking up of a single IP datagram into two or more IP datagrams of smaller size is called IP fragmentation.

3. Why is an IP datagram fragmented?
4. Every transmission medium has a limit on the maximum size of a frame (MTU) it can transmit. As IP datagrams are encapsulated in frames, the size of IP datagram is also restricted. If the size of An IP datagram is greater than this limit, then it must be fragmented.

5. Which RFCs discuss IP fragmentation?
6. RFC 791 & RFC 815 discusses about IP datagrams, fragmentation and reassembly.

7. Is it possible to select an IP datagram size to always avoid fragmentation?
8. It is not possible to select a particular IP datagram size to always avoid fragmentation, as the MTU for different transmission It is possible, though, for a given path to choose a size that will not lead to fragmentation. This is called Path MTU Discovery and is discussed in the RFC 1191. The TCP transport protocol tries to avoid fragmentation using the Maximum Segment Size (MSS) option.

9. Where an IP datagram may get fragmented?
10. An IP datagram may get fragmented either at the sending host or at one of the intermediate routers.

11. Where are the IP datagram fragments reassembled?
12. The IP fragments are reassembled only at the destination host.

13. How to prevent an IP datagram from being fragmented?
14. A IP datagram can be prevented from fragmentation, by setting the "don't fragment" flag in the IP header.

15. What happens when a datagram must be fragmented to traverse a network, but the "don't fragment" flag in the datagram is set?
16. The datagram whose "don't fragment" flag is set is discarded, if it must be fragmented to traverse a network. Also, a ICMP error message is sent back to the sender of the datagram.

17. Will all the fragments of a datagram reach the destination using the same path?
18. The different fragments of the same IP datagram can travel in either in the same path or in different paths to the destination.

19. Will all the fragments of a datagram arrive at the destination system in the correct order?
20. The different fragments of a single IP datagram can arrive in any order to the destination system.

21. What happens to the original IP datagram when one or more fragments are lost?
22. When one or more fragments of an IP datagram are lost, then the entire IP datagram is discarded after a timeout period.

23. What is the minimum size of an IP fragment?
24. The minimum size of an IP fragment is the minimum size of an IP header plus eight data bytes. Most firewall-type devices will drop an initial IP fragment (offset 0) that does not contain enough data to hold the transport headers. In other words, the IP fragment normally need 20 octets of data in addition to the IP header in order to get through a firewall if offset is 0.

25. What are the limitations on the size of a fragment?
26. The size of an IP datagram fragment is limited by

1. The amount of remaining data in the original IP datagram
2. The MTU of the network and
3. Must be a multiple of 8, except for the final fragment.

27. How is an IP datagram fragment differentiated from a non-fragmented IP datagram?
28. A complete IP datagram is differentiated from an IP fragment using the offset field and the "more fragments" flags. For a non-fragmented IP datagram, the fragment offset will be zero and the "more fragments" flag will be set to zero.

29. How are the fragments of a single IP datagram identified?
30. The "identification" field in the IP header is used to identify the fragments of a single IP datagram. The value of this field is set by the originating system. It is unique for that source-destination pair and protocol for the duration in which the datagram will be active.

31. How is the last fragment of an IP datagram identified?
32. The last fragment of an IP datagram is identified using the "more fragments" flag. The "more fragment" flag is set to zero for the last fragment.

33. How is the length of a complete IP datagram calculated from the received IP fragments?
34. Using the fragment offset field and the length of the last fragment, the length of a complete IP datagram is calculated.

35. How is an IP datagram fragmented?
36. In the following example, an IP datagram is fragmented into two. This same algorithm can be used to fragment the datagram into 'n' fragments.

1. The IP layer creates two new IP datagrams, whose length satisfies the requirements of the network in which the original datagram is going to be sent.
2. The IP header from the original IP datagram is copied to the two new datagrams.
3. The data in the original IP datagram is divided into two on an 8 byte boundary. The number of 8 byte blocks in the first portion is called Number of Fragment Blocks (NFB).
4. The first portion of the data is placed in the first new IP datagram.
5. The length field in the first new IP datagram is set to the length of the first datagram.
6. The fragment offset field in the first IP datagram is set to the value of that field in the original datagram.
7. The "more fragments" field in the first IP datagram is set to one.
8. The second portion of the data is placed in the second new IP datagram.
9. The length field in the second new IP datagram is set to the length of the second datagram.
10. The "more fragments" field in the second IP datagram is set to the same value as the original IP datagram.
11. The fragment offset field in the second IP datagram is set to the value of that field in the original datagram plus NFB.

37. How a destination system reassembles the fragments of an IP datagram?
1. When a host receives an IP fragment, it stores the fragment in a reassembly buffer based on its fragment offset field.
2. Once all the fragments of the original IP datagram are received, the datagram is processed.
3. Upon receiving the first fragment, a reassembly timer is started.
4. If the reassembly timer expires before all the fragments are received, the datagram is discarded.

38. What fields are changed in an IP header due to fragmentation?
39. The following IP header fields are changed due to IP fragmentation:

1. Total Length
3. More Fragments Flag
4. Fragment Offset
6. Options

40. What happens to the IP options field when an IP datagram is fragmented?
41. Depending on the option, either it is copied to all the fragments or to only the first fragment.

42. Which IP options are copied to all the fragments of an IP datagram?
43. If the most significant bit in the option type is set (i.e. value one), then that option is copied to all the fragments. If it is not set (i.e. value zero), it is copied only to the first fragment.

IP Q&A

1. What is IP?
2. Internet Protocol (IP) is an unreliable, best effort delivery, connection-less protocol used for transmitting and receiving data between hosts in a TCP/IP network.

3. To which OSI layer does IP belong?
4. IP belongs to the Network Layer (layer 3) in the OSI model.

5. Which RFC discusses IP?
6. RFC 791 discusses about the IP protocol version 4.

7. Which version of IP is discussed in this document?
8. IP version 4 (IPv4) is discussed in this document.

9. What do you mean by IP is an unreliable protocol?
10. IP is a unreliable protocol because it does not guarantee the delivery of a datagram to its destination. The reliability must be provided by the upper layer protocols like TCP. IP does not support flow control, retransmission, acknowledgement and error recovery.

11. What do you mean by IP is a best-effort protocol?
12. IP is a best-effort protocol, because it will make every effort to always transmit a datagram and also datagrams will not be just discarded. However, the delivery of the datagram to the destination is not guaranteed.

13. What do you mean by IP is a connection-less protocol?
14. IP is a connection-less protocol because it does not maintain state information about the connection to a destination host. Each datagram is handled independent of other datagrams and also each datagram may reach the destination through different network routes.

15. What is the role of IP in the TCP/IP protocol suite?
16. IP is used for

1. Transmitting data from higher-level protocols like TCP, UDP in IP datagrams, from one host to another host in the network.
2. Identifying individual hosts in a network using an IP address.
3. Routing datagrams through gateways and
4. Fragmenting and reassembling datagrams based on the MTU of the underlying network.

17. What is an IP Datagram?
18. An IP datagram is a basic unit of information used by the IP layer to exchange data between two hosts. A IP datagram consists of an IP header and data.

19. How higher-level data is carried by IP to a destination host?
20. The data from higher-level protocols like TCP, UDP is encapsulated in an IP datagram and transmitted to the destination host. IP will not modify the higher-level data.

21. What is the minimum and maximum size of an IP datagram?
22. The minimum size of an IP datagram is 576 bytes and the maximum size is 65535 bytes.

23. What is the minimum and maximum size of an IP datagram header?
24. The minimum size of an IP datagram header is 20 bytes. The maximum IP datagram header size is 60 bytes.

25. Is there a limitation on the minimum size of a IP datagram a network can handle?
26. Yes. All IP networks must be able to handle datagrams of at least 576 bytes in length.

27. What are the fields in an IP datagram header?
28. The various fields in an IP datagram header and their size in bits are shown below:

`    +-------------+    Version      4 bits   +-------------+    IP Header    4 bits    Length        +-------------+    Type of      8 bits    Service       +-------------+    Size of the  16 bits    Datagram      +-------------+    Datagram ID  16 bits   +-------------+    Control      3 bits    Flags         +-------------+    Fragment     13 bits    Offset        +-------------+    Time to      8 bits    Live          +-------------+    Protocol     8 bits   +-------------+    Header       16 bits    Checksum      +-------------+    Source IP    32 bits    Address       +-------------+    Destination  32 bits    IP Address    +-------------+    Options      Variable Length   +-------------+`
The various fields are explained below:
`    +-----------+-----------------------------------------------------+    Version    IP protocol version.  For IPv4, this value is 4.      +-----------+-----------------------------------------------------+    IP Header  Length of the IP header in multiples of                Length     32-bit words.                                         +-----------+-----------------------------------------------------+    Type of    Quality of Service(QOS) requested for this datagram.    Service                                                           (TOS)                                                            +-----------+-----------------------------------------------------+    Datagram   Length of the entire datagram in bytes, including      Size       the header and the payload.                           +-----------+-----------------------------------------------------+    Datagram   Current datagram identifier.                           ID                                                               +-----------+-----------------------------------------------------+    Control    Bit 0: Reserved                                        Flags      Bit 1: 0 - Allow fragment, 1 - Don't fragment.                    Bit 2: 0 - Last fragment, 1 - More fragments.         +-----------+-----------------------------------------------------+    Fragment   Specifies the offset in the original IP datagram,      Offset     where this fragment begins.  This is a multiple of                32 bit words.                                         +-----------+-----------------------------------------------------+    Time to    The time upto which this datagram can live in the      Live       network.                                               (TTL)                                                            +-----------+-----------------------------------------------------+    Protocol   Indicates to which upper-layer protocol layer this                datagram should be delivered. e.g. TCP, UDP           +-----------+-----------------------------------------------------+    Header     IP header checksum.                                    Checksum                                                         +-----------+-----------------------------------------------------+    Source IP  IP address of the source host sending this IP          Address    datagram.                                             +-----------+-----------------------------------------------------+    Target IP  IP address of the destination host to which this       Address    IP datagram must be delivered.                        +-----------+-----------------------------------------------------+    Options    Used for timestamps, security, source routing, etc.   +-----------+-----------------------------------------------------+`

29. What is the byte order used for transmitting datagram headers in the TCP/IP protocol suite?
30. All the datagram headers in the TCP/IP protocol suite are transmitted in the "big endian" byte order. i.e. The most significant byte is transmitted first. This is also called as "network byte order".

31. Why there are two length fields (IP header length, IP datagram length) in the IP header?
32. The size of the IP header is not fixed. Depending on the IP options present, the size of the IP header will vary. A separate field for the IP header length is added, so that the destination system can separate the IP datagram header from the payload.

33. How is the value for datagram identifier calculated?
34. The IP datagram identifier is just a sequence number assigned by the transmitting host. The algorithm for assigning value to this field is not specified by the IP protocol.

35. What is the use of datagram identifier field?
36. The IP datagram identifier field is used to uniquely identify and assemble the different fragments of an IP datagram.

37. Is the datagram identifier field unique for each IP datagram?
38. Yes. The IP datagram identifier field is different for each IP datagram transmitted. The fragments of an IP datagram will have the same identifier value.

39. What is the use of Type Of Service field in the IP header?
40. The Type Of Service (TOS) field is used TCP to describe the desired quality of service for an IP datagram by upper layer protocols like TCP. This field can be used to specify the nature and priority of a IP datagram (like Network Control, Immediate, Critical, etc) and the criteria for selecting a path for forwarding a datagram by a gateway.

41. What are the different types of criteria can be specified using the TOS field?
42. The different types of criteria that can be specified by the TOS field in an IP datagram are:

1. Minimize delay,
2. Maximize throughput
3. Maximize reliability
4. Minimize cost and
5. Normal service.

43. Which RFC discusses the Type Of Service (TOS) field?
44. RFC 1349 discusses the Type Of Service (TOS) field.

45. What is the use of the Time To Live (TTL) field in the IP header?
46. The TTL field is used to limit the lifetime of a IP datagram and to prevent indefinite looping of IP datagrams.

47. How is the TTL field used to prevent indefinite looping of IP datagrams?
48. The TTL field contains a counter value set by the source host. Each gateway that processes this datagram, decreases the TTL value by one. When the TTL value reaches zero, the datagram is discarded.

49. What is the typical value for the TTL field?
50. The typical value for a TTL field is 32 or 64.

51. When is a datagram considered undeliverable?
52. If a datagram cannot be delivered to the destination host due to some reason, it is considered an undeliverable datagram.

53. How a datagram becomes an undeliverable datagram?
54. A datagram may become undeliverable, if

1. The destination host is down.
3. A network in the route to the destination host is down.
4. The Time To Live (TTL) value of the datagram becomes zero.

55. What happens to an undeliverable datagram?
56. An undeliverable datagram is discarded and an ICMP error message is sent to the source host.

57. Is it possible for an IP datagram to be duplicated?
58. Yes. A host may receive the same copy of an IP datagram twice. It is upto the higher layer protocols to discard the duplicate copy of the datagram.

59. Which part of the IP datagram is used for calculating the checksum?
60. The checksum field in the IP header covers only the IP header. The payload data is not used for calculating this checksum.

RARP Q&A

1. What is RARP?
2. Reverse Address Resolution Protocol (RARP) is a network protocol used to resolve a data link layer address to the corresponding network layer address. For example, RARP is used to resolve a Ethernet MAC address to an IP address.

3. To which OSI layer does RARP belong?
4. RARP belongs to the OSI data link layer (layer 2).

5. Which RFC specifies the requirements for RARP?
6. RFC 903 specifies the RARP packet format and other details.

7. Why is RARP needed?
8. Normally, the IP address of a system is stored in a configuration file in the local disk. When the system is started, it determines its IP address from this file. In the case of a diskless workstation, its IP address cannot be stored in the system itself. In this case, RARP can be used to get the IP address from a RARP server.

9. What is a RARP server?
10. All the mappings between the hardware MAC addresses and the IP addresses of the hosts are stored in a configuration file in a host in the network. This host is called the RARP server. This host responds to all the RARP requests.

11. Where is the mapping between the MAC address and IP addresses stored in a RARP server?
12. The mapping between MAC addresses and IP addresses is usually stored in a configuration file in the local hard disk in the RARP server.

13. Can RARP be used in a network other than Ethernet?
14. Yes. RARP is a general protocol, which can be used to map any type of hardware MAC address to any type of network layer protocol address.

15. How does RARP resolve an Ethernet MAC address to an IP address?
16. When a diskless system is booted up, it broadcasts a RARP request packet with its MAC address. This packet is received by all the hosts in the network. When the RARP server receives this packet, it looks up this MAC address in the configuration file and determines the corresponding IP address. It then sends this IP address in the RARP reply packet. The diskless system receives this packet and gets its IP address.

17. When is a RARP request packet generated?
18. A RARP request packet is usually generated during the booting sequence of a host. A host must determines its IP address during the booting sequence. The IP address is needed to communicate with other hosts in the network.

19. What happens when a RARP server receives a RARP request packet?
20. When a RARP server receives a RARP request packet it performs the following steps:

1. The MAC address in the request packet is looked up in the configuration file and mapped to the corresponding IP address.
3. If the mapping is found, a RARP reply packet is generated with the MAC and IP address. This packet is sent to the host, which originated the RARP request.

22. When a host receives a RARP reply packet, it gets its IP address from the packet and completes the booting process. This IP address is used for communicating with other hosts, till it is rebooted.

23. What is the length of a RARP request and reply packet?
24. The length of a RARP request or a RARP reply packet is 28 bytes.

25. What is the RARP packet format?
26. The various fields of a RARP request/reply packet and their length are shown below:

`    +--------+   Hardware 2 bytes   MAC       Address   Type      +--------+   Protocol 2 bytes   Address   Type      +--------+   Hardware 1 byte   MAC       Address   Size      +--------+   Protocol 1 byte   Address   Size      +--------+   Op       2 bytes   +--------+   Sender   6 bytes (depends on the above size field)   MAC       Address   +--------+   Sender   4 bytes (depends on the above size field)   IP        Address   +--------+   Target   6 bytes (depends on the above size field)   MAC       Address   +--------+   Target   4 bytes (depends on the above size field)   IP        Address   +--------+`
The fields are further explained below:
`    +---------+-------------------------------------------------------+   Ethernet For a RARP request, source MAC address is the MAC        Header   address of the host sending the RARP request,                     destination MAC address is the Ethernet broadcast                 address (FF:FF:FF:FF:FF:FF), frame type field is 0x8035            For RARP reply, source MAC address is the MAC address             of the RARP server replying to the RARP request,                  destination MAC address is the MAC address of the host            that sent the RARP request, and the frame type field is            0x8035.                                                  +---------+-------------------------------------------------------+   Hardware Type of the hardware MAC address present in the packet.   Address  For Ethernet the value of this field is 1.               Type                                                              +---------+-------------------------------------------------------+   Protocol Type of the protocol address requested for the MAC       Address  address. For IP address the value of this field is       Type     0x800.                                                   +---------+-------------------------------------------------------+   Hardware Size of the hardware MAC address.  For Ethernet, the     Address  value of this field is 6.                                Size                                                              +---------+-------------------------------------------------------+   Protocol Size of the protocol address.  For IP, the value of      Address  this field is 4.                                         Size                                                              +---------+-------------------------------------------------------+   OperationType of operation being performed.  The value of this             field can be 3 (RARP request) or 4 (RARP reply).         +---------+-------------------------------------------------------+   Source   In a RARP request packet, this is the hardware MAC       MAC      address of the source host.  In a RARP reply packet,     address  this is the hardware MAC address of the RARP server               sending the RARP reply.                                  +---------+-------------------------------------------------------+   Source   In a RARP request packet, this is undefined.  In a       IP       RARP reply packet, this is the IP address of the RARP    address  server sending the RARP reply.                           +---------+-------------------------------------------------------+   Target   In a RARP request packet, this is the hardware MAC       MAC      address of the source host.  In a RARP reply packet,     address  this is the hardware MAC address of the host, that sent            the RARP request packet.                                 +---------+-------------------------------------------------------+   Target   In a RARP request packet, this is undefined. In a RARP   IP       reply packet, this is the IP address of the host         address  that sent the RARP request packet.                       +---------+-------------------------------------------------------+`

27. Does RARP use the same packet format as ARP?
28. Yes. RARP uses the same packet format as ARP.

29. How is a RARP packet differentiated from an ARP packet?
30. The frame type in the Ethernet header is used to differentiate a RARP packet from an ARP packet. The value of the opcode field in the RARP header can also be used.

31. Is the format of a RARP request packet the same as that of a RARP reply packet?
32. Yes. The packet format of a RARP request packet is same as that of a RARP reply packet.

33. How is a RARP request differentiated from a RARP reply packet?
34. The 'operation' field in the RARP packet is used to differentiate between a RARP request and a RARP reply packet.

35. What are the values for the source and destination IP address fields in a RARP request packet?
36. In an RARP request packet, the source and destination IP address values are undefined.

37. What are the values for the source and destination IP address values in a RARP reply packet?
38. In a RARP reply packet, the source IP address is the IP address of the RARP server responding to the RARP request and the destination IP address is the IP address of the host that sent the RARP request.

39. Do all the hosts in a network process a RARP packet?
40. Since a RARP request packet is a broadcast packet, it is received by all the hosts in the network. But only a RARP server processes a RARP request packet, all the other hosts discard the packet. The RARP reply packet is not broadcast, it is sent directly to the host, which sent the RARP request.

41. What will happen if more than one RARP server in a network responds to a RARP request?
42. If more than one RARP server respond to a RARP request, then only the first RARP reply received is used. All other replies are discarded.

43. What will happen if a RARP reply is not received for a RARP request?
44. If a RARP reply is not received within a reasonable amount of time, the host, which sent the RARP request, will not be able to complete its booting sequence. Usually the host will again retry sending the RARP request after a timeout period.

45. Are there any alternative protocols to RARP?
46. The BOOTP and DHCP protocols can be used instead of RARP to get the IP address from the MAC address.

ARP Q&A

1. What is ARP?
2. Address Resolution Protocol (ARP) is a network protocol, which maps a network layer protocol address to a data link layer hardware address. For example, ARP is used to resolve IP address to the corresponding Ethernet address.

3. To which OSI layer does ARP belong?
4. ARP belongs to the OSI data link layer (Layer 2). ARP protocol is implemented by the network protocol driver. ARP packets are encapsulated by Ethernet headers and transmitted.

5. Which RFC specify the requirements for ARP?
6. RFC 826 specifies the ARP packet format and other details.

7. What is the use of ARP?
8. A host in an Ethernet network can communicate with another host, only if it knows the Ethernet address (MAC address) of that host. The higher level protocols like IP use a different kind of addressing scheme (like IP address) from the lower level hardware addressing scheme like MAC address. ARP is used to get the Ethernet address of a host from its IP address. ARP is extensively used by all the hosts in an Ethernet network.

9. Why a IP address needs to be mapped to a MAC address, why can't the MAC address itself is represented using the IP address?
10. The length of a MAC address is 6 bytes and the length of an IP address is 4 bytes. Obviously, the MAC address cannot be represented using the IP address. So an IP address must be mapped to the corresponding MAC address.

11. Can ARP be used in a network other than Ethernet?
12. ARP is a general protocol, which can be used in any type of broadcast network. The fields in the ARP packet specifies the type of the MAC address and the type of the protocol address. ARP is used with most IEEE 802.x LAN media. In particular, it is also used with FDDI, Token Ring, and Fast Ethernet, in precisely the same way as it is with Ethernet.

13. How does ARP resolve an IP address to an Ethernet MAC address?
14. When ARP needs to resolve a given IP address to Ethernet address, it broadcasts an ARP request packet. The ARP request packet contains the source MAC address and the source IP address and the destination IP address. Each host in the local network receives this packet. The host with the specified destination IP address, sends an ARP reply packet to the originating host with its IP address.

15. What is an ARP cache?
16. ARP maintains the mapping between IP address and MAC address in a table in memory called ARP cache. The entries in this table are dynamically added and removed.

17. When is an ARP request packet generated?
18. The following steps results in the generation of an ARP request packet:

1. The IP module sends a packet, destined for another host in the network, to the ARP module.
2. The ARP module looks up the ARP table (cache) to resolve the IP address.
3. If the supplied IP address is present in the ARP cache, it is resolved into its Ethernet address.
4. If the ARP module is not able to find an entry for this IP address in the ARP cache, then it sends an ARP request packet to the Ethernet driver, to resolve the IP address to the Ethernet address.
5. After the IP address is resolved by the ARP module, the packet is sent to the Ethernet driver for transmission.

19. What happens when a host receives an ARP request packet?
20. The ARP request is received and processed by all the hosts in the network, since it is a broadcast packet. The following steps are carried out when a ARP request packet is received by a host:

1. If the IP address to be resolved is for this host, then the ARP module sends an ARP reply packet with its Ethernet MAC address.
2. If the IP address to be resolved is for this host, then the ARP module updates its ARP cache with the source Ethernet MAC address to source IP address mapping present in the ARP request packet. If the entry is already present in the cache, it is overwritten. If it is not present, it is added.
3. If the IP address to be resolved is not for this host, then the ARP module discards the ARP request packet.

21. Will a host update its ARP cache upon receiving any ARP request?
22. A host will update its ARP cache, only if the ARP request is for its IP address. Otherwise, it will discard the ARP request.

23. What is the disadvantage if a host updates its ARP cache upon receiving any ARP request?
24. The host will exhaust the ARP cache with a lot of unused ARP entries, if it updates the ARP cache for any ARP request.

26. The ARP reply packet is received only by the host, which transmitted the ARP request packet. The ARP module adds the Ethernet hardware address to IP address mapping present in the ARP reply packet to the ARP cache.

27. Is there a separate packet format for ARP request and ARP reply?
28. No. Both the ARP request and ARP reply packets use the same format.

29. Which MAC address is an ARP request directed to?
30. All ARP request packets are transmitted with the Ethernet broadcast address, so that all hosts in the network will receive the request.

31. To which MAC address is an ARP reply packet directed to?
32. ARP reply packet is directed to the host, which transmitted the ARP request packet.

33. If a host is not able to get the MAC address of a host, how it knows about its IP address?
34. A host will either use a static file like /etc/hosts or DNS protocol to get the IP address of another host.

35. What will happen if an ARP reply is not received for an ARP request?
36. If an ARP reply is not received, then that IP address cannot be resolved to an Ethernet address. Without a Ethernet address, the packets cannot be transmitted.

37. When is an entry added to the ARP cache?
38. A new entry is added to the ARP cache when an IP address is successfully mapped to a MAC address. Usually, entries are added dynamically to the ARP cache. Static entries can also be added.

39. What will happen if a new ARP request packet is received, but the MAC address to IP address is already present in the ARP cache?
40. If a ARP request packet is received and the mapping already exists in the ARP cache, it will be overwritten with the values present in the request.

41. When is an entry removed from an ARP cache?
42. An entry in an ARP cache is removed after a pre-determined timeout period (e.g. 20 minutes).

43. What is the format of an ARP packet?
44. The various fields of a ARP request/reply packet and their length are shown below:

`    +--------+   Hardware 2 bytes   MAC       Address   Type      +--------+   Protocol 2 bytes   Address   Type      +--------+   Hardware 1 byte   MAC       Address   Size      +--------+   Protocol 1 byte   Address   Size      +--------+   Op       2 bytes   +--------+   Sender   6 bytes (depends on the above size field)   MAC       Address   +--------+   Sender   4 bytes (depends on the above size field)   IP        Address   +--------+   Target   6 bytes (depends on the above size field)   MAC       Address   +--------+   Target   4 bytes (depends on the above size field)   IP        Address   +--------+`
The fields are further explained below:
`    +---------+-------------------------------------------------------+   Ethernet For a ARP request, source MAC address is the MAC         Header   address of the host sending the ARP request,                      destination MAC address is the Ethernet broadcast                 address (FF:FF:FF:FF:FF:FF), frame type field is 0x806.            For ARP reply, source MAC address is the MAC address of            the host replying to the ARP request, destination MAC             address is the MAC address of the host that sent the              ARP request, and the frame type field is 0x806.          +---------+-------------------------------------------------------+   Hardware Type of the hardware MAC address which is being mapped.   Address  For Ethernet the value of this field is 1.               Type                                                              +---------+-------------------------------------------------------+   Protocol Type of the protocol address to which the MAC address    Address  is mapped.  For IP address the value of this field is    Type     0x800.                                                   +---------+-------------------------------------------------------+   Hardware Size of the hardware MAC address.  For Ethernet, the     Address  value of this field is 6.                                Size                                                              +---------+-------------------------------------------------------+   Protocol Size of the protocol address.  For IP, the value of      Address  this field is 4.                                         Size                                                              +---------+-------------------------------------------------------+   OperationType of operation being performed.  The value of this             field can be 1 (ARP request), 2 (ARP reply)              +---------+-------------------------------------------------------+   Source   The hardware MAC address of the host sending the ARP     MAC      request or reply.  This is same as the source MAC        address  address present in the Ethernet header.                  +---------+-------------------------------------------------------+   Source   The IP address of the host sending the ARP request or    IP       reply.                                                   address                                                           +---------+-------------------------------------------------------+   Target   The hardware MAC address of the host receiving the ARP   MAC      request or reply.  This is same as the destination MAC   address  address present in the Ethernet header.                  +---------+-------------------------------------------------------+   Target   The IP address of the host receiving the ARP request     IP       or reply.                                                address                                                           +---------+-------------------------------------------------------+`

45. What is the size of an ARP request and reply packet?
46. The size of an ARP request or reply packet is 28 bytes.

47. How to differentiate between a ARP request packet and a ARP reply packet, as the Ethernet type field is same on both the packets?
48. An ARP request packet can be differentiated from an ARP reply packet using the 'operation' field in the ARP packet. For a ARP request it is 1 and for an ARP reply it is 2.

49. Why is the hardware MAC address present in both the Ethernet header and the ARP packet (request and reply)?
50. The Ethernet header is processed by the data link driver and removed from the packet. When the ARP layer gets the packet, it needs to know the hardware and protocol addresses in order to update the table. That is why the hardware MAC address is present in both the Ethernet header and the ARP packet.

51. What is proxy ARP?
52. Proxy ARP is the process in which one system responds to the ARP request for another system. For example, host A sends an ARP request to resolve the IP address of host B. Instead of Host B, Host C responds to this ARP request.

53. What is the use of proxy ARP?
54. When routers receive ARP requests from one network for hosts on the network, they will respond with a ARP reply packet with their MAC address. For example, let us say host A is in one network, host B is in another network and router C connects these two networks. When host A sends an ARP request to resolve the IP address of host B, the router C receives this packet. The router C sends an ARP reply with its MAC address. So host A will send all the packets destined for host B to the router C. Router C will then forward those packets to host B. Proxy ARP is also used if a host in a network is not able to understand subnet addressing. For example, if host A and host B are actually in two different subnets, but host A cannot understand subnet addressing. So host A assumes that host B is present in the same network. In this case a router, host C, can use proxy ARP to route packets between host A and host B.

55. What is gratuitous ARP?
56. When a host sends an ARP request to resolve its own IP address, it is called gratuitous ARP. In the ARP request packet, the source IP address and destination IP address are filled with the same source IP address itself. The destination MAC address is the Ethernet broadcast address (FF:FF:FF:FF:FF:FF).

57. What is the use of gratuitous ARP?
58. Gratuitous ARP is used for the following:

1. In a properly configured network, there will not be an ARP reply for a gratuitous ARP request. But if another host in the network is also configured with the same IP address as the source host, then the source host will get an ARP reply. In this way, a host can determine whether another host is also configured with its IP address.
2. When the network interface card in a system is changed, the MAC address to its IP address mapping is changed. In this case, when the host is rebooted, it will send an ARP request packet for its own IP address. As this is a broadcast packet, all the hosts in the network will receive and process this packet. They will update their old mapping in the ARP cache with this new mapping.

Ethernet Q&A

1. What is Ethernet?
2. Ethernet is a Local Area Network (LAN) cabling and signaling specification for baseband networks. Ethernet uses a bus or star topology for connecting different nodes in a network.

3. To which OSI layer does Ethernet belong?
4. Ethernet belongs to both the Physical Layer (Layer 1) and the Data Link layer (Layer 2) in the OSI architecture.

5. What are the standard data rates for Ethernet?
6. The standard data rates for Ethernet are 10 Mbps, 100 Mbps, and 1 Gbps

7. What are the IEEE standards that cover Ethernet?
8. The following IEEE standards define Ethernet:

`   +--------+----------------------------------------------------+  IEEE                      Description                        Standard                                                     +--------+----------------------------------------------------+  802.2   Logical Link Control (LLC) Specification.  Specifies          the general interface between the network layer              (IP, IPX, etc) and the data link layer (Ethernet,            Token Ring, etc).                                    +--------+----------------------------------------------------+  802.3   CSMA/CD Network (Ethernet) Specification.  Specifies          the frame format, cabling and signaling standards.   +--------+----------------------------------------------------+`

9. How two systems in an Ethernet network communicate?
10. In a Ethernet network, a system broadcasts the data using a Ethernet frame. The destination system is specified in the Ethernet frame using its Ethernet address. All the systems in the network listen for an Ethernet frame with their Ethernet address in it. When a system receives an Ethernet frame with its address in it, it processes the frame and sends it to the higher layers (like IP) for further processing.

11. What is a "collision"?
12. At any one instance, in an Ethernet network, only one device can transmit. If two devices transmit at the same instance, then the signals from both devices will collide and a "collision" will occur. When a "collision" occurs, the signals will get distorted and the frame will be lost. Collisions are very common in a Ethernet network.

13. How is "collision" handled in Ethernet networks?
14. Ethernet uses the Carrier Sense Multiple Access with Collision Detection (CSMA/CD) media access control mechanism to detect and recover from a collision.

15. What is CSMA/CD?
16. CSMA/CD is a media access control mechanism used in Ethernet to recover from frame collision. The following steps are followed to recover from a collision.

Step 1: Before an Ethernet device sends a frame on the Ethernet cable, it listens to find if another device is already transmitting a frame (Carrier Sense).
Step 2: Once the device finds that other devices are not transmitting any frame, it starts transmitting the frame. If two devices detect that the Ethernet cable is free at the same time, then both will start transmitting the frames (Multiple Access). This will result in collision.
Step 3: The Ethernet devices while transmitting the frames, also listen for the collision. (Collision Detect).
Step 4: If they detect a collision, both the devices stop sending the frame (back off).
Step 5: They retry the transmission after a logarithmic time-out period. This process is repeated till the frame is transmitted successfully, for a maximum of 16 times. The frame is discarded after the 16th retry.

17. What is "late collision"?
18. An Ethernet device will detect a collision, while it is transmitting, only if the collision reaches it before it completes transmitting the entire frame. If the collision reaches the transmitter, after it completed sending the entire frame, then the transmitter will not detect the collision, it will assume the collision occurred because of some other frame. This is called "late collision". Late collision will occur, if the length of the Ethernet network segment is greater than the standard allowed length.

19. How "late collision" is avoided in Ethernet?
20. Late collision can be avoided, if the maximum length of the Ethernet network segment is restricted, such that if a collision occurs, it will reach the transmitter before the transmitter completed transmitting the entire frame. In a typical 10 Mbps network, the minimum length of an Ethernet frame is 576 bits (72 bytes) and the maximum length of a single Ethernet network segment is 2.5 kms.

21. What is an Ethernet address?
22. Each device in an Ethernet network is uniquely identified by a 48 bit (6 bytes) address called Ethernet address. Ethernet address is also known as Media Access Control (MAC) address. Ethernet addresses are represented as six pairs of hexadecimal digits separated by a colon. Ethernet address are buried in the network adapter by the manufacturer. A Ethernet address of a device cannot be changed. Example: 00:60:08:11:B1:AB, 00:00:c0:5e:83:0e

24. The Ethernet address in which all the bits are 1 is known as a broadcast address. It is represented as FF:FF:FF:FF:FF:FF. A frame with this address is received and processed by all the nodes in the network.

25. What are the different Ethernet frame formats?
26. The different Ethernet frame formats are listed below: Ethernet II and IEEE 802.3

27. Why there are different Ethernet frame formats?
28. Xerox developed the first version of Ethernet, Ethernet I. The second version of Ethernet, Ethernet II, was developed by DEC, Intel and Xerox. After this the Ethernet was standardized by IEEE and the new format is known as 802.3 format. To provide backward compatibility with Ethernet II, 802.2 SNAP format was developed.

29. What is the format of an Ethernet II frame?
30. `    +-----------+----------+----------+-----------+----------+   DestinationSource MACFrame typeData        CRC        MAC AddressAddress   (IP, ARP) (46 to      Checksum   (6 bytes)  (6 bytes) (2 bytes) 1500 bytes) (4 bytes)   +-----------+----------+----------+-----------+----------+`

31. What is the format of an 802.3 frame?
32. The various components of an 802.3 frame are shown below:

`    +----------+---------+-----------+----------+   802.3 MAC 802.2 LLCData        CRC        Header    Header   (43 to      Checksum   (14 bytes)(3 bytes)1497 bytes) (4 bytes)   +----------+---------+-----------+----------+`
`    +-----------+----------+---------+   DestinationSource MACLength of   MAC AddressAddress   the frame   (6 bytes)  (6 bytes) (2 bytes)   +-----------+----------+---------+`
`    +-----------+--------+--------+   DestinationSource  Control   SAP        SAP     Byte      (1 byte)   (1 byte)(1 byte)   +-----------+--------+--------+`

33. What is the format of an 802.2 SNAP frame?
34. `    +----------+---------+----------+-----------+----------+   802.3 MAC 802.2 LLC802.2 SNAPData        CRC        Header    Header   Header    (38 to      Checksum   (14 bytes)(3 bytes)(5 bytes) 1492 bytes) (4 bytes)   +----------+---------+----------+-----------+----------+`
`    +---------------------+---------+   OUI (OrganizationallyType       Unique Id)           (2 bytes)   (3 bytes)                       +---------------------+---------+`

35. How is the length of an Ethernet II frame calculated?
36. The length of an Ethernet II frame is not present in the frame itself. It depends on the Ethernet network interface used. When the interface sends a frame to the network device driver, it supplies the length of the received frame.

37. What is the minimum and maximum size of an Ethernet frame?
38. The minimum size of an Ethernet frame is 64 bytes. The breakup of this size between the fields is: Destination Address (6 bytes) + Source Address (6 bytes) + Frame Type (2 bytes) + Data (46 bytes) + CRC Checksum (4 bytes). The minimum number of bytes passed as data in a frame must be 46 bytes. If the size of the data to be passed is less than this, then padding bytes are added. The maximum size of an Ethernet frame is 1518 bytes. The breakup of this size between the fields is: Destination Address (6 bytes) + Source Address (6 bytes) + Frame Type (2 bytes) + Data (1500 bytes) + CRC Checksum (4 bytes). The maximum number of bytes of data that can be passed in a single frame is 1500 bytes.

39. What is a SAP?
40. SAP, Service Access Point, is the logical point at which services are provided by an OSI layer. Typically, the protocols in the network layer (like IP) bind at specific SAP in the Logical Link Control Layer( LLC) for accessing the services provided by it.

41. Why Sub Network Access Protocol (SNAP) header is required?
42. The 802.2 LLC header replaces the 'protocol type' of the Ethernet II format with two SAP fields, Source SAP and Destination SAP. The value of the SAP field in the 802.2 header is equivalent to the 'protocol type' field in the Ethernet II header. The value of the SAP field will be between 1 and 255, since it is an 8 bit field. On the other hand, the 'protocol type' value for the standard protocols like IP, ARP, etc is grater than 1500. Obviosuly, these values cannot be represented in the SAP fields. So to provide compatibility with Ethernet II, SNAP header was added to the 802.2 LLC header. In a SNAP frame, both the SAP values will be 0xAA and the first 5 bytes of the data will give the protocol ID. Out of the 5 bytes of data, the last 2 bytes are same as the protocol type field of the Ethernet II frame. The first 3 bytes are called as 'Organizationally Unique Identifer' (OUI) and are allocated as a vendor identifier. Typically, OUI will be zero.

43. What are the values for SSAP, DSAP, control and org fields in a 802.2 SNAP frame?
44. `    +-------+-----+   Field  Value   +-------+-----+   SSAP   0xAA   DSAP   0xAA   Control3      OUI    0      +-------+-----+`

45. How to differentiate between an 802.3 frame and an Ethernet II frame?
46. The value of 'length' field in an 802.3 frame must be less than 1500 and in a Ethernet II frame the value of 'type' field must be more than 1500. Since the 802.3 frame 'length' field and the Ethernet II frame 'type' field are at the same offset from the header, depending on the value present, the frame can be differentiated.

47. What is promiscuous mode?
48. Normally, a Ethernet network interface will pass a frame to the above network layers only if it is addressed to that interface. If the network interface is put in the promiscuous mode, the Ethernet network interface will send all the frames (frames addressed to any host in the network), regardless of their destination address to the above network layers. This mode is used by network analyzers to capture all the frames.

49. What is MTU?
50. Maximum Transmission Unit (MTU) is the maximum number of bytes that can be transmitted in a single transmission unit. Every communication medium has a MTU. For Ethernet, the MTU of a frame is 1500.

Algorithms and High-Level Models

For designs with significant control flow, algorithms can be described in software languages, flowcharts, abstract state machines, algorithmic state machines, etc.
For designs with trivial control flow (e.g. every parcel of input data undergoes the same computation), data-dependency graphs (section 2.4.2) are a good way to describe the algorithm.
For designs with a small amount of control flow (e.g. a microprocessor, where a single decision is made based upon the opcode) a set of data-dependency graphs is often a good choice.

When creating an algorithmic description of your hardware design, think about how you can represent parallelism in the algorithmic notation that you are using, and how you can exploit parallelism to improve the performance of your design.

Flow Charts and State Machines:
Flow charts and various flavours of state machines are covered well in many courses. Generally everything that you've learned about these forms of description are also applicable in hardware design. In addition, you can exploit parallelism in state machine design to create communicating finite state machines. A single complex state machine can be factored into multiple simple state machines that operate in parallel and communicate with each other.

In software, the expression: (((((a + b) + c) + d) + e) + f) takes the same amount of time to execute as: (a + b) + (c + d) + (e + f).
But, remember: hardware runs in parallel. In algorithmic descriptions, parentheses can guide parallel vs serial execution. In hardware, (((((a + b) + c) + d) + e) + f) takes 5 adders with a depth of 5 for result, and using (a + b) + (c + d) + (e + f) also takes 5 adders but just a depth of 3 to compute the result.
Datadependency graphs capture algorithms of datapath-centric designs. Datapath-centric designs have few, if any, control decisions: every parcel of input data undergoes the same computation.

High-Level Models:
There are many different types of high-level models, depending upon the purpose of the model and the characteristics of the design that the model describes. Some models may capture power consumption, others performance, others data functionality.

High-level models are used to estimate the most important design metrics very early in the design cycle. If power consumption is more important that performance, then you might write highlevel models that can predict the power consumption of different design choices, but which has no information about the number of clock cycles that a computation takes, or which predicts the latency inaccurately.

Conversely, if performance is important, you might write clock-cycle accurate high-level models that do not contain any information about power consumption. Conventionally, performance has been the primary design metric. Hence, high-level models that predict performance are more prevalent and more well understood than other types of high-level models. There are many research and entrepreneurial opportunities for people who can develop tools and/or languages for high-level models for estimating power, area, maximum clock speed, etc.

“behavioural model” & “structural model”

The phrases "behavioural model" and "structural model" are commonly used for what we'll call "high-level models" and "synthesizable models". In most cases, what people call structural code contains both structural and behavioural code. The technically correct definition of a structural model is an HDL program that contains only component instantiations and generate statements. Thus, even a program with c <= a AND b; is, strictly speaking, behavioural.

Basic aspects of a typical digital design flow...

• Requirements
• Description of what the customer wants
• Algorithm
• Functional description of computation. Probably not synthesizable. Could be a flowchart, software, diagram, mathematical equation, etc..
• High-Level Model
• HDL code that is not necessarily synthesizable, but divides algorithm into signals and clock cycles. Possibly mixes datapath and control. In VHDL, could be a singleprocess that captures the behaviour of the algorithm. Usually synthesizable; resulting hardware is usually big and slow compared to optimized RTL code.
• Dataflow Diagram
• A picture that depicts the datapath computation over time, clock-cycle by clock-cycle.
• Hardware Block Diagram
• A picture that depicts the structure of the datapath: the components and the connections between the components. (e.g., netlist or schematic)
• State Machine
• A picture that depicts the behaviour of the control circuitry over time.
• DP+Ctrl RTL code
• Synthesizable HDL code that separates the datapath and control into separate processes and assignments.
• Optimized RTL Code
• HDL code that has been written to meet design goals (high performance, low power, small, etc.)
• Implementation Code
• A collection of files that include all of the information needed to build the circuit: HDL program targeted for a particular implementation technology (e.g.a specificFPGA chip), constraint files, script files, etc.

Note: Recomendation Spend the time up front to plan a good design on paper. Use dataflow diagrams and state machines to predict performance and area. You will probably produce a more optimal design with less effort if you explore high-level optimizations with dataflow diagrams and state machines.