diff --git a/zebra/Makefile.am b/zebra/Makefile.am
index 90ce7b9..ab09a36 100644
--- a/zebra/Makefile.am
+++ b/zebra/Makefile.am
@@ -1,3 +1,5 @@
+include ../common.am
+
 ## Process this file with automake to produce Makefile.in.
 
 AM_CPPFLAGS = -I.. -I$(top_srcdir) -I$(top_srcdir)/lib -I$(top_builddir)/lib
@@ -20,6 +22,10 @@
 othersrc = zebra_fpm_netlink.c
 endif
 
+if HAVE_PROTOBUF
+protobuf_srcs = zebra_fpm_protobuf.c
+endif
+
 AM_CFLAGS = $(WERROR)
 
 sbin_PROGRAMS = zebra
@@ -30,7 +36,7 @@
 	zserv.c main.c interface.c connected.c zebra_rib.c zebra_routemap.c \
 	redistribute.c debug.c rtadv.c zebra_snmp.c zebra_vty.c \
 	irdp_main.c irdp_interface.c irdp_packet.c router-id.c zebra_fpm.c \
-	$(othersrc)
+	$(othersrc) $(protobuf_srcs)
 
 testzebra_SOURCES = test_main.c zebra_rib.c interface.c connected.c debug.c \
 	zebra_vty.c \
@@ -42,7 +48,7 @@
 	rt_netlink.h zebra_fpm.h zebra_fpm_private.h \
 	ioctl_solaris.h
 
-zebra_LDADD = $(otherobj) ../lib/libzebra.la $(LIBCAP)
+zebra_LDADD = $(otherobj) ../lib/libzebra.la $(LIBCAP) $(Q_FPM_PB_CLIENT_LDOPTS)
 
 testzebra_LDADD = ../lib/libzebra.la $(LIBCAP)
 
diff --git a/zebra/main.c b/zebra/main.c
index 8370732..35cb159 100644
--- a/zebra/main.c
+++ b/zebra/main.c
@@ -71,6 +71,7 @@
   { "batch",       no_argument,       NULL, 'b'},
   { "daemon",      no_argument,       NULL, 'd'},
   { "keep_kernel", no_argument,       NULL, 'k'},
+  { "fpm_format",  required_argument, NULL, 'F'},
   { "config_file", required_argument, NULL, 'f'},
   { "pid_file",    required_argument, NULL, 'i'},
   { "socket",      required_argument, NULL, 'z'},
@@ -130,6 +131,7 @@
 	      "-b, --batch        Runs in batch mode\n"\
 	      "-d, --daemon       Runs in daemon mode\n"\
 	      "-f, --config_file  Set configuration file name\n"\
+	      "-F, --fpm_format   Set fpm format to 'netlink' or 'protobuf'\n"\
 	      "-i, --pid_file     Set process identifier file name\n"\
 	      "-z, --socket       Set path of zebra socket\n"\
 	      "-k, --keep_kernel  Don't delete old routes which installed by "\
@@ -295,6 +297,7 @@
   char *progname;
   struct thread thread;
   char *zserv_path = NULL;
+  char *fpm_format = NULL;
 
   /* Set umask before anything for security */
   umask (0027);
@@ -310,9 +313,9 @@
       int opt;
   
 #ifdef HAVE_NETLINK  
-      opt = getopt_long (argc, argv, "bdkf:i:z:hA:P:ru:g:vs:C", longopts, 0);
+      opt = getopt_long (argc, argv, "bdkf:F:i:z:hA:P:ru:g:vs:C", longopts, 0);
 #else
-      opt = getopt_long (argc, argv, "bdkf:i:z:hA:P:ru:g:vC", longopts, 0);
+      opt = getopt_long (argc, argv, "bdkf:F:i:z:hA:P:ru:g:vC", longopts, 0);
 #endif /* HAVE_NETLINK */
 
       if (opt == EOF)
@@ -336,6 +339,9 @@
 	case 'f':
 	  config_file = optarg;
 	  break;
+	case 'F':
+	  fpm_format = optarg;
+	  break;
 	case 'A':
 	  vty_addr = optarg;
 	  break;
@@ -423,9 +429,9 @@
 #endif /* HAVE_SNMP */
 
 #ifdef HAVE_FPM
-  zfpm_init (zebrad.master, 1, 0);
+  zfpm_init (zebrad.master, 1, 0, fpm_format);
 #else
