Proposal: FPGA-Based Internet Protocol Version 6 Router

Proposal: FPGA-Based Internet Protocol version 6 Router

Howard Hamilton

Mike Hyatt

Jeff Moore

Julia Pitre

CPSC 483: Computer System Design

Professor: Dr. Rabi Mahapatra

February 2, 2000

Table of Contents

Project Objectives and Deliverables ...... 1
Component and Equipment Lists...... 1
. Cost of Prototype ...... 1
Schedule ...... 1
Team Responsibilities...... 3

4.1. Howard Hamilton...... 3

4.2. Mike Hyatt...... 3

4.3. Jeff Moore...... 3

4.4. Julia Pitre ...... 3

Final Testing Environment...... 3
Theory ...... 4

6.1. LAN technology...... 4

6.2. Internet Protocol ...... 5

Technology ...... 7

7.1. Overview...... 8

7.2. Functional Modules...... 9

7.3. Arbiter...... 9

7.4. Packet Processor (PP)...... 10

7.5. DIOM ...... 10

7.5.1. Packet Forwarding...... 11

7.5.2. Packet Length Calculations...... 11

7.5.3. Checksum Calculations...... 11

7.6. CACM ...... 11

7.6.1. Interacting with the PP...... 12

7.6.2. Interacting with the RTM ...... 12

Conclusion ...... 12
References ...... 13

Index of Tables and Figures

Table 2.1: Component List and Prices...... 1

Table 2.2: Equipment List and Prices...... 1

Figure 6.1: The 802.3 frame...... 4

Figure 6.2: The IP6 header...... 5

Table 6.3: IPv6 Addresses...... 6

Figure 7.1: Block Diagram of External Interface...... 8

Figure 7.2: FSM – Interlocking Processes...... 9

1. Project Objectives and Deliverables

The goal of our project is to construct a router based on a Field Programmable Gate Array. The router will implement Internet Protocol version 6. Our project deliverable will be a functional four-port router. The completed router should be able to route packets between two computers and will require a power supply. It is expected that this project will be 75% software and 25% hardware due to the intensive programming of the FPGA required.

2. Component and Equipment Lists

The components and equipment required are listed below in tables 2.1 and 2.2, respectively. All prices were from various retail suppliers.

Component / Price
Xilinx Chip / $1000*
EEPROM (boot) / $2.00
Router casing / Unknown
Power supply (5V) / Provided by department
Board / Provided by department
4 ethernet interfaces / Unknown

Table 2.1: Component List and Prices

Equipment / Price
Computer capable of programming the FPGA / Free via lab 218
2 Ethernet cables / $10*
2 computers/laptops running LINUX / Free via SSO
2 ethernet cards / $28

Table 2.2: Equipment List and Prices

2.1. Cost of Prototype

The expected cost of the prototype is currently $1,040.00, including shipping and handling. This assumes that components will not need to be replaced, and the cost of unknown components is $0.00.

3. Schedule

A Gantt chart is provided on the next page.
Insert gannt chart here
4. Team Responsibilities

4.1. Howard Hamilton

Howard Hamilton’s responsibilities are as follows:

Software Implementation of the Arbiter module
Software Implementation of the Memory modules
Final testing of Packet Processor module
Hardware implementation

4.2. Mike Hyatt

Mike Hyatt’s responsibilities are as follows:

Software Implementation of the Packet Processor module
Software Implementation of the DIOM
Final testing of the Arbiter module
Assembly driver (midterm deliverable)

4.3. Jeff Moore

Jeff Moore’s responsibilities are as follows:

Software Implementation of the Packet Processor module
Software Implementation of the DIOM
Final testing of the Memory modules
Hardware implementation

4.4. Julia Pitre

Julia Pitre’s responsibilities are as follows:

Component and equipment acquisition
Software Implementation of the Arbiter module
Software Implementation of the Memory modules
Final testing of the DIOM

HLL dummy program (midterm deliverable)

5. Final Testing Environment

