Repository: scionproto/scion
Pull request #3713 (2020-04-15 15:45:18)

colibri: add application level types for store
Add some application level types.
Add the COLIBRI store interface.

<!-- Reviewable:start -->
---
This change is [<img src="https://reviewable.io/review_button.svg" height="34" align="absmiddle" alt="Reviewable"/>](https://reviewable.io/reviews/scionproto/scion/3713)
<!-- Reviewable:end -->



Patch:
diff --git a/go/cs/reservation/BUILD.bazel b/go/cs/reservation/BUILD.bazel
new file mode 100644
index 000000000..53e3a0849
--- /dev/null
+++ b/go/cs/reservation/BUILD.bazel
@@ -0,0 +1,12 @@
+load("@io_bazel_rules_go//go:def.bzl", "go_library")
+
+go_library(
+    name = "go_default_library",
+    srcs = ["index.go"],
+    importpath = "github.com/scionproto/scion/go/cs/reservation",
+    visibility = ["//visibility:public"],
+    deps = [
+        "//go/lib/colibri/reservation:go_default_library",
+        "//go/lib/serrors:go_default_library",
+    ],
+)
diff --git a/go/cs/reservation/index.go b/go/cs/reservation/index.go
new file mode 100644
index 000000000..864e1f3ae
--- /dev/null
+++ b/go/cs/reservation/index.go
@@ -0,0 +1,67 @@
+// Copyright 2020 ETH Zurich, Anapaya Systems
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package reservation
+
+import (
+	"time"
+
+	"github.com/scionproto/scion/go/lib/colibri/reservation"
+	"github.com/scionproto/scion/go/lib/serrors"
+)
+
+type IndicesInterface interface {
+	Len() int
+	GetIndexNumber(i int) reservation.IndexNumber
+	GetExpiration(i int) time.Time
+}
+
+// ValidateIndices checks that the indices follow consecutive index numbers, their expiration
+// times are greater or equal, and no more than three indices per expiration time. Also no more
+// than 16 indices are allowed.
+func ValidateIndices(indices IndicesInterface) error {
+	lastExpiration := time.Unix(0, 0)
+	lastIndexNumber := reservation.IndexNumber(0).Sub(1)
+	if indices.Len() > 0 {
+		lastIndexNumber = indices.GetIndexNumber(0).Sub(1)
+		if indices.Len() > 16 {
+			// with only 4 bits to represent the index number, we cannot have more than 16 indices
+			return serrors.New("too many indices", "index_count", indices.Len())
+		}
+	}
+	indicesPerExpTime := 0
+	for i := 0; i < indices.Len(); i++ {
+		if indices.GetExpiration(i).Before(lastExpiration) {
+			return serrors.New("index expires before than a previous one",
+				"idx", indices.GetIndexNumber(i),
+				"expiration", indices.GetExpiration(i), "previous_exp", lastExpiration)
+		}
+		if indices.GetExpiration(i).Equal(lastExpiration) {
+			indicesPerExpTime++
+			if indicesPerExpTime > 3 {
+				return serrors.New("more than three indices per expiration time",
+					"expiration", indices.GetExpiration(i))
+			}
+		} else {
+			indicesPerExpTime = 1
+		}
+		if indices.GetIndexNumber(i).Sub(lastIndexNumber) != reservation.IndexNumber(1) {
+			return serrors.New("non consecutive indices", "prev_index_number", lastIndexNumber,
+				"index_number", indices.GetIndexNumber(i))
+		}
+		lastExpiration = indices.GetExpiration(i)
+		lastIndexNumber = indices.GetIndexNumber(i)
+	}
+	return nil
+}
diff --git a/go/cs/reservation/segment/BUILD.bazel b/go/cs/reservation/segment/BUILD.bazel
new file mode 100644
index 000000000..620ec0b6c
--- /dev/null
+++ b/go/cs/reservation/segment/BUILD.bazel
@@ -0,0 +1,35 @@
+load("@io_bazel_rules_go//go:def.bzl", "go_library", "go_test")
+
+go_library(
+    name = "go_default_library",
+    srcs = [
+        "index.go",
+        "path.go",
+        "request.go",
+        "reservation.go",
+    ],
+    importpath = "github.com/scionproto/scion/go/cs/reservation/segment",
+    visibility = ["//visibility:public"],
+    deps = [
+        "//go/cs/reservation:go_default_library",
+        "//go/lib/addr:go_default_library",
+        "//go/lib/colibri/reservation:go_default_library",
+        "//go/lib/common:go_default_library",
+        "//go/lib/serrors:go_default_library",
+    ],
+)
+
+go_test(
+    name = "go_default_test",
+    srcs = [
+        "path_test.go",
+        "reservation_test.go",
+    ],
+    embed = [":go_default_library"],
+    deps = [
+        "//go/lib/colibri/reservation:go_default_library",
+        "//go/lib/common:go_default_library",
+        "//go/lib/xtest:go_default_library",
+        "@com_github_stretchr_testify//require:go_default_library",
+    ],
+)
diff --git a/go/cs/reservation/segment/index.go b/go/cs/reservation/segment/index.go
new file mode 100644
index 000000000..cdb4ba7c5
--- /dev/null
+++ b/go/cs/reservation/segment/index.go
@@ -0,0 +1,56 @@
+// Copyright 2020 ETH Zurich, Anapaya Systems
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package segment
+
+import (
+	"time"
+
+	base "github.com/scionproto/scion/go/cs/reservation"
+	"github.com/scionproto/scion/go/lib/colibri/reservation"
+)
+
+type IndexState uint8
+
+// possible states of a segment reservation index.
+const (
+	IndexTemporary IndexState = iota
+	IndexPending              // the index is confirmed, but not yet activated.
+	IndexActive
+)
+
+// Index is a segment reservation index.
+type Index struct {
+	Idx        reservation.IndexNumber
+	Expiration time.Time
+	state      IndexState
+	MinBW      reservation.BWCls
+	MaxBW      reservation.BWCls
+	AllocBW    reservation.BWCls
+	Token      reservation.Token
+}
+
+// State returns the read-only state.
+func (index *Index) State() IndexState {
+	return index.state
+}
+
+// Indices is a collection of Index that implements IndicesInterface.
+type Indices []Index
+
+var _ base.IndicesInterface = (*Indices)(nil)
+
+func (idxs Indices) Len() int                                     { return len(idxs) }
+func (idxs Indices) GetIndexNumber(i int) reservation.IndexNumber { return idxs[i].Idx }
+func (idxs Indices) GetExpiration(i int) time.Time                { return idxs[i].Expiration }
diff --git a/go/cs/reservation/segment/path.go b/go/cs/reservation/segment/path.go
new file mode 100644
index 000000000..c4896497b
--- /dev/null
+++ b/go/cs/reservation/segment/path.go
@@ -0,0 +1,61 @@
+// Copyright 2020 ETH Zurich, Anapaya Systems
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package segment
+
+import (
+	"github.com/scionproto/scion/go/lib/addr"
+	"github.com/scionproto/scion/go/lib/common"
+	"github.com/scionproto/scion/go/lib/serrors"
+)
+
+// Path represents a reservation path, in the reservation order.
+type Path []PathStep
+
+func (p Path) Validate() error {
+	if len(p) < 2 {
+		return serrors.New("invalid path length", "len", len(p))
+	}
+	if p[0].Ingress != 0 {
+		return serrors.New("wrong ingress interface for source", "ingress", p[0].Ingress)
+	}
+	if p[len(p)-1].Egress != 0 {
+		return serrors.New("wrong egress interface for destination",
+			"egress ID", p[len(p)-1].Ingress)
+	}
+	return nil
+}
+
+// PathStep is one hop of the Path. For a source AS Ingress will be invalid. Conversely for dst.
+type PathStep struct {
+	AS      addr.AS
+	Ingress common.IFIDType
+	Egress  common.IFIDType
+}
+
+func (s *PathStep) Equal(o *PathStep) bool {
+	return s.AS == o.AS && s.Ingress == o.Ingress && s.Egress == o.Egress
+}
+
+func (p Path) Equal(o Path) bool {
+	if len(p) != len(o) {
+		return false
+	}
+	for i := 0; i < len(p); i++ {
+		if !p[i].Equal(&o[i]) {
+			return false
+		}
+	}
+	return true
+}
diff --git a/go/cs/reservation/segment/request.go b/go/cs/reservation/segment/request.go
new file mode 100644
index 000000000..d171786c6
--- /dev/null
+++ b/go/cs/reservation/segment/request.go
@@ -0,0 +1,46 @@
+// Copyright 2020 ETH Zurich, Anapaya Systems
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package segment
+
+import (
+	"time"
+
+	"github.com/scionproto/scion/go/lib/colibri/reservation"
+)
+
+// SetupReq is a segment reservation setup request. It contains a reference to the reservation
+// it requests, or nil if not yet created.
+// This same type is used for renewal of the segment reservation.
+type SetupReq struct {
+	Reservation *Reservation // nil if no reservation yet
+	Timestamp   time.Time
+	MinBW       uint8
+	MaxBW       uint8
+	SplitCls    uint8
+	StartProps  reservation.PathEndProps
+	EndProps    reservation.PathEndProps
+	AllocTrail  []reservation.AllocationBead
+}
+
+// SetupTelesReq represents a telescopic segment setup.
+type SetupTelesReq struct {
+	SetupReq
+	BaseID reservation.SegmentID
+}
+
+func SetupReqFromWire(raw []byte) (*SetupReq, error) {
+	// TODO(juagargi)
+	return nil, nil
+}
diff --git a/go/cs/reservation/segment/reservation.go b/go/cs/reservation/segment/reservation.go
new file mode 100644
index 000000000..b21c8710c
--- /dev/null
+++ b/go/cs/reservation/segment/reservation.go
@@ -0,0 +1,151 @@
+// Copyright 2020 ETH Zurich, Anapaya Systems
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package segment
+
+import (
+	"time"
+
+	base "github.com/scionproto/scion/go/cs/reservation"
+	"github.com/scionproto/scion/go/lib/colibri/reservation"
+	"github.com/scionproto/scion/go/lib/serrors"
+)
+
+// Reservation represents a segment reservation.
+type Reservation struct {
+	ID          reservation.SegmentID
+	Path        Path
+	Indices     Indices
+	activeIndex int // -1 <= activeIndex < len(Indices)
+}
+
+// Validate will return an error for invalid values.
+func (r *Reservation) Validate() error {
+	if err := base.ValidateIndices(r.Indices); err != nil {
+		return err
+	}
+	if r.activeIndex < -1 || r.activeIndex > 0 || r.activeIndex >= len(r.Indices) {
+		// when we activate an index all previous indices are removed.
+		// Thus activeIndex can only be -1 or 0
+		return serrors.New("invalid active index", "active_index", r.activeIndex)
+	}
+	activeIndex := -1
+	for i, index := range r.Indices {
+		if index.State() == IndexActive {
+			if activeIndex != -1 {
+				return serrors.New("more than one active index",
+					"first_active", r.Indices[activeIndex].Idx, "another_active", index.Idx)
+			}
+			activeIndex = i
+		}
+	}
+	return r.Path.Validate()
+}
+
+// ActiveIndex returns the currently active Index for this reservation, or nil if none.
+func (r *Reservation) ActiveIndex() *Index {
+	if r.activeIndex == -1 {
+		return nil
+	}
+	return &r.Indices[r.activeIndex]
+}
+
+// NewIndex creates a new index in this reservation and returns a pointer to it.
+// Parameters of this index can be changed using the pointer, except for the state.
+func (r *Reservation) NewIndex(expTime time.Time) (reservation.IndexNumber, error) {
+	idx := reservation.IndexNumber(0)
+	if len(r.Indices) > 0 {
+		idx = r.Indices[len(r.Indices)-1].Idx.Add(1)
+	}
+	newIndices := make(Indices, len(r.Indices)+1)
+	copy(newIndices, r.Indices)
+	newIndices[len(newIndices)-1] = Index{
+		Expiration: expTime,
+		Idx:        idx,
+		state:      IndexTemporary,
+	}
+	if err := base.ValidateIndices(newIndices); err != nil {
+		return 0, err
+	}
+	r.Indices = newIndices
+	return r.Indices[len(r.Indices)-1].Idx, nil
+}
+
+// SetIndexConfirmed sets the index as IndexPending (confirmed but not active). If the requested
+// index has state active, it will emit an error.
+func (r *Reservation) SetIndexConfirmed(idx reservation.IndexNumber) error {
+	sliceIndex, err := r.findIndex(idx)
+	if err != nil {
+		return err
+	}
+	if r.Indices[sliceIndex].state == IndexActive {
+		return serrors.New("cannot confirm an already active index", "index_number", idx)
+	}
+	r.Indices[sliceIndex].state = IndexPending
+	return nil
+}
+
+// SetIndexActive sets the index as active. If the reservation had already an active state,
+// it will remove all previous indices.
+func (r *Reservation) SetIndexActive(idx reservation.IndexNumber) error {
+	sliceIndex, err := r.findIndex(idx)
+	if err != nil {
+		return err
+	}
+	if r.activeIndex == sliceIndex {
+		return nil // already active
+	}
+	if r.Indices[sliceIndex].state != IndexPending {
+		return serrors.New("attempt to activate a non confirmed index", "index_number", idx,
+			"state", r.Indices[sliceIndex].state)
+	}
+	if r.activeIndex > -1 {
+		if r.activeIndex > sliceIndex {
+			return serrors.New("activating a past index",
+				"last active", r.Indices[r.activeIndex].Idx, "current", idx)
+		}
+	}
+	// remove indices [lastActive,currActive) so that currActive is at position 0
+	r.Indices = r.Indices[sliceIndex:]
+	r.activeIndex = 0
+	r.Indices[0].state = IndexActive
+	return nil
+}
+
+// RemoveIndex removes all indices from the beginning until this one, inclusive.
+func (r *Reservation) RemoveIndex(idx reservation.IndexNumber) error {
+	sliceIndex, err := r.findIndex(idx)
+	if err != nil {
+		return err
+	}
+	r.Indices = r.Indices[sliceIndex+1:]
+	r.activeIndex -= sliceIndex
+	if r.activeIndex < -1 {
+		r.activeIndex = -1
+	}
+	return nil
+}
+
+func (r *Reservation) findIndex(idx reservation.IndexNumber) (int, error) {
+	var firstIdx reservation.IndexNumber = 0
+	if len(r.Indices) > 0 {
+		firstIdx = r.Indices[0].Idx
+	}
+	sliceIndex := int(idx.Sub(firstIdx))
+	if sliceIndex > len(r.Indices)-1 {
+		return 0, serrors.New("index not found in this reservation", "index_number", idx,
+			"indices length", len(r.Indices))
+	}
+	return sliceIndex, nil
+}
diff --git a/go/cs/reservationstorage/BUILD.bazel b/go/cs/reservationstorage/BUILD.bazel
new file mode 100644
index 000000000..e0223af62
--- /dev/null
+++ b/go/cs/reservationstorage/BUILD.bazel
@@ -0,0 +1,13 @@
+load("@io_bazel_rules_go//go:def.bzl", "go_library")
+
+go_library(
+    name = "go_default_library",
+    srcs = ["store.go"],
+    importpath = "github.com/scionproto/scion/go/cs/reservationstorage",
+    visibility = ["//visibility:public"],
+    deps = [
+        "//go/cs/reservation/e2e:go_default_library",
+        "//go/cs/reservation/segment:go_default_library",
+        "//go/lib/colibri/reservation:go_default_library",
+    ],
+)
diff --git a/go/cs/reservationstorage/store.go b/go/cs/reservationstorage/store.go
new file mode 100644
index 000000000..76beccde4
--- /dev/null
+++ b/go/cs/reservationstorage/store.go
@@ -0,0 +1,33 @@
+// Copyright 2020 ETH Zurich, Anapaya Systems
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package reservationstorage
+
+import (
+	"context"
+
+	"github.com/scionproto/scion/go/cs/reservation/e2e"
+	sgt "github.com/scionproto/scion/go/cs/reservation/segment"
+	rsv "github.com/scionproto/scion/go/lib/colibri/reservation"
+)
+
+// Store is the interface to interact with the reservation store.
+type Store interface {
+	AdmitSegmentReservation(ctx context.Context, req sgt.SetupReq) error
+	ConfirmSegmentReservation(ctx context.Context, id rsv.SegmentID, idx rsv.IndexNumber) error
+	CleanupSegmentReservation(ctx context.Context, id rsv.SegmentID, idx rsv.IndexNumber) error
+	TearDownSegmentReservation(ctx context.Context, id rsv.SegmentID, idx rsv.IndexNumber) error
+	AdmitE2EReservation(ctx context.Context, req e2e.SetupReq) error
+	CleanupE2EReservation(ctx context.Context, id rsv.E2EID, idx rsv.IndexNumber) error
+}
diff --git a/go/lib/colibri/reservation/BUILD.bazel b/go/lib/colibri/reservation/BUILD.bazel
index d0a59af40..b274a4c4c 100644
--- a/go/lib/colibri/reservation/BUILD.bazel
+++ b/go/lib/colibri/reservation/BUILD.bazel
@@ -9,6 +9,7 @@ go_library(
         "//go/lib/addr:go_default_library",
         "//go/lib/common:go_default_library",
         "//go/lib/serrors:go_default_library",
+        "//go/lib/spath:go_default_library",
         "//go/lib/util:go_default_library",
     ],
 )