-  zfpm_init (zebrad.master, 0, 0);
+  zfpm_init (zebrad.master, 0, 0, fpm_format);
 #endif
 
   /* Process the configuration file. Among other configuration
diff --git a/zebra/zebra_fpm.c b/zebra/zebra_fpm.c
index 9cbbf68..22fc6ca 100644
--- a/zebra/zebra_fpm.c
+++ b/zebra/zebra_fpm.c
@@ -139,6 +139,15 @@
 } zfpm_state_t;
 
 /*
+ * Message format to be used to communicate with the FPM.
+ */
+typedef enum
+{
+  ZFPM_MSG_FORMAT_NONE,
+  ZFPM_MSG_FORMAT_NETLINK,
+  ZFPM_MSG_FORMAT_PROTOBUF,
+} zfpm_msg_format_e;
+/*
  * Globals.
  */
 typedef struct zfpm_glob_t_
@@ -149,6 +158,11 @@
    */
   int enabled;
 
+  /*
+   * Message format to be used to communicate with the fpm.
+   */
+  zfpm_msg_format_e message_format;
+
   struct thread_master *master;
 
   zfpm_state_t state;
@@ -863,19 +877,40 @@
  */
 static inline int
 zfpm_encode_route (rib_dest_t *dest, struct rib *rib, char *in_buf,
-		   size_t in_buf_len)
+		   size_t in_buf_len, fpm_msg_type_e *msg_type)
 {
-#ifndef HAVE_NETLINK
-  return 0;
-#else
-
+  size_t len;
   int cmd;
+  len = 0;
 
-  cmd = rib ? RTM_NEWROUTE : RTM_DELROUTE;
+  *msg_type = FPM_MSG_TYPE_NONE;
 
-  return zfpm_netlink_encode_route (cmd, dest, rib, in_buf, in_buf_len);
+  switch (zfpm_g->message_format) {
 
+  case ZFPM_MSG_FORMAT_PROTOBUF:
+#ifdef HAVE_PROTOBUF
+    len = zfpm_protobuf_encode_route (dest, rib, (uint8_t *) in_buf,
+				      in_buf_len);
+    *msg_type = FPM_MSG_TYPE_PROTOBUF;
+#endif
+    break;
+
+  case ZFPM_MSG_FORMAT_NETLINK:
+#ifdef HAVE_NETLINK
+    *msg_type = FPM_MSG_TYPE_NETLINK;
+    cmd = rib ? RTM_NEWROUTE : RTM_DELROUTE;
+    len = zfpm_netlink_encode_route (cmd, dest, rib, in_buf, in_buf_len);
+    assert(fpm_msg_align(len) == len);
+    *msg_type = FPM_MSG_TYPE_NETLINK;
 #endif /* HAVE_NETLINK */
+    break;
+
+  default:
+    break;
+  }
+
+  return len;
+
 }
 
 /*
@@ -883,7 +918,7 @@
  *
  * Returns the rib that is to be sent to the FPM for a given dest.
  */