Our final test before the demonstration will be to verify that our router functions correctly. This will require two computers running Linux. This operating system is necessary because it supports IP version 6. Both computers will have network cards and will connect to the router through ethernet cable. Our final test will be to try to ping one computer from the other.

6. Theory

The Internet Protocol handles the internet layer of the TCP/IP stack. Internet Protocol handles end-to-end connectivity between hosts on an internetwork; it moves information from one host on the network to another host. IP is serviced from beneath by the Host to Network layer of the TCP/IP protocol stack, and provides its services to the transport protocol above it. In this case, we shall be using Ethernet to handle the network functions of our device.

6.1. LAN technology

Our device will be implemented using Ethernet LAN technology. Ethernet is an implementation of the IEEE 802.3 1 persistent CSMA/CD local area network protocol. 1 persistent CSMA/CD, or Carrier Sense Multiple Access with Collision Detection describes the media access method specified by 802.3. Since the network is a bus, only one host may transmit at a time. 1 persistent CSMA protocol dictates that the host waits until it detects an idle channel. Then with a probability of 1, the host will attempt to transmit a frame over that channel. Should two networks attempt to access the LAN simultaneously, a collision occurs and all colliding hosts immediately terminate their transmissions, wait a random amount of time, and then transmit their frames. 1 persistent CSMA differs from nonpersistent and p-persistent CSMA in that the host attempts to transmit immediately upon detection of an idle line, while the others will wait some amount specified by their varying protocols.

Our device will interface with Ethernet via the 802.3 Medium Access Sublayer. This layer handles the framing of data packets as they are handed off to an internetwork protocol such as IP. Figure 6.1 notes the IEEE 802.3 frame format. Ethernet is not an exact implementation of the 802.3 protocol, but it is functionally similar.

Byte Width / 7 / 1 / 2 or 6 / 2 or 6 / 2 / 0-1500 / 0-46 / 4
Field / Preamble / Start of Frame / Destination Address / Source Address / Length of Data field /

Data

/ Pad / CRC

Figure 6.1: The 802.3 frame

The preamble is the 7-byte pattern with each byte containing the pattern 10101010 (0xAA). This field is followed immediately by the Start of Frame byte pattern, 10101011 (0xAB). These fields are needed so that the receiver can properly synchronize with the sender without the need of a common external clock. The frame contains the destination and source addresses followed by the data length and actual data. The pad field is needed to ensure frames have a minimum length of 64 bytes. This is needed to make distinguishing valid frames from garbage frames left over from aborted transfers due to collision. As well, if a frame becomes too short, it is conceivable that the source station may complete transmission of the frame before the packet reaches the end of the cable. Should a collision occur at this point, the sender would erroneously conclude that the frame was sent successfully. Finally, the CRC is a 32-bit hash code of the data field and is used to ensure that an error free transmission has been made. Should any parts of the frame be damaged due to line noise or some other transmission error, the checksum field will most likely be wrong, and the error will be detected.

6.2. Internet Protocol

Routing is an activity that takes place in the network layer of the TCP/IP protocol, or the Network layer of the ISO/OSI model. Routers examine the IP header attached to a particular datagram of information and forward them along to another network based upon the destination address. Our device will be utilizing version 6 of the Internet Protocol, which has many advantages over version 4, which is currently used by most of the hosts on the global Internet. The IPv6 header is listed below in figure 6.2.

32 bits

Version / Priority /

Flow Label

Payload Length

/ Next Header / Hop Limit
Source Address (16 Bytes)
Destination Address (16 Bytes)

Figure 6.2: The IP6 header

The Version field is essential in that it allows transition from one version of IP to another to take place gradually, over a period of many months or years. Routers can distinguish between IPv4 and IPv6 and handle them accordingly. The Priority field is used to determine the immediacy of the packet. Priorities of 0 through 7 are packets that are subject to various flow control methods in time of network congestion. Priorities 8 through 15 indicate information that must be handled in a real time fashion and cannot be delayed. Multimedia transmission falls under this category, where as FTP and Telnet will have lower priority. The Flow Label field is the IPv6 attempt at gaining the benefits of both datagram and virtual circuit technologies. If a datagram comes through a router with a nonzero flow label, the router will look up that information in a table and determine what special actions it must take.

