EtherGuard-VPN/path/path.go

package path

import (
	"errors"
	"fmt"
	"io/ioutil"
	"math"
	"strings"
	"sync"
	"time"

	"github.com/KusakabeSi/EtherGuard-VPN/mtypes"
	orderedmap "github.com/KusakabeSi/EtherGuard-VPN/orderdmap"
	yaml "gopkg.in/yaml.v2"
)

func (g *IG) GetCurrentTime() time.Time {
	return time.Now().Add(g.ntp_offset).Round(0)
}

type Latency struct {
	ping           float64
	ping_old       float64
	additionalCost float64
	validUntil     time.Time
}

type Fullroute struct {
	Next      mtypes.NextHopTable `yaml:"NextHopTable"`
	Dist      mtypes.DistTable    `yaml:"DistanceTable"`
	Dist_noAC mtypes.DistTable    `yaml:"DistanceTableWithoutAdditionalaCost"`
}

// IG is a graph of integers that satisfies the Graph interface.
type IG struct {
	Vert                 map[mtypes.Vertex]bool
	edges                map[mtypes.Vertex]map[mtypes.Vertex]*Latency
	edgelock             *sync.RWMutex
	gsetting             mtypes.GraphRecalculateSetting
	SuperNodeInfoTimeout time.Duration
	RecalculateCoolDown  time.Duration
	TimeoutCheckInterval time.Duration
	recalculateTime      time.Time
	dlTable              mtypes.DistTable
	dlTable_noAC         mtypes.DistTable
	nhTable              mtypes.NextHopTable
	changed              bool
	NhTableExpire        time.Time
	IsSuperMode          bool
	loglevel             mtypes.LoggerInfo

	ntp_wg      sync.WaitGroup
	ntp_info    mtypes.NTPInfo
	ntp_init_t  time.Time
	ntp_offset  time.Duration
	ntp_servers orderedmap.OrderedMap // serverurl:lentancy
}

func NewGraph(num_node int, IsSuperMode bool, theconfig mtypes.GraphRecalculateSetting, ntpinfo mtypes.NTPInfo, loglevel mtypes.LoggerInfo) (*IG, error) {
	g := IG{
		edgelock:             &sync.RWMutex{},
		gsetting:             theconfig,
		RecalculateCoolDown:  mtypes.S2TD(theconfig.RecalculateCoolDown),
		TimeoutCheckInterval: mtypes.S2TD(theconfig.TimeoutCheckInterval),
		ntp_info:             ntpinfo,
	}
	g.Vert = make(map[mtypes.Vertex]bool, num_node)
	g.edges = make(map[mtypes.Vertex]map[mtypes.Vertex]*Latency, num_node)
	g.IsSuperMode = IsSuperMode
	g.loglevel = loglevel
	g.InitNTP()
	return &g, nil
}

func (g *IG) GetWeightType(x float64) (y float64) {
	x = math.Abs(x)
	y = x
	if g.gsetting.JitterTolerance > 0.001 && g.gsetting.JitterToleranceMultiplier > 1 {
		t := g.gsetting.JitterTolerance
		r := g.gsetting.JitterToleranceMultiplier
		y = math.Pow(math.Ceil(math.Pow(x/t, 1/r)), r) * t
	}
	return y
}

func (g *IG) ShouldUpdate(oldval float64, newval float64, withCooldown bool) bool {
	if (oldval >= mtypes.Infinity) != (newval >= mtypes.Infinity) {
		return true
	}
	if withCooldown {
		if g.recalculateTime.Add(g.RecalculateCoolDown).After(time.Now()) {
			return false
		}
	}
	oldval = math.Abs(oldval * 1000)
	newval = math.Abs(newval * 1000)
	if g.IsSuperMode {
		if g.gsetting.JitterTolerance > 0.001 && g.gsetting.JitterToleranceMultiplier >= 1 {
			diff := math.Abs(newval - oldval)
			x := math.Max(oldval, newval)
			t := g.gsetting.JitterTolerance
			r := g.gsetting.JitterToleranceMultiplier
			return diff > t+x*(r-1) // https://www.desmos.com/calculator/raoti16r5n
		}
		return oldval == newval
	} else {
		return g.GetWeightType(oldval) != g.GetWeightType(newval)
	}
}