-static struct rib *
+struct rib *
 zfpm_route_for_update (rib_dest_t *dest)
 {
   struct rib *rib;
@@ -919,6 +954,7 @@
   fpm_msg_hdr_t *hdr;
   struct rib *rib;
   int is_add, write_msg;
+  fpm_msg_type_e msg_type;
 
   s = zfpm_g->obuf;
 
@@ -943,7 +979,6 @@
 
     hdr = (fpm_msg_hdr_t *) buf;
     hdr->version = FPM_PROTO_VERSION;
-    hdr->msg_type = FPM_MSG_TYPE_NETLINK;
 
     data = fpm_msg_data (hdr);
 
@@ -963,11 +998,13 @@
       }
 
     if (write_msg) {
-      data_len = zfpm_encode_route (dest, rib, (char *) data, buf_end - data);
+      data_len = zfpm_encode_route (dest, rib, (char *) data, buf_end - data,
+				    &msg_type);
 
       assert (data_len);
       if (data_len)
 	{
+	  hdr->msg_type = msg_type;
 	  msg_len = fpm_data_len_to_msg_len (data_len);
 	  hdr->msg_len = htons (msg_len);
 	  stream_forward_endp (s, msg_len);
@@ -1569,6 +1606,64 @@
 }
 
 
+/*
+ * zfpm_init_message_format
+ */
+static inline void
+zfpm_init_message_format (const char *format)
+{
+  int have_netlink, have_protobuf;
+
+  have_netlink = have_protobuf = 0;
+
+#ifdef HAVE_NETLINK
+  have_netlink = 1;
+#endif
+
+#ifdef HAVE_PROTOBUF
+  have_protobuf = 1;
+#endif
+
+  zfpm_g->message_format = ZFPM_MSG_FORMAT_NONE;
+
+  if (!format)
+    {
+      if (have_netlink)
+	{
+	  zfpm_g->message_format = ZFPM_MSG_FORMAT_NETLINK;
+	}
+      else if (have_protobuf)
+	{
+	  zfpm_g->message_format = ZFPM_MSG_FORMAT_PROTOBUF;
+	}
+      return;
+    }
+
+  if (!strcmp ("netlink", format))
+    {
+      if (!have_netlink)
+	{
+	  zlog_err ("FPM netlink message format is not available");
+	  return;
+	}
+      zfpm_g->message_format = ZFPM_MSG_FORMAT_NETLINK;
+      return;
+    }
+
+  if (!strcmp ("protobuf", format))
+    {
+      if (!have_protobuf)
+	{
+	  zlog_err ("FPM protobuf message format is not available");
+	  return;
+	}
+      zfpm_g->message_format = ZFPM_MSG_FORMAT_PROTOBUF;
+      return;
+    }
+
+  zlog_warn ("Unknown fpm format '%s'", format);
+}
+
 /**
  * fpm_remote_srv_write 
  *
@@ -1598,11 +1693,13 @@
  *
  * @param[in] port port at which FPM is running.
  * @param[in] enable TRUE if the zebra FPM module should be enabled
+ * @param[in] format to use to talk to the FPM. Can be 'netink' or 'protobuf'.
  *
  * Returns TRUE on success.
  */
 int
-zfpm_init (struct thread_master *master, int enable, uint16_t port)
+zfpm_init (struct thread_master *master, int enable, uint16_t port,
+	   const char *format)
 {
   static int initialized = 0;
 
@@ -1618,16 +1715,6 @@
   zfpm_g->sock = -1;
   zfpm_g->state = ZFPM_STATE_IDLE;
 
-  /*
-   * Netlink must currently be available for the Zebra-FPM interface
-   * to be enabled.
-   */
-#ifndef HAVE_NETLINK
-  enable = 0;
-#endif
-
-  zfpm_g->enabled = enable;
-
   zfpm_stats_init (&zfpm_g->stats);
   zfpm_stats_init (&zfpm_g->last_ivl_stats);
   zfpm_stats_init (&zfpm_g->cumulative_stats);
@@ -1637,6 +1724,16 @@
   install_element (CONFIG_NODE, &fpm_remote_ip_cmd);
   install_element (CONFIG_NODE, &no_fpm_remote_ip_cmd);
 
+  zfpm_init_message_format(format);
+
+  /*
+   * Disable FPM interface if no suitable format is available.
+   */
+  if (zfpm_g->message_format == ZFPM_MSG_FORMAT_NONE)
+      enable = 0;
+
+  zfpm_g->enabled = enable;
+
   if (!enable) {
     return 1;
   }
diff --git a/zebra/zebra_fpm.h b/zebra/zebra_fpm.h
index 44dec02..ecd23c7 100644
--- a/zebra/zebra_fpm.h
+++ b/zebra/zebra_fpm.h
@@ -28,7 +28,8 @@
 /*
  * Externs.
  */
-extern int zfpm_init (struct thread_master *master, int enable, uint16_t port);
+extern int zfpm_init (struct thread_master *master, int enable, uint16_t port,
+		      const char *message_format);
 extern void zfpm_trigger_update (struct route_node *rn, const char *reason);
 
 #endif /* _ZEBRA_FPM_H */
diff --git a/zebra/zebra_fpm_private.h b/zebra/zebra_fpm_private.h
index 809a70a..1c4fd4c 100644
--- a/zebra/zebra_fpm_private.h
+++ b/zebra/zebra_fpm_private.h
@@ -53,4 +53,9 @@
 zfpm_netlink_encode_route (int cmd, rib_dest_t *dest, struct rib *rib,
 			   char *in_buf, size_t in_buf_len);
 
+extern int
+zfpm_protobuf_encode_route (rib_dest_t *dest, struct rib *rib,
+			    uint8_t *in_buf, size_t in_buf_len);
+
+extern struct rib *zfpm_route_for_update (rib_dest_t *dest);
 #endif /* _ZEBRA_FPM_PRIVATE_H */
diff --git a/zebra/zebra_fpm_protobuf.c b/zebra/zebra_fpm_protobuf.c
new file mode 100644
index 0000000..beef310
--- /dev/null
+++ b/zebra/zebra_fpm_protobuf.c
@@ -0,0 +1,311 @@
+/*
+ * zebra_fpm_protobuf.c
+ *
+ * @copyright Copyright (C) 2016 Sproute Networks, Inc.
+ *
+ * @author Avneesh Sachdev <avneesh@sproute.com>
+ *
+ * This file is part of Quagga.
+ *
+ * Quagga is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation; either version 2, or (at your option) any
+ * later version.
+ *
+ * Quagga is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with Quagga; see the file COPYING.  If not, write to the Free
+ * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
+ * 02111-1307, USA.
+ */
+#include <zebra.h>
+
+#include "log.h"
+#include "rib.h"
+
+#include "qpb/qpb.pb-c.h"
+#include "qpb/qpb.h"
+#include "qpb/qpb_allocator.h"
+#include "qpb/linear_allocator.h"
+#include "fpm/fpm_pb.h"
+
+#include "zebra_fpm_private.h"
+
+/*
+ * create_delete_route_message
+ */
+static Fpm__DeleteRoute *
+create_delete_route_message (qpb_allocator_t *allocator, rib_dest_t *dest,
+			     struct rib *rib)
+{
+  Fpm__DeleteRoute *msg;
+
+  msg = QPB_ALLOC(allocator, typeof(*msg));
+  if (!msg) {
+    assert(0);
+    return NULL;
+  }
+
+  fpm__delete_route__init(msg);
+  msg->vrf_id = rib_dest_vrf(dest)->vrf_id;
+
+  qpb_address_family_set(&msg->address_family, rib_dest_af(dest));
+
+  /*
+   * XXX Hardcode subaddress family for now.
+   */
+  msg->sub_address_family = QPB__SUB_ADDRESS_FAMILY__UNICAST;
+  msg->key = fpm_route_key_create (allocator, rib_dest_prefix(dest));
+  if (!msg->key) {
+    assert(0);
+    return NULL;
+  }
+
+  return msg;
+}
+
+/*
+ * add_nexthop
+ */
+static inline int
+add_nexthop (qpb_allocator_t *allocator, Fpm__AddRoute *msg, rib_dest_t *dest,
+	     struct nexthop *nexthop)
+{
+  uint32_t if_index;
+  union g_addr *gateway, *src;
+
+  gateway = src = NULL;
+
+  if_index = nexthop->ifindex;
+
+  if (nexthop->type == NEXTHOP_TYPE_IPV4
+      || nexthop->type == NEXTHOP_TYPE_IPV4_IFINDEX)
+    {
+      gateway = &nexthop->gate;
+      if (nexthop->src.ipv4.s_addr)
+	src = &nexthop->src;
+    }
+
+  if (nexthop->type == NEXTHOP_TYPE_IPV6
+      || nexthop->type == NEXTHOP_TYPE_IPV6_IFNAME
+      || nexthop->type == NEXTHOP_TYPE_IPV6_IFINDEX)
+    {
+      gateway = &nexthop->gate;
+    }
+
+  if (nexthop->type == NEXTHOP_TYPE_IFINDEX
+      || nexthop->type == NEXTHOP_TYPE_IFNAME)
+    {
+      if (nexthop->src.ipv4.s_addr)
+	src = &nexthop->src;
+    }
+
+  if (!gateway && if_index == 0)
+    return 0;
+
+  /*
+   * We have a valid nexthop.
+   */
+  {
+    Fpm__Nexthop *pb_nh;
+    pb_nh = QPB_ALLOC(allocator, typeof(*pb_nh));
+    if (!pb_nh) {
+      assert(0);
+      return 0;
+    }
+
+    fpm__nexthop__init(pb_nh);
+
+    if (if_index != 0) {
+      pb_nh->if_id = qpb_if_identifier_create (allocator, if_index);
+    }
+
+    if (gateway) {
+      pb_nh->address = qpb_l3_address_create (allocator, gateway,
+					      rib_dest_af(dest));
+    }
+
+    msg->nexthops[msg->n_nexthops++] = pb_nh;
+  }
+
+  // TODO: Use src.
+
+  return 1;
+}
+
+/*
+ * create_add_route_message
+ */
+static Fpm__AddRoute *
+create_add_route_message (qpb_allocator_t *allocator, rib_dest_t *dest,
+			  struct rib *rib)
+{
+  Fpm__AddRoute *msg;
+  int discard;
+  struct nexthop *nexthop, *tnexthop;
+  int recursing;
+  uint num_nhs, u;
+  struct nexthop *nexthops[MAX (MULTIPATH_NUM, 64)];
+
+  msg = QPB_ALLOC(allocator, typeof(*msg));
+  if (!msg) {
+    assert(0);
+    return NULL;
+  }
+
+  fpm__add_route__init(msg);
+
+  msg->vrf_id = rib_dest_vrf(dest)->vrf_id;
+
+  qpb_address_family_set (&msg->address_family, rib_dest_af(dest));
+
+  /*
+   * XXX Hardcode subaddress family for now.
+   */
+  msg->sub_address_family = QPB__SUB_ADDRESS_FAMILY__UNICAST;
+  msg->key = fpm_route_key_create (allocator, rib_dest_prefix(dest));
+  qpb_protocol_set (&msg->protocol, rib->type);
+
+  if ((rib->flags & ZEBRA_FLAG_BLACKHOLE) || (rib->flags & ZEBRA_FLAG_REJECT))
+    discard = 1;
+  else
+    discard = 0;
+
+  if (discard)
+    {
+      if (rib->flags & ZEBRA_FLAG_BLACKHOLE) {
+	msg->route_type = FPM__ROUTE_TYPE__BLACKHOLE;
+      } else if (rib->flags & ZEBRA_FLAG_REJECT) {
+	msg->route_type = FPM__ROUTE_TYPE__UNREACHABLE;
+      } else {
+	assert (0);
+      }
+      return msg;
+    }
+  else {
+    msg->route_type = FPM__ROUTE_TYPE__NORMAL;
+  }
+
+  msg->metric = rib->metric;
+
+  /*
+   * Figure out the set of nexthops to be added to the message.
+   */
+  num_nhs = 0;
+  for (ALL_NEXTHOPS_RO (rib->nexthop, nexthop, tnexthop, recursing))
+    {
+      if (MULTIPATH_NUM != 0 && num_nhs >= MULTIPATH_NUM)
+        break;
+
+      if (num_nhs >= ZEBRA_NUM_OF(nexthops))
+	break;
+
+      if (CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_RECURSIVE))
+        continue;
+
+      if (!CHECK_FLAG (nexthop->flags, NEXTHOP_FLAG_ACTIVE))
+	continue;
+
+      nexthops[num_nhs] = nexthop;
+      num_nhs++;
+    }
+
+  if (!num_nhs) {
+    zfpm_debug ("netlink_encode_route(): No useful nexthop.");
+    assert(0);
+    return NULL;
+  }
+
+  /*
+   * And add them to the message.
+   */
+  if (!(msg->nexthops = qpb_alloc_ptr_array(allocator, num_nhs))) {
+    assert(0);
+    return NULL;
+  }
+
+  msg->n_nexthops = 0;
+  for (u = 0; u < num_nhs; u++) {
+    if (!add_nexthop(allocator, msg, dest, nexthops[u])) {
+      assert(0);
+      return NULL;
+    }
+  }
+
+  assert(msg->n_nexthops == num_nhs);
+
+  return msg;
+}
+
+/*
+ * create_route_message
+ */
+static Fpm__Message *
+create_route_message (qpb_allocator_t *allocator, rib_dest_t *dest,
+		      struct rib *rib)
+{
+  Fpm__Message *msg;
+
+  msg = QPB_ALLOC(allocator, typeof(*msg));
+  if (!msg) {
+    assert(0);
+    return NULL;
+  }
+
+  fpm__message__init(msg);
+
+  if (!rib) {
+    msg->type = FPM__MESSAGE__TYPE__DELETE_ROUTE;
+    msg->delete_route = create_delete_route_message(allocator, dest, rib);
+    if (!msg->delete_route) {
+      assert(0);
+      return NULL;
+    }
+    return msg;
+  }
+
+  msg->type = FPM__MESSAGE__TYPE__ADD_ROUTE;
+  msg->add_route = create_add_route_message(allocator, dest, rib);
+  if (!msg->add_route) {
+    assert(0);
+    return NULL;
+  }
+
+  return msg;
+}
+
+/*
+ * zfpm_protobuf_encode_route
+ *
+ * Create a protobuf message corresponding to the given route in the
+ * given buffer space.
+ *
+ * Returns the number of bytes written to the buffer. 0 or a negative
+ * value indicates an error.
+ */
+int
+zfpm_protobuf_encode_route (rib_dest_t *dest, struct rib *rib,
+			    uint8_t *in_buf, size_t in_buf_len)
+{
+  Fpm__Message *msg;
+  QPB_DECLARE_STACK_ALLOCATOR (allocator, 4096);
+  size_t len;
+
+  QPB_INIT_STACK_ALLOCATOR (allocator);
+
+  msg = create_route_message(&allocator, dest, rib);
+  if (!msg) {
+    assert(0);
+    return 0;
+  }
+
+  len = fpm__message__pack(msg, (uint8_t *) in_buf);
+  assert(len <= in_buf_len);
+
+  QPB_RESET_STACK_ALLOCATOR (allocator);
+  return len;
+}