The Payload length field indicates how many bytes of actual data follow the header. The Next Header field indicates the next header that will need to be processed. IPv6 allows for several optional headers that are not included by default. If there are to be no extension headers, as they are called, then this frame indicates which protocol (TCP, UDP, etc) will be handing this packets transport layer responsibilities. The Hop Limit is decremented at each route point and is used to prevent immortal packets. Should the packet never arrive at its destination, it will be terminated once it reaches its hop limit.

Source and Destination addresses are 16 bytes long, long enough to ensure that, in theory, the potential address space is limitless. However, with a different address length, new schemes for representing IP addresses must be devised. IPv6 addresses are written as 8 colon delimited groups of four hexadecimal numbers. These addresses are likely to contain a large number of zeros, so certain methods have been devised to deal with them. Leading zeros within a number group may be deleted, and one or more groups of zeroes may also be removed; a double colon marks their absence. IPv4 addresses will contain a large number of zeroes when written in IPv6 format, so they may be written with a preceding double colon, then the standard dotted decimal notation. Utilizing these rules, table 6.3 indicates some sample IPv6 headers.

Full IPv6 Address / 1000:0000:000:000:0FED:CAB9:8765:4321
Shortened Address / 1000::FED:CAB9:8765:4321
IPv4 Address / ::128.194.22.168

Table 6.3: IPv6 Addresses

In addition to the normal fields, optional fields may be appended to the IP header. If any of these are to be used, the Next Header field will indicates so. Optional headers may be fixed or variable in length.

IPv6 allows for geographic based, and provider based host addressing. Geographic based addressing is what is in place under IPv4. Provider based addressing is designed under the premise that several large service providers will be managing a large number of IP addresses and each of these companies will be given a slice of the address space. A binary prefix at the head of an IPv6 address determines which addressing system to use There is also the option of link/site local addresses that only have significance within a particular organization, which is useful of sites that wish to be separate from the rest of the planet. Multicast addresses also have a scope field that determines whether the address’s scope is link, site, organizational or planetary. The scope field is robust enough to allow future expansions in the hierarchy to include other planets, star systems or galaxies, should the need arise.

IPv6 includes an additional type of addressing scheme in addition to unicast and multicast known as anycasting. With these addresses, information is sent to a group of addresses, but instead of attempting delivery to all of them, as with multicast, it need only unicast to one host, usually the one it can reach in the shortest amount of time. This is useful when communicating to clusters of machines.

In general, IPv6 is a faster, more flexible protocol than IPv4. It has fewer fields in the header to improve routing performance, as unneeded fields were removed. Additionally, IPv6 does not autofragment packets that are too large to be routed to a particular host. If a router handles a packet that is too large it sends and error to the sender, which then re-transmits all future packets to that destination in smaller units. Additionally, IPv6 compliant routers support 576 byte packets, which minimizes the chance of fragmentation in the first place.

7. Technology

The router we plan to implement will be a small, four-network prototype to examine the concept of IPv6 routing utilizing field programmable gate arrays. We will be implementing our design on Xilinx XC4000 family FPGA’s which will provide a great performance enhancement over software based IPv6 routing solutions. The principle problem of routing is table lookup. When a packet is to be routed, the router searches a database for a best match, based upon the packet destination address and decides which network to forward the packet on to. The planetary Internet is an internetwork of numerous autonomous systems. Within each AS, its governing body may select its own routing algorithms, but it is still convenient to have protocols for communication within and between ASes.

Intra AS communication can be done via the OSPF or Open Shortest Path First method. This protocol is an open standard and is not owned by any particular organization or company. OSPF works by creating a directed graph of the networks it services, weighting them based on delay, distance or reliability and computing shortest paths based upon these numbers. When a packet needs to be directed from one router to another, it is sent along the shortest path indicated for its particular need. OSPF is capable of routing based upon differing metrics such that a packet can be sent along either the route with the least delay, highest throughput, or the most reliable path. Additionally, OSPF allows the grouping of networks within an AS into an abstraction known as an area.