diff --git a/go/lib/colibri/reservation/types.go b/go/lib/colibri/reservation/types.go
index 7641da7b1..1e19a774f 100644
--- a/go/lib/colibri/reservation/types.go
+++ b/go/lib/colibri/reservation/types.go
@@ -20,6 +20,7 @@ import (
 	"github.com/scionproto/scion/go/lib/addr"
 	"github.com/scionproto/scion/go/lib/common"
 	"github.com/scionproto/scion/go/lib/serrors"
+	"github.com/scionproto/scion/go/lib/spath"
 	"github.com/scionproto/scion/go/lib/util"
 )
 
@@ -32,12 +33,22 @@ type SegmentID struct {
 
 const SegmentIDLen = 10
 
+// NewSegmentID returns a new SegmentID
+func NewSegmentID(AS addr.AS, suffix []byte) (*SegmentID, error) {
+	if len(suffix) != 4 {
+		return nil, serrors.New("wrong suffix length, should be 4", "actual_len", len(suffix))
+	}
+	id := SegmentID{ASID: AS}
+	copy(id.Suffix[:], suffix)
+	return &id, nil
+}
+
 // SegmentIDFromRaw constructs a SegmentID parsing a raw buffer.
 func SegmentIDFromRaw(raw []byte) (
 	*SegmentID, error) {
 
 	if len(raw) < SegmentIDLen {
-		return nil, serrors.New("Buffer too small", "actual", len(raw),
+		return nil, serrors.New("buffer too small", "actual", len(raw),
 			"min", SegmentIDLen)
 	}
 	id := SegmentID{
@@ -49,7 +60,7 @@ func SegmentIDFromRaw(raw []byte) (
 
 func (id *SegmentID) Read(raw []byte) (int, error) {
 	if len(raw) < SegmentIDLen {
-		return 0, serrors.New("Buffer too small", "actual", len(raw), "min", SegmentIDLen)
+		return 0, serrors.New("buffer too small", "actual", len(raw), "min", SegmentIDLen)
 	}
 	auxBuff := make([]byte, 8)
 	common.Order.PutUint64(auxBuff, uint64(id.ASID))
@@ -70,7 +81,7 @@ const E2EIDLen = 16
 // E2EIDFromRaw constructs an E2EID parsing a buffer.
 func E2EIDFromRaw(raw []byte) (*E2EID, error) {
 	if len(raw) < E2EIDLen {
-		return nil, serrors.New("Buffer too small", "actual", len(raw), "min", E2EIDLen)
+		return nil, serrors.New("buffer too small", "actual", len(raw), "min", E2EIDLen)
 	}
 	id := E2EID{
 		ASID: addr.AS(common.Order.Uint64(append([]byte{0, 0}, raw[0:6]...))),
@@ -81,7 +92,7 @@ func E2EIDFromRaw(raw []byte) (*E2EID, error) {
 
 func (id *E2EID) Read(raw []byte) (int, error) {
 	if len(raw) < E2EIDLen {
-		return 0, serrors.New("Buffer too small", "actual", len(raw), "min", E2EIDLen)
+		return 0, serrors.New("buffer too small", "actual", len(raw), "min", E2EIDLen)
 	}
 	auxBuff := make([]byte, 8)
 	common.Order.PutUint64(auxBuff, uint64(id.ASID))
@@ -104,7 +115,7 @@ type BWCls uint8
 // Validate will return an error for invalid values.
 func (b BWCls) Validate() error {
 	if b > 63 {
-		return serrors.New("Invalid BWClass value", "BWCls", b)
+		return serrors.New("invalid BWClass value", "bw_cls", b)
 	}
 	return nil
 }
@@ -119,22 +130,30 @@ type RLC uint8
 // Validate will return an error for invalid values.
 func (c RLC) Validate() error {
 	if c > 63 {
-		return serrors.New("Invalid BWClass", "BWCls", c)
+		return serrors.New("invalid BWClass", "bw_cls", c)
 	}
 	return nil
 }
 
-// Index is a 4 bit index for a reservation.
-type Index uint8
+// IndexNumber is a 4 bit index for a reservation.
+type IndexNumber uint8
 
 // Validate will return an error for invalid values.
-func (i Index) Validate() error {
+func (i IndexNumber) Validate() error {
 	if i >= 1<<4 {
-		return serrors.New("Invalid Index", "Index", i)
+		return serrors.New("invalid IndexNumber", "value", i)
 	}
 	return nil
 }
 
+func (i IndexNumber) Add(other IndexNumber) IndexNumber {
+	return (i + other) % 16
+}
+
+func (i IndexNumber) Sub(other IndexNumber) IndexNumber {
+	return (i - other) % 16
+}
+
 // PathType specifies which type of COLIBRI path this segment reservation or request refers to.
 type PathType uint8
 
@@ -152,7 +171,7 @@ const (
 // Validate will return an error for invalid values.
 func (pt PathType) Validate() error {
 	if pt == UnknownPath || pt > CorePath {
-		return serrors.New("Invalid path type", "PathType", pt)
+		return serrors.New("invalid path type", "path_type", pt)
 	}
 	return nil
 }
@@ -180,7 +199,7 @@ type InfoField struct {
 	ExpirationTick Tick
 	BWCls          BWCls
 	RLC            RLC
-	Idx            Index
+	Idx            IndexNumber
 	PathType       PathType
 }
 
@@ -208,14 +227,14 @@ func (f *InfoField) Validate() error {
 // InfoFieldFromRaw builds an InfoField from the InfoFieldLen bytes buffer.
 func InfoFieldFromRaw(raw []byte) (*InfoField, error) {
 	if len(raw) < InfoFieldLen {
-		return nil, serrors.New("Buffer too small", "min size", InfoFieldLen,
-			"current size", len(raw))
+		return nil, serrors.New("buffer too small", "min_size", InfoFieldLen,
+			"current_size", len(raw))
 	}
 	info := InfoField{
 		ExpirationTick: Tick(common.Order.Uint32(raw[:4])),
 		BWCls:          BWCls(raw[4]),
 		RLC:            RLC(raw[5]),
-		Idx:            Index(raw[6]) >> 4,
+		Idx:            IndexNumber(raw[6]) >> 4,
 		PathType:       PathType(raw[6]) & 0x7,
 	}
 	if err := info.Validate(); err != nil {
@@ -227,7 +246,7 @@ func InfoFieldFromRaw(raw []byte) (*InfoField, error) {
 // Read serializes this InfoField into an array of InfoFieldLen bytes.
 func (f *InfoField) Read(b []byte) (int, error) {
 	if len(b) < InfoFieldLen {
-		return 0, serrors.New("Buffer too short", "size", len(b))
+		return 0, serrors.New("buffer too short", "size", len(b))
 	}
 	common.Order.PutUint32(b[:4], uint32(f.ExpirationTick))
 	b[4] = byte(f.BWCls)
@@ -236,3 +255,45 @@ func (f *InfoField) Read(b []byte) (int, error) {
 	b[7] = 0 // b[7] is padding
 	return 8, nil
 }
+
+// PathEndProps represent the zero or more properties a COLIBRI path can have at both ends.
+type PathEndProps uint8
+
+// The only current properties are "Local" (can be used to create e2e rsvs) and "Transfer" (can be
+// stiched together with another segment reservation). The first 4 bits encode the properties
+// of the "Start" AS, and the last 4 bits encode those of the "End" AS.
+const (
+	StartLocal    PathEndProps = 0x10
+	StartTransfer PathEndProps = 0x20
+	EndLocal      PathEndProps = 0x01
+	EndTransfer   PathEndProps = 0x02
+)
+
+// Validate will return an error for invalid values.
+func (pep PathEndProps) Validate() error {
+	if pep&0x0F > 0x03 {
+		return serrors.New("invalid path end properties (@End)", "path_end_props", pep)
+	}
+	if pep>>4 > 0x03 {
+		return serrors.New("invalid path end properties (@Start)", "path_end_props", pep)
+	}
+	return nil
+}
+
+// AllocationBead represents an allocation resolved in an AS for a given reservation.
+// It is used in an array to represent the allocation trail that happened for a reservation.
+type AllocationBead struct {
+	AllocBW uint8
+	MaxBW   uint8
+}
+
+// Token is used in the data plane to forward COLIBRI packets.
+type Token struct {
+	InfoField
+	HopFields []spath.HopField
+}
+
+// Validate will return an error for invalid values. It will not check the hop fields' validity.
+func (t *Token) Validate() error {
+	return t.InfoField.Validate()
+}


Test patch:
diff --git a/go/cs/reservation/e2e/BUILD.bazel b/go/cs/reservation/e2e/BUILD.bazel
new file mode 100644
index 000000000..40e7419f5
--- /dev/null
+++ b/go/cs/reservation/e2e/BUILD.bazel
@@ -0,0 +1,15 @@
+load("@io_bazel_rules_go//go:def.bzl", "go_library")
+
+go_library(
+    name = "go_default_library",
+    srcs = [
+        "request.go",
+        "reservation.go",
+    ],
+    importpath = "github.com/scionproto/scion/go/cs/reservation/e2e",
+    visibility = ["//visibility:public"],
+    deps = [
+        "//go/cs/reservation/segment:go_default_library",
+        "//go/lib/colibri/reservation:go_default_library",
+    ],
+)
diff --git a/go/cs/reservation/e2e/request.go b/go/cs/reservation/e2e/request.go
new file mode 100644
index 000000000..1fb8ecdc1
--- /dev/null
+++ b/go/cs/reservation/e2e/request.go
@@ -0,0 +1,21 @@
+// Copyright 2020 ETH Zurich, Anapaya Systems
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package e2e
+
+// "github.com/scionproto/scion/go/lib/colibri/reservation"
+
+type SetupReq struct {
+	//
+}
diff --git a/go/cs/reservation/e2e/reservation.go b/go/cs/reservation/e2e/reservation.go
new file mode 100644
index 000000000..9f9106dce
--- /dev/null
+++ b/go/cs/reservation/e2e/reservation.go
@@ -0,0 +1,25 @@
+// Copyright 2020 ETH Zurich, Anapaya Systems
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package e2e
+
+import (
+	"github.com/scionproto/scion/go/cs/reservation/segment"
+	"github.com/scionproto/scion/go/lib/colibri/reservation"
+)
+
+type Reservation struct {
+	ID                 reservation.E2EID
+	SegmentReservation *segment.Reservation
+}
diff --git a/go/cs/reservation/segment/path_test.go b/go/cs/reservation/segment/path_test.go
new file mode 100644
index 000000000..248362f36
--- /dev/null
+++ b/go/cs/reservation/segment/path_test.go
@@ -0,0 +1,118 @@
+// Copyright 2020 ETH Zurich, Anapaya Systems
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package segment
+
+import (
+	"testing"
+
+	"github.com/stretchr/testify/require"
+
+	"github.com/scionproto/scion/go/lib/common"
+	"github.com/scionproto/scion/go/lib/xtest"
+)
+
+func TestValidatePath(t *testing.T) {
+	tc := map[string]struct {
+		Path    Path
+		IsValid bool
+	}{
+		"src-dst": {
+			Path:    newPathFromComponents(0, "ff00:0:1", 1, 1, "ff00:0:2", 0),
+			IsValid: true,
+		},
+		"invalid dst": {
+			Path:    newPathFromComponents(0, "ff00:0:1", 1, 1, "ff00:0:2", 2),
+			IsValid: false,
+		},
+		"invalid src": {
+			Path:    newPathFromComponents(2, "ff00:0:1", 1, 1, "ff00:0:2", 0),
+			IsValid: false,
+		},
+	}
+	for name, tc := range tc {
+		name, tc := name, tc
+		t.Run(name, func(t *testing.T) {
+			t.Parallel()
+			err := tc.Path.Validate()
+			if tc.IsValid {
+				require.NoError(t, err)
+			} else {
+				require.Error(t, err)
+			}
+		})
+	}
+}
+
+func TestEqualPath(t *testing.T) {
+	tc := map[string]struct {
+		Path1   Path
+		Path2   Path
+		IsEqual bool
+	}{
+		"eq1": {
+			Path1:   newPathFromComponents(0, "ff00:0:1", 1, 1, "ff00:0:2", 0),
+			Path2:   newPathFromComponents(0, "ff00:0:1", 1, 1, "ff00:0:2", 0),
+			IsEqual: true,
+		},
+		"eq2": {
+			Path1:   newPathFromComponents(0, "ff00:0:1", 1, 2, "ff00:1:10", 3, 1, "ff00:0:2", 0),
+			Path2:   newPathFromComponents(0, "ff00:0:1", 1, 2, "ff00:1:10", 3, 1, "ff00:0:2", 0),
+			IsEqual: true,
+		},
+		"neq1": {
+			Path1:   newPathFromComponents(0, "ff00:0:1", 1, 1, "ff00:0:2", 0),
+			Path2:   newPathFromComponents(1, "ff00:0:1", 1, 1, "ff00:0:2", 0),
+			IsEqual: false,
+		},
+		"neq2": {
+			Path1:   newPathFromComponents(0, "ff00:0:1", 1, 1, "ff00:0:2", 0),
+			Path2:   newPathFromComponents(0, "ff00:0:3", 1, 1, "ff00:0:2", 0),
+			IsEqual: false,
+		},
+		"neq3": {
+			Path1:   newPathFromComponents(0, "ff00:0:1", 1, 1, "ff00:0:2", 0),
+			Path2:   newPathFromComponents(0, "ff00:0:1", 2, 1, "ff00:0:2", 0),
+			IsEqual: false,
+		},
+		"neq4": {
+			Path1:   newPathFromComponents(0, "ff00:0:1", 1, 2, "ff00:1:10", 3, 1, "ff00:0:2", 0),
+			Path2:   newPathFromComponents(0, "ff00:0:1", 1, 2, "ff00:1:10", 3),
+			IsEqual: false,
+		},
+	}
+	for name, tc := range tc {
+		name, tc := name, tc
+		t.Run(name, func(t *testing.T) {
+			t.Parallel()
+			eq := tc.Path1.Equal(tc.Path2)
+			require.Equal(t, tc.IsEqual, eq)
+		})
+	}
+}
+
+func newPathFromComponents(chain ...interface{}) Path {
+	if len(chain)%3 != 0 {
+		panic("wrong number of arguments")
+	}
+	p := Path{}
+	for i := 0; i < len(chain); i += 3 {
+		p = append(p, PathStep{
+			Ingress: common.IFIDType(chain[i].(int)),
+			AS:      xtest.MustParseAS(chain[i+1].(string)),
+			Egress:  common.IFIDType(chain[i+2].(int)),
+		})
+	}
+	return p
+}
diff --git a/go/cs/reservation/segment/reservation_test.go b/go/cs/reservation/segment/reservation_test.go
new file mode 100644
index 000000000..61f9e5754
--- /dev/null
+++ b/go/cs/reservation/segment/reservation_test.go
@@ -0,0 +1,246 @@
+// Copyright 2020 ETH Zurich, Anapaya Systems
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package segment
+
+import (
+	"testing"
+	"time"
+
+	"github.com/stretchr/testify/require"
+
+	"github.com/scionproto/scion/go/lib/colibri/reservation"
+	"github.com/scionproto/scion/go/lib/xtest"
+)
+
+func TestNewIndex(t *testing.T) {
+	r := newReservation()
+	require.Len(t, r.Indices, 0)
+	expTime := time.Unix(1, 0)
+	idx, err := r.NewIndex(expTime)
+	require.NoError(t, err)
+	require.Len(t, r.Indices, 1)
+	require.True(t, r.Indices[0].Idx == idx)
+	require.True(t, r.Indices[0].Expiration == expTime)
+	require.Equal(t, reservation.IndexNumber(0), idx)
+
+	// up to 3 indices per expiration time
+	idx, err = r.NewIndex(expTime)
+	require.NoError(t, err)
+	require.Equal(t, reservation.IndexNumber(1), idx)
+	idx, err = r.NewIndex(expTime)
+	require.NoError(t, err)
+	require.Equal(t, reservation.IndexNumber(2), idx)
+	r.Indices = r.Indices[:1]
+
+	// exp time is less
+	_, err = r.NewIndex(expTime.Add(-1 * time.Millisecond))
+	require.Error(t, err)
+	require.Len(t, r.Indices, 1)
+
+	// exp time is same
+	idx, err = r.NewIndex(expTime)
+	require.NoError(t, err)
+	require.Len(t, r.Indices, 2)
+	require.True(t, r.Indices[1].Idx == idx)
+	require.True(t, r.Indices[1].Expiration == expTime)
+	require.Equal(t, reservation.IndexNumber(1), idx)
+	idx, err = r.NewIndex(expTime)
+	require.NoError(t, err)
+	require.Len(t, r.Indices, 3)
+	require.True(t, r.Indices[2].Idx == idx)
+	require.True(t, r.Indices[2].Expiration == expTime)
+	require.Equal(t, reservation.IndexNumber(2), idx)
+
+	// too many indices for the same exp time
+	_, err = r.NewIndex(expTime)
+	require.Error(t, err)
+	require.Len(t, r.Indices, 3)
+
+	// exp time is greater
+	expTime = expTime.Add(time.Second)
+	idx, err = r.NewIndex(expTime)
+	require.NoError(t, err)
+	require.Len(t, r.Indices, 4)
+	require.True(t, r.Indices[3].Idx == idx)
+	require.True(t, r.Indices[3].Expiration == expTime)
+	require.Equal(t, reservation.IndexNumber(3), idx)
+
+	// index number rollover
+	r = newReservation()
+	r.NewIndex(expTime)
+	require.Len(t, r.Indices, 1)
+	r.Indices[0].Idx = r.Indices[0].Idx.Sub(1)
+	idx, err = r.NewIndex(expTime)
+	require.NoError(t, err)
+	require.True(t, r.Indices[1].Idx == idx)
+	require.True(t, r.Indices[1].Expiration == expTime)
+	require.Equal(t, reservation.IndexNumber(0), idx)
+}
+func TestReservationValidate(t *testing.T) {
+	r := newReservation()
+	err := r.Validate()
+	require.NoError(t, err)
+
+	// more than 16 indices
+	for i := 0; i < 16; i++ {
+		expTime := time.Unix(int64(i), 0)
+		r.NewIndex(expTime)
+	}
+	require.Len(t, r.Indices, 16)
+	err = r.Validate()
+	require.NoError(t, err)
+	r.Indices = append(r.Indices, r.Indices[15])
+	r.Indices[16].Idx.Add(1) // rollover
+	err = r.Validate()
+	require.Error(t, err)
+
+	// wrong path
+	r.Path = Path{}
+	err = r.Validate()
+	require.Error(t, err)
+
+	r = newReservation()
+	r.activeIndex = 0
+	err = r.Validate()
+	require.Error(t, err)
+
+	// exp time is before
+	r = newReservation()
+	expTime := time.Unix(1, 0)
+	r.NewIndex(expTime)
+	r.NewIndex(expTime)
+	r.Indices[1].Expiration = expTime.Add(-1 * time.Second)
+	err = r.Validate()
+	require.Error(t, err)
+
+	// non consecutive indices
+	r.Indices = r.Indices[:1] // remove tainted index
+	r.NewIndex(expTime)
+	err = r.Validate()
+	require.NoError(t, err)
+	r.Indices[1].Idx = 2
+	err = r.Validate()
+	require.Error(t, err)
+
+	// more than three indices per exp time
+	r.Indices = r.Indices[:1]
+	r.NewIndex(expTime)
+	r.NewIndex(expTime)
+	err = r.Validate()
+	require.NoError(t, err)
+	_, err = r.NewIndex(expTime.Add(time.Second))
+	require.NoError(t, err)
+	r.Indices[3].Expiration = expTime
+	r.Indices[3].Idx = 3
+	err = r.Validate()
+	require.Error(t, err)
+
+	// more than one active index
+	r.Indices = r.Indices[:1]
+	r.NewIndex(expTime)
+	r.Indices[0].state = IndexActive
+	r.Indices[1].state = IndexActive
+	err = r.Validate()
+	require.Error(t, err)
+}
+
+func TestSetIndexConfirmed(t *testing.T) {
+	r := newReservation()
+	expTime := time.Unix(1, 0)
+	id, _ := r.NewIndex(expTime)
+	require.Equal(t, IndexTemporary, r.Indices[0].state)
+	err := r.SetIndexConfirmed(id)
+	require.NoError(t, err)
+	require.Equal(t, IndexPending, r.Indices[0].state)
+
+	// confirm already confirmed
+	err = r.SetIndexConfirmed(id)
+	require.NoError(t, err)
+	require.Equal(t, IndexPending, r.Indices[0].state)
+}
+
+func TestSetIndexActive(t *testing.T) {
+	r := newReservation()
+	expTime := time.Unix(1, 0)
+
+	// index not confirmed
+	idx, _ := r.NewIndex(expTime)
+	err := r.SetIndexActive(idx)
+	require.Error(t, err)
+
+	// normal activation
+	r.SetIndexConfirmed(idx)
+	err = r.SetIndexActive(idx)
+	require.NoError(t, err)
+	require.Equal(t, IndexActive, r.Indices[0].state)
+	require.Equal(t, 0, r.activeIndex)
+
+	// already active
+	err = r.SetIndexActive(idx)
+	require.NoError(t, err)
+
+	// remove previous indices
+	r.NewIndex(expTime)
+	idx, _ = r.NewIndex(expTime)
+	require.Len(t, r.Indices, 3)
+	require.Equal(t, 0, r.activeIndex)
+	r.SetIndexConfirmed(idx)
+	err = r.SetIndexActive(idx)
+	require.NoError(t, err)
+	require.Len(t, r.Indices, 1)
+	require.Equal(t, 0, r.activeIndex)
+	require.True(t, r.Indices[0].Idx == idx)
+}
+
+func TestRemoveIndex(t *testing.T) {
+	r := newReservation()
+	expTime := time.Unix(1, 0)
+	idx, _ := r.NewIndex(expTime)
+	err := r.RemoveIndex(idx)
+	require.NoError(t, err)
+	require.Len(t, r.Indices, 0)
+
+	idx, _ = r.NewIndex(expTime)
+	idx2, _ := r.NewIndex(expTime)
+	err = r.RemoveIndex(idx)
+	require.NoError(t, err)
+	require.Len(t, r.Indices, 1)
+	require.True(t, r.Indices[0].Idx == idx2)
+
+	expTime = expTime.Add(time.Second)
+	r.NewIndex(expTime)
+	idx, _ = r.NewIndex(expTime)
+	idx2, _ = r.NewIndex(expTime)
+	require.Len(t, r.Indices, 4)
+	err = r.RemoveIndex(idx)
+	require.NoError(t, err)
+	require.Len(t, r.Indices, 1)
+	require.True(t, r.Indices[0].Idx == idx2)
+}
+
+func newReservation() *Reservation {
+	segID, err := reservation.NewSegmentID(xtest.MustParseAS("ff00:0:1"),
+		xtest.MustParseHexString("beefcafe"))
+	if err != nil {
+		panic(err)
+	}
+	p := newPathFromComponents(0, "ff00:0:1", 1, 1, "ff00:0:2", 0)
+	r := Reservation{
+		ID:          *segID,
+		Path:        p,
+		activeIndex: -1,
+	}
+	return &r
+}
diff --git a/go/lib/colibri/reservation/types_test.go b/go/lib/colibri/reservation/types_test.go
index 5d01e612e..6dc03cfcb 100644
--- a/go/lib/colibri/reservation/types_test.go
+++ b/go/lib/colibri/reservation/types_test.go
@@ -135,19 +135,31 @@ func TestValidateRLC(t *testing.T) {
 	}
 }
 
-func TestValidateIndex(t *testing.T) {
+func TestValidateIndexNumber(t *testing.T) {
 	for i := 0; i < 16; i++ {
-		idx := Index(i)
+		idx := IndexNumber(i)
 		if err := idx.Validate(); err != nil {
 			t.Fatalf("Unexpected error at i = %d: %v", i, err)
 		}
 	}
-	idx := Index(16)
+	idx := IndexNumber(16)
 	if err := idx.Validate(); err == nil {
 		t.Fatal("Expected validation error but did not get one")
 	}
 }
 
+func TestIndexNumberArithmetic(t *testing.T) {
+	var idx IndexNumber = 1
+	x := idx.Add(IndexNumber(15))
+	if x != IndexNumber(0) {
+		t.Fatalf("Unexpected result %v", x)
+	}
+	x = idx.Sub(IndexNumber(2))
+	if x != IndexNumber(15) {
+		t.Fatalf("Unexpected result %v", x)
+	}
+}
+
 func TestValidatePathType(t *testing.T) {
 	validTypes := []PathType{
 		DownPath,
@@ -256,3 +268,32 @@ func TestInfoFieldRead(t *testing.T) {
 			hex.EncodeToString(raw), hex.EncodeToString(rawReference))
 	}
 }
+
+func TestValidatePathEndProperties(t *testing.T) {
+	for i := 0; i < 4; i++ {
+		pep := PathEndProps(i)
+		if err := pep.Validate(); err != nil {
+			t.Fatalf("Unexpected error at i = %d: %v", i, err)
+		}
+	}
+	pep := PathEndProps(4)
+	if err := pep.Validate(); err == nil {
+		t.Fatal("Expected validation error but got none")
+	}
+
+	for i := 0; i < 4; i++ {
+		pep := PathEndProps(i << 4)
+		if err := pep.Validate(); err != nil {
+			t.Fatalf("Unexpected error at i = %d: %v", i, err)
+		}
+	}
+	pep = PathEndProps(4 << 4)
+	if err := pep.Validate(); err == nil {
+		t.Fatal("Expected validation error but got none")
+	}
+
+	pep = PathEndProps(0x10 | 0x04)
+	if err := pep.Validate(); err == nil {
+		t.Fatal("Expected validation error but got none")
+	}
+}