func (g *IG) CheckAnyShouldUpdate(withCooldown bool) bool {
	vert := g.Vertices()
	for u := range vert {
		for v := range vert {
			if u != v {
				newVal := g.Weight(u, v, false)
				oldVal := g.OldWeight(u, v, false)
				if g.ShouldUpdate(oldVal, newVal, withCooldown) {
					return true
				}
			}
		}
	}
	return false
}

func (g *IG) RecalculateNhTable(checkchange bool) (changed bool) {
	if g.gsetting.StaticMode {
		if g.changed {
			changed = checkchange
		}
		return
	}
	if !g.CheckAnyShouldUpdate(true) {
		return
	}

	dist, dist_noAC, next, _ := g.FloydWarshall(false)
	changed = false
	if checkchange {
	CheckLoop:
		for src, dsts := range next {
			for dst, old_next := range dsts {
				nexthop := g.Next(src, dst)
				if old_next != nexthop {
					changed = true
					break CheckLoop
				}
			}
		}
	}
	g.dlTable, g.dlTable_noAC, g.nhTable = dist, dist_noAC, next
	g.recalculateTime = time.Now()

	return
}

func (g *IG) RemoveVirt(v mtypes.Vertex, recalculate bool, checkchange bool) (changed bool) { //Waiting for test
	g.edgelock.Lock()
	delete(g.Vert, v)
	delete(g.edges, v)
	for u := range g.edges {
		delete(g.edges[u], v)
	}
	g.edgelock.Unlock()
	g.changed = true
	if recalculate {
		changed = g.RecalculateNhTable(checkchange)
	}
	return
}

func (g *IG) UpdateLatency(src mtypes.Vertex, dst mtypes.Vertex, val float64, TimeToAlive float64, SuperAdditionalCost float64, recalculate bool, checkchange bool) (changed bool) {
	return g.UpdateLatencyMulti([]mtypes.PongMsg{{
		Src_nodeID:     src,
		Dst_nodeID:     dst,
		Timediff:       val,
		AdditionalCost: SuperAdditionalCost,
		TimeToAlive:    TimeToAlive,
	}}, recalculate, checkchange)
}

func (g *IG) UpdateLatencyMulti(pong_info []mtypes.PongMsg, recalculate bool, checkchange bool) (changed bool) {
	g.edgelock.Lock()
	should_update := false
	for _, pong_msg := range pong_info {
		u := pong_msg.Src_nodeID
		v := pong_msg.Dst_nodeID
		newval := pong_msg.Timediff
		if dst_latency, ok := g.gsetting.ManualLatency[mtypes.NodeID_Broadcast]; ok {
			if _, ok := dst_latency[mtypes.NodeID_Broadcast]; ok {
				newval = dst_latency[mtypes.NodeID_Broadcast] / 1000 // s to ms
			}
			if _, ok := dst_latency[v]; ok {
				newval = dst_latency[v] / 1000 // s to ms
			}
		}
		if dst_latency, ok := g.gsetting.ManualLatency[u]; ok {
			if _, ok := dst_latency[mtypes.NodeID_Broadcast]; ok {
				newval = dst_latency[mtypes.NodeID_Broadcast] / 1000 // s to ms
			}
			if _, ok := dst_latency[v]; ok {
				newval = dst_latency[v] / 1000 // s to ms
			}
		}
		w := newval
		additionalCost := pong_msg.AdditionalCost
		if additionalCost < 0 {
			additionalCost = 0
		}
		g.Vert[u] = true
		g.Vert[v] = true
		if _, ok := g.edges[u]; !ok {
			g.recalculateTime = time.Time{}
			g.edges[u] = make(map[mtypes.Vertex]*Latency)
		}
		g.edgelock.Unlock()
		oldval := g.OldWeight(u, v, false)
		g.edgelock.Lock()
		should_update = should_update || g.ShouldUpdate(oldval, w, false)
		if _, ok := g.edges[u][v]; ok {
			g.edges[u][v].ping = w
			g.edges[u][v].validUntil = time.Now().Add(mtypes.S2TD(pong_msg.TimeToAlive))
			g.edges[u][v].additionalCost = additionalCost / 1000
		} else {
			g.edges[u][v] = &Latency{
				ping:           w,
				ping_old:       mtypes.Infinity,
				validUntil:     time.Now().Add(mtypes.S2TD(pong_msg.TimeToAlive)),
				additionalCost: additionalCost / 1000,
			}
		}
	}
	g.edgelock.Unlock()
	if should_update && recalculate {
		changed = g.RecalculateNhTable(checkchange)
	}
	return
}
func (g *IG) Vertices() map[mtypes.Vertex]bool {
	vr := make(map[mtypes.Vertex]bool)
	g.edgelock.RLock()
	defer g.edgelock.RUnlock()
	for k, v := range g.Vert { //copy a new list
		vr[k] = v
	}
	return vr
}
func (g *IG) Neighbors(v mtypes.Vertex) (vs []mtypes.Vertex) {
	g.edgelock.RLock()
	defer g.edgelock.RUnlock()
	for k := range g.edges[v] { //copy a new list
		vs = append(vs, k)
	}
	return vs
}

func (g *IG) Next(u, v mtypes.Vertex) mtypes.Vertex {
	if _, ok := g.nhTable[u]; !ok {
		return mtypes.NodeID_Invalid
	}
	if _, ok := g.nhTable[u][v]; !ok {
		return mtypes.NodeID_Invalid
	}
	return g.nhTable[u][v]
}

func (g *IG) Weight(u, v mtypes.Vertex, withAC bool) (ret float64) {
	g.edgelock.RLock()
	defer g.edgelock.RUnlock()
	//defer func() { fmt.Println(u, v, ret) }()
	if u == v {
		return 0
	}
	if _, ok := g.edges[u]; !ok {
		return mtypes.Infinity
	}
	if _, ok := g.edges[u][v]; !ok {
		return mtypes.Infinity
	}
	if time.Now().After(g.edges[u][v].validUntil) {
		return mtypes.Infinity
	}
	ret = g.edges[u][v].ping
	if withAC {
		ret += g.edges[u][v].additionalCost
	}
	if ret >= mtypes.Infinity {
		return mtypes.Infinity
	}
	return
}

func (g *IG) OldWeight(u, v mtypes.Vertex, withAC bool) (ret float64) {
	g.edgelock.RLock()
	defer g.edgelock.RUnlock()
	if u == v {
		return 0
	}
	if _, ok := g.edges[u]; !ok {
		return mtypes.Infinity
	}
	if _, ok := g.edges[u][v]; !ok {
		return mtypes.Infinity
	}
	ret = g.edges[u][v].ping_old
	if withAC {
		ret += g.edges[u][v].additionalCost
	}
	if ret >= mtypes.Infinity {
		return mtypes.Infinity
	}
	return
}

func (g *IG) SetWeight(u, v mtypes.Vertex, weight float64) {
	g.edgelock.Lock()
	defer g.edgelock.Unlock()
	if _, ok := g.edges[u]; !ok {
		return
	}
	if _, ok := g.edges[u][v]; !ok {
		return
	}
	g.edges[u][v].ping = weight
}

func (g *IG) SetOldWeight(u, v mtypes.Vertex, weight float64) {
	g.edgelock.Lock()
	defer g.edgelock.Unlock()
	if _, ok := g.edges[u]; !ok {
		return
	}
	if _, ok := g.edges[u][v]; !ok {
		return
	}
	g.edges[u][v].ping_old = weight
}

func (g *IG) RemoveAllNegativeValue() {
	vert := g.Vertices()
	for u := range vert {
		for v := range vert {
			if g.Weight(u, v, true) < 0 {
				if g.loglevel.LogInternal {
					fmt.Printf("Internal: Remove negative value : edge[%v][%v] = 0\n", u, v)
				}
				g.SetWeight(u, v, 0)
			}
		}
	}
}

func (g *IG) FloydWarshall(again bool) (dist mtypes.DistTable, dist_noAC mtypes.DistTable, next mtypes.NextHopTable, err error) {
	if g.loglevel.LogInternal {
		if !again {
			fmt.Println("Internal: Start Floyd Warshall algorithm")
		} else {
			fmt.Println("Internal: Start Floyd Warshall algorithm again")

		}
	}
	vert := g.Vertices()
	dist = make(mtypes.DistTable)
	dist_noAC = make(mtypes.DistTable)
	next = make(mtypes.NextHopTable)
	for u := range vert {
		dist[u] = make(map[mtypes.Vertex]float64)
		dist_noAC[u] = make(map[mtypes.Vertex]float64)
		next[u] = make(map[mtypes.Vertex]mtypes.Vertex)
		for v := range vert {
			dist[u][v] = mtypes.Infinity
			dist_noAC[u][v] = mtypes.Infinity
		}
		dist[u][u] = 0
		dist_noAC[u][u] = 0
		for _, v := range g.Neighbors(u) {
			w := g.Weight(u, v, true)
			wo := g.Weight(u, v, false)
			if w < mtypes.Infinity {
				v := v
				dist[u][v] = w
				dist_noAC[u][v] = wo
				next[u][v] = v
			}
			g.SetOldWeight(u, v, wo)
		}
	}
	for k := range vert {
		for i := range vert {
			for j := range vert {
				if dist[i][k] < mtypes.Infinity && dist[k][j] < mtypes.Infinity {
					if dist[i][j] > dist[i][k]+dist[k][j] {
						dist[i][j] = dist[i][k] + dist[k][j]
						dist_noAC[i][j] = dist_noAC[i][k] + dist_noAC[k][j]
						next[i][j] = next[i][k]
					}
				}
			}
		}
	}
	for i := range dist {
		if dist[i][i] < 0 {
			if !again {
				if g.loglevel.LogInternal {
					fmt.Println("Internal: Error: Negative cycle detected")
				}
				g.RemoveAllNegativeValue()
				err = errors.New("negative cycle detected")
				dist, dist_noAC, next, _ = g.FloydWarshall(true)
				return
			} else {
				dist = make(mtypes.DistTable)
				dist_noAC = make(mtypes.DistTable)
				next = make(mtypes.NextHopTable)
				err = errors.New("negative cycle detected again")
				if g.loglevel.LogInternal {
					fmt.Println("Internal: Error: Negative cycle detected again")
				}
				return
			}
		}
	}
	return
}

func (g *IG) Path(u, v mtypes.Vertex) (path []mtypes.Vertex, err error) {
	g.edgelock.RLock()
	defer g.edgelock.RUnlock()
	footprint := make(map[mtypes.Vertex]bool)
	for u != v {
		if _, has := footprint[u]; has {
			return path, fmt.Errorf("cycle detected in nhTable, s:%v e:%v path:%v", u, v, path)
		}
		if _, ok := g.nhTable[u]; !ok {
			return path, fmt.Errorf("nhTable[%v] not exist", u)
		}
		if _, ok := g.nhTable[u][v]; !ok {
			return path, fmt.Errorf("nhTable[%v][%v] not exist", u, v)
		}
		path = append(path, u)
		footprint[u] = true
		u = g.nhTable[u][v]
	}
	path = append(path, u)
	return path, nil
}

func (g *IG) SetNHTable(nh mtypes.NextHopTable) { // set nhTable from supernode
	g.edgelock.Lock()
	defer g.edgelock.Unlock()
	g.nhTable = nh
	g.changed = true
	g.NhTableExpire = time.Now().Add(g.SuperNodeInfoTimeout)
}

func (g *IG) GetNHTable(recalculate bool) mtypes.NextHopTable {
	if recalculate && time.Now().After(g.NhTableExpire) {
		g.RecalculateNhTable(false)
	}
	return g.nhTable
}

func (g *IG) GetDtst(withAC bool) mtypes.DistTable {
	if withAC {
		return g.dlTable
	} else {
		return g.dlTable_noAC
	}

}

func (g *IG) GetEdges(isOld bool, withAC bool) (edges map[mtypes.Vertex]map[mtypes.Vertex]float64) {
	vert := g.Vertices()
	edges = make(map[mtypes.Vertex]map[mtypes.Vertex]float64, len(vert))
	for src := range vert {
		edges[src] = make(map[mtypes.Vertex]float64, len(vert))
		for dst := range vert {
			if src != dst {
				if isOld {
					edges[src][dst] = g.OldWeight(src, dst, withAC)
				} else {
					edges[src][dst] = g.Weight(src, dst, withAC)
				}
			}
		}
	}
	return
}

func (g *IG) GetBoardcastList(id mtypes.Vertex) (tosend map[mtypes.Vertex]bool) {
	tosend = make(map[mtypes.Vertex]bool)
	for _, element := range g.nhTable[id] {
		tosend[element] = true
	}
	return
}

func (g *IG) GetBoardcastThroughList(self_id mtypes.Vertex, in_id mtypes.Vertex, src_id mtypes.Vertex) (tosend map[mtypes.Vertex]bool, errs []error) {
	tosend = make(map[mtypes.Vertex]bool)
	for check_id := range g.GetBoardcastList(self_id) {
		path, err := g.Path(src_id, check_id)
		if err != nil {
			errs = append(errs, err)
			continue
		}
		for _, path_node := range path {
			if path_node == self_id && check_id != in_id {
				tosend[check_id] = true
				continue
			}
		}
	}
	return
}

func printExample() {
	fmt.Println(`X 1   2   3   4   5   6
1 0   0.5 Inf Inf Inf Inf
2 0.5 0   0.5 0.5 Inf Inf
3 Inf 0.5 0   0.5 0.5 Inf
4 Inf 0.5 0.5 0   Inf 0.5
5 Inf Inf 0.5 Inf 0   Inf
6 Inf Inf Inf 0.5 Inf 0`)
}

func ParseDistanceMatrix(input string) ([]mtypes.PongMsg, error) {
	lines := strings.Split(input, "\n")
	verts := strings.Fields(lines[0])
	ret := make([]mtypes.PongMsg, 0, len(verts)*len(verts))
	for li, line := range lines[1:] {
		element := strings.Fields(line)
		src, err := mtypes.String2NodeID(element[0])
		if err != nil {
			return ret, err
		}
		if len(element) != len(verts) {
			return ret, fmt.Errorf("parse error at line %v: element number mismatch to node id number", li)
		}
		for ei, sval := range element[1:] {
			val, err := mtypes.String2Float64(sval)
			if err != nil {
				return ret, err
			}
			dst, err := mtypes.String2NodeID(verts[ei+1])
			if err != nil {
				return ret, err
			}
			if src != dst && val != mtypes.Infinity {
				ret = append(ret, mtypes.PongMsg{
					Src_nodeID:  src,
					Dst_nodeID:  dst,
					Timediff:    val,
					TimeToAlive: 999999,
				})
			}
		}
	}
	return ret, nil
}

func Solve(filePath string, pe bool) error {
	if pe {
		printExample()
		return nil
	}

	g, _ := NewGraph(3, false, mtypes.GraphRecalculateSetting{}, mtypes.NTPInfo{}, mtypes.LoggerInfo{LogInternal: false})
	inputb, err := ioutil.ReadFile(filePath)
	if err != nil {
		return err
	}

	input := string(inputb)
	all_edge, _ := ParseDistanceMatrix(input)
	g.UpdateLatencyMulti(all_edge, false, false)
	dist, dist_noAC, next, err := g.FloydWarshall(false)
	if err != nil {
		fmt.Println("Error:", err)
	}
	g.dlTable, g.dlTable_noAC, g.nhTable = dist, dist_noAC, next

	rr, _ := yaml.Marshal(Fullroute{
		Dist:      dist,
		Dist_noAC: dist_noAC,
		Next:      next,
	})
	fmt.Print(string(rr))

	fmt.Println("\nHuman readable:")
	fmt.Println("src\tdist\t\tpath")
	all_vert := g.Vertices()
	for u := range all_vert {
		for v := range all_vert {
			if u != v {
				path, err := g.Path(u, v)
				pathstr := fmt.Sprint(path)
				if err != nil {
					pathstr = fmt.Sprint(path)
				}
				fmt.Printf("%d -> %d\t%3f\t%s\n", u, v, dist[u][v], pathstr)
			}
		}
	}
	return nil
}