In OSPF, there are four different classes of routers:

Routers internal to one area.
Routers connecting two or more areas.
Routers on the backbone
Routers connecting to other ASes.

When communicating across AS boundaries, a protocol known as BGP, or Border Gateway Protocol is used. An additional protocol is necessary when communication between ASes because international or intercorporate boundaries are often crossed and there are certain political ramifications. Due to security or legal concerns, certain routes that may be technically valid would not be implemented, such as not sending traffic starting or ending at one corporation through the AS of its major competitors. As well, military communications of one nation should not be routed through an AS governed by nations unfriendly to the source or destination. BGP routers primarily communicate with other BGP routers. Currently, we have no plans of implementing BGP capability into our prototype, as it extends beyond the scope of our experiment. In that respect, out device is capable of routing only within its specified autonomous system.

7.1. Overview

Our main objective is to develop an IPv6 router using the FPGA. Almost all implementations of IPv6 routers today are software implementations. Due to the flexibility and high-density design of the FPGA, a hardware routing solution is now more feasible. Figure 7.1 illustrates the external interfaces of the FPGA-based IPv6 router.

Figure 7.1: Block Diagram of External Interface

7.2. Functional Modules

The IPv6 router we plan to implement using the FPGA consists of the following main functional modules: Arbiter, Packet Processor (PP), Direct Input to Output Module (DIOM), and Memory.

7.3. Arbiter

The Arbiter is the main control unit for the router. It allocates resources, controls information-sharing between various modules, initiates packet processing, controls packet forwarding transactions, manages ready input queues, and communicates with the external Logical Link Control sublayer interface. When the input queues have ready packets, the Arbiter selects the queue with the highest priority. It then issues a process command to the PP to operate on the packet, as well as a route command to the DIOM to forward processed packets from the input queues to their target network interface. The following figure shows the design of the Arbiter FSMs.

Figure 7.2: FSM – Interlocking Processes

Note that the function of process 1 is to control the transfer of information from the input queues and the PP, and monitor the status of the input queues via status tables. These status tables function as a shared memory area between process 1 and process 2. Process 2 controls the transfer of information from the input queues and the DIOM, and monitors the status of the input queues by sharing the status tables with process 1. A state transition in process 1 is a function of the input to process 1, the current state of FSM1, the output of process 2, and the current state of FSM2. A state transition in process 2 follows the same pattern. It becomes obvious that the interleaving of the two processes is dependent upon properly saving the state variables in shared memory. It is also critical for the two processes to interlock their results between state machine cycles by reading shared process output variables stored in shared memory. In essence, each machine views the other's output result before starting a new state machine cycle. At start up, process 1 declares a virtual output and starts the cycle.

7.4. Packet Processor (PP)

The PP implements the IPv6 protocol. The processing of a packet could result in one of three outcomes:

The processed packet is a normal packet with no errors and therefore should be routed to its destination
The processed packet contains an error that should be reported to the sender via an ICMP error message
The processed packet has an error that is not an ICMP type error

If the latter takes place, a process status vector informs the Arbiter that the current packet contains errors. If no such errors are detected, processing continues normally. An intermediate operation performed by the FSM is to search for a match for the current destination address carried by the packet in the event the packet is normal packet. If the packet contains ICMP type errors, a search is conducted in order to find a match for the current source address carried by the packet. The remaining actions performed by the FSM are divided into two major analysis operations. The first is a rigorous analysis of the IPv6 header. The result of this analysis leads to a better picture of the state of the packet. If the packet contains no extension headers, the rest of the packet is treated as data. On the other hand, if the packet contains one or more extension headers, the second operation the FSM performs is a recursive analysis of the chained extension headers until no more headers are present. Processing extension headers is a difficult task for the hardware router because the headers are of variable size and their structure is not known a priori. However, their intended objective can be known from the previous headers in the